Integer Programming Method of Project Selection



Integer programming is a yet another type of constrained optimization method of project selection. In this method, you look towards a decision that works on integer values and not on fractional values. For example, producing a number of cars can never be fractional.

In contrast to the linear programming method, where you work on a continuous model that enables you to define decision variables to be fractional, in the integer programming model, you must consider only integer values for the decision variables. For example, when you can produce 189.86 tones of sugar in a plant, you cannot produce 23.6 airplanes. While you can use linear programming method to select a project in the former case, you must use the linear programming method to select a project in the latter case because fractional solution is not at all realistic for it.

In the integer programming method, you optimize a solution by using the following formula:

image001

Subject to:

image003

image005

 

You define an integer programming method as mixed integer program when you restrict only some of the decision variables as integers. However, when you make sure that the value of all the decision variables must be integers, then it is a pure integer program.

As in case of the linear programming method, where if the decision constraints are of a network type, you can get an integer solution by ignoring integrality restriction. However, in general the decision variables are fractional. For such a solution to be an integer solution, you must consider further steps to arrive at a solution.

Formulation of an Integer Program

 

The integer programming method has extensive programming capabilities that are better than the linear programming capabilities. The integrality restriction of this method reflects the natural sense of non possibility of dividing a problem. For example, when you decide to add a room to a building, it does not make any sense to have a fractional solution. In such problems, you must consider a solution that is integral in nature.

When formulating an integer program, you must consider the following components:

Binary Variables

At times, you might have just two values for making a decision, which are Yes and No. In such cases, the variables in the program are restricted to only two values – 0 or 1. The variables for which you restrict values to 0 or 1 are known as binary, logical, bivalent, or 0 – 1 variables. In formulating an integer program, you use such variables quite frequently.

To formulate a problem solution using a binary variable in an integer program, you use the following formula:

image009

Logical Constraints

When you use decision variables in an integer program, you impose logical constraints. You can consider the following constraints at the time of formulating a solution by using an integer program:

  • Constraint feasibility: For a decision variable, you ask a question whether the choice available for the decision variable satisfies the constraint. If the constraint is satisfied, you assign value 0 to the variable and 1 if it does not.
  • Alternative constraints: For a decision variable, you might have more than one constraint. The decision variable must satisfy at least one constraint and not both.
  • Conditional constraints: In contrast to the alternative constraints, you might have multiple constraints, the decision variable must satisfy both the constraints.
  • Compound alternatives: Compound alternatives include sets of alternative constraints. These sets of constraints can lie in disjointed regions when plotted on a graph or can be on overlapping regions.