#integer linear programming

[mooptcom]

Integer Programming (IP) Intro & 3 Types

Integer Linear Programming (ILP) is required to solve optimization problems with integer values as the solution.

Integer Linear Programming is a subset of Linear Programming (LP). It has all the characteristics of an LP, an attempt to find a maximum or minimum solution to a function given certain constraints, except for some or all of the variables to the LP solution must be restricted to integers.

There are many events we need to solve the real world optimization problems with Integer Linear Programming, instead of Linear Programming. It doesn't make sense to use a continuous variable to represent the number of airplanes to produce because there is no point in manufacturing a partial airplane. The production of large indivisible items is one of the use case of ILP.

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

which we will explain in details in the coming lessons.

[mooptcom]

Graphical Method for Integer Linear Programming (ILP)

Revisiting the lorry loading puzzle as an integrer linear programming problem with the graphical method.

Consider the following problem from Linear Programming with Minizinc Introduction:

300 boxes need to be loaded and shipped to a supermarket from a warehouse. We may rent lorries that can accommodate 30 boxes and 40 boxes, costing us RM 400 and RM 500 respectively. How many lorries of each type to load all boxes while minimizing the cost?

Our goal is to minimize the cost of loading these boxes by selecting the right amount of the different lorries.

Previously from Linear Programming with Graphical Method - Part 1, we concluded that with 7.5 lorries of 40 boxes (total 300 boxes), we can load all the boxes and pay only RM 3750 (7.5 x RM 500).

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.

It is actually a more specific case of linear programming problem, called Integer Linear Programming (ILP).