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

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.

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.

Solution.

We start the formulation exercise by defining the decision variables.

Let

x_{1} = Number of amethysts to be carried

x_{2} = Number of rubies to be carried

x_{3} = 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_{1} + 3x_{2} + x_{3}

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_{1} + 2x_{2} + 2x_{3} ≤
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_{1}, x_{2} and x_{3} are all non-negative
integers.

Thus, we have the following formulation:

Maximize (4x_{1} + 3x_{2} + x_{3})

subject to

3x_{1} + 2x_{2} + 2x_{3} ≤
11

x_{1}, x_{2} and x_{3} are all non-negative
integers.

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 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

x_{j} = |
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_{j}x_{j}

subject to

a_{jt}x_{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.