Model Formulation: Integer Programming

The effective use and applications require, as a first step, the formulation of the model when the problem is presented.

"A model is a vehicle, which bridges the gap between where we are and where we want to go." -Vinay Chhabra & Manish Dewan

In this section, we illustrate the formulation of integer programming problems. The best way to explain a topic is through examples. So consider the following examples.

example Example 1: Model Formulation Integer Programming

You have entered in a treasure cave (with a password KHUL JA SIM SIM) full of three types of valuable stones, amethyst (A), ruby (R), and topaz (T). Each piece of A, R, and T weighs 3, 2, 2 kg., and is known to have a value of 4, 3, 1 crore respectively. You have got a bag that can carry a maximum of 11 kg. Your problem is to decide on how many pieces of each type to carry, within the capacity of your bag, so as to maximize the total value carried. The stones cannot be broken.

"Ready money is Aladdin's lamp." -G. G. Byron


We start the formulation exercise by defining the decision variables.

x1 = Number of amethysts to be carried
x2 = Number of rubies to be carried
x3 = Number of topaz to be carried

The objective function here is to maximize the total value carried, which is given by the linear function.

Maximize 4x1 + 3x2 + x3

Since one amethyst is of 3 kg, one ruby is of 2 kg, one topaz is of 2 kg, and the capacity of the bag being 11 kg., the constraint can be expressed as

3x1 + 2x2 + 2x3 ≤ 11

Finally, we note the fact that stones cannot be broken, i.e., the variables have to take discrete values, which may be stated algebraically as

x1, x2 and x3 are all non-negative integers.

Thus, we have the following formulation:

Maximize (4x1 + 3x2 + x3)

subject to

3x1 + 2x2 + 2x3 ≤ 11
x1, x2 and x3 are all non-negative integers.

Go-No-Go Decisions

exampleExample 2: Integer Programming

Universal Teacher Publications wants to take up four projects. However, because of budget limitations, not all the projects can be selected. It is known that project j has a present value of cj and would require an investment of ajt in period t. The capital available in period t is bt. The problem is to choose projects so as to maximize present value, without violating the budget constraints. Formulate the problem as an I.P.


For choice situations of 'yes-no', 'go-no-go' type, where the objective is to determine whether or not a particular activity is to be undertaken, integer binary variables that can take a value of 0 or 1, can be used to represent the decision variables. Here, we find that for each project, we want to find out whether it should be taken up or not, as such we define four decision variables xj (j = 1, 2, 3, 4) corresponding to each project, and

xj = 1 if a if project is selected.
0 otherwise

Then, the objective function and the constraints can be expressed in terms of the decision variables, to give the required formulation:

Maximize cjxj

subject to
ajtxj ≤ bt, for all period t.

xj = 1 or 0, for all projects.

Basically, there are two algorithms to determine the optimal solution for an integer programming problem. One of these is the cutting plane algorithm devised by Gomory and the other is the branch & bound algorithm developed by Land & Doig. The next section concentrates on the cutting plane method.

Share this article with your friends