## Integer Programming

Integer programming is a form of linear programming such that all the variables have to be integers because it is not possible for a solution to consists of decimal eg when allocating routes, it is not possible to split a route. >br /> Example: A company has two warehouses
$W_1, \: W_2$
and three outlets
$O_1, \: O_2, \: O_3$
. . Stock is to be sent from warehouse to outlet so that each outlet is fully stocked and each warehouse is fully utilised, with all stock being sent to some outlet.
$W_1, \: W_2$
have capacities of 12 and 8 respectively and outlets
$O_1, \: O_2, \: O_3$
require 8, 7 and 5 units respectively. The cost of transporting a unit from each warehouse to each outlet is summarised in the table below.
 Outlet $O_1$ $O_2$ $O_3$ Capacity $W_1$ 3 5 3 12 Needs $W_2$ 2 7 1 8 8 7 5
We can let the route
$W_1-O_1$
take
$x$
units, then the route
$W_2-O_1$
must take at most
$8-x$
units, hence
$0 \le (8-x) \le 8 \rightarrow 0 \le x \le 8$
.
We can let the route
$W_1-O_2$
take
$y$
units, then the route
$W_2-O_2$
must take at most
$7-y$
units hence
$0 \le (7-y) \le 8 \rightarrow 0 \le y \le 7$
.

We can let the route
$W_1-O_3$
take
$z$
units, then the route
$W_2-O_3$
must take at most
$5-z$
units hence
$0 \le (5-z) \le 5 \rightarrow 0 \le z \le 5$
.

By considering the warehouses, we have
$x+y+z=12 \rightarrow z=12-x-y$
and
$(8-x)+(7-y)+(5-z)=8 \rightarrow x+y+z=12$
.
We can eliminate a variable from these constraints. Suppose we choose to eliminate hence
$z$
, then from the last, and hence
$0 \le z \le 5$
, we have hence
$x+y \ge 7$
.

Now we can sketch the constraints
$x \le 8, \: y \le 7, 7 \le x+y \le 12$
.

We can test the integer coordinates of point inside the feasible region, or the vertices of the feasible region, if the coordinates are integer points. The cost function, to be minimised, is
$3x+5y+3(12-x-y)+2(8-x)+7(7-y)+1(x+y-7)=94-x-4y$
.
Test each vertex.
$(0,7): \: 94-0-4 \times 7=66$

$(5,7): \: 94-5-4 \times 7=61$

$(8,4): \: 94-8-4 \times 4=70$

$(8,9): \: 94-8-4 \times 0=86$

$(7,0): \: 94-7-4 \times 0=87$

The minimum cost solution is
$(5,7)$
, corresponding to sending 5,7, 3 and 5 units on routes
$W_1-O_1, \: W_1-O_2, \: W_2-O_1$
and
$W_2-O_3$
respectively.