#integer linear programming

We showed how to load boxes to a set of lorries in our previous article Graphical Method for Integer Linear Programming (ILP), in which we cannot rent a partial lorry (7.5 lorries). It has to be a whole lorry (7 or 8 lorries), leaving the empty space unoccupied.

The variables take only integer values, instead of a solid area of feasible region. The optimal solution is always on the edge of the feasible region, however, rounding off the floating point solution can lead to infeasible solution.

So, the integer solution may not lie on an extreme point of continuous feasible region, and LP cannot be used. From the graphic, the collection of dots/points indicate the new feasible solutions.

Types of Integer Programming

According to the nature of the variables, we can distinguish three types of IP models, which are Pure IP, Mixed IP and Binary IP.

Pure IP requires that all decision variables have integer values in the final solution.

Mixed IP requires some, not all, of the decision variables to have integer solutions.

Binary IP, also 0-1 IP, involves problems in which the variables are restricted to be either 0 or 1, such as state or mode decisions, yes/no decisions or logical decisions.

Example:

Unit commitment problem with the state or mode decisions. A particular stage 0-1 binary variables (boolean), i.e. on or off.

Planning of investments as a yes/no decisions. It takes a value 1 to invest in a warehouse (yes) and 0 to ignore it (no).

A given tax break is only applicable (true/false) if a certain investment is made. This is a logical decisions, the logic constraints between different decision variables, i.e. AND, OR, NOT, IMPLY, ... etc.

The solution complexity increases with the number of possible combinations of integer variables (combinatorial problem). Even the fastest computer can take excessively long time to solve a big integer programming problem.

Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.

There are some methods for solving ILP problems, such as:

Rounding off a non-integer solution

Cutting Plane method

Branch and Bound method

The addictive algorithm for 0-1 IP

However, in reality, we cannot rent a 0.5 lorry.

It has to be a whole lorry, leaving the empty space unoccupied.

So, based on our graph, we will have to go for the 10 lorries of 30 boxes with the cost of RM 4000.

If we really think so, we are leaving money on the table!

Any point under the shaded area is the possible solution.

Luckily, not many are integer coordinates, i.e. a pair of integer numbers.

In order to find the coordinates, simply insert an integer value for either nLorry30 or nLorry40.

For example, we can find the value of nLorry30 when nLorry40 = 0 by inserting zero in place of nLorry40 and solving the equation as follows:

Capacity: 30*nLorry30 + 40*(0) = 300 30*nLorry30 + 0 = 300 30*nLorry30 = 300 nLorry30 = 300/30 = 10

So the coordinates of the second point are nTruck40 = 0 and nTruck30 = 10 which can be written as (10, 0).

nTruck30 nTruck40 -0.67 8 0 7.5 0.67 7 1 6.75 2 6 3 5.25 3.33 5 4 4.5 4.67 4 5 3.75 6 3 7 2.25 7.33 2 8 1.5 8.67 1 10 0

Only three integer coordinates, i.e. (10,0), (2,6) and (6,3)

We can now calculate the cost for these three points, using the straight parallel line, by substituting in values for the objective.

Cost = 400 * nLorry30 + 500 * nLorry40

For point 0 (0, 0):

Cost = 400(0) + 500(0) = RM 0

For point (2, 6):

Cost = 400(2) + 500(6) = RM 3800

For point (6, 3):

Cost = 400(6) + 500(3) = RM 3900

We actually need 6 lorries of 40 boxes (240 boxes @ RM 3000) and 2 lorries with 30 seats (60 boxes @ RM 800).

So that we can load all the boxes and pay only RM 3800.

It is slightly higher cost, extra RM 50 from previous solution, but now we satisfy the real world constraint that we cannot rent a partial lorry.