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 1

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

Solution.

We start the formulation exercise by defining the decision variables.

Let
x₁ = Number of amethysts to be carried
x₂ = Number of rubies to be carried
x₃ = 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 4x₁ + 3x₂ + x₃

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

3x₁ + 2x₂ + 2x₃ £ 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

x₁, x₂ and x₃ are all non-negative integers.

Thus, we have the following formulation:

Maximize (4x₁ + 3x₂ + x₃)

subject to

3x₁ + 2x₂ + 2x₃ £ 11
x₁, x₂ and x₃ are all non-negative integers.

Go-No-Go Decisions

Example 2

www.universalteacher.com 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 c_j and would require an investment of a_jt in period t. The capital available in period t is b_t. The problem is to choose projects so as to maximize present value, without violating the budget constraints. Formulate the problem as an I.P.

Solution.

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 x_j (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 c_jx_j

subject to
a_jtx_j £ b_t, for all period t.

x_j = 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.