Omis2010 – Lecture 4 Integer Linear Programming
• Linear programming allows us to solve large -scale problems. It gives answers in terms of
• However, there are many situations where we need solutions to problems which are not
allowed to fall in a continuous range
Integer Programming (ILP)
• An integer programming (ILP) in which all variables are required to be integers is called a pure/all
integer programming problem.
• An IP in which only some of the variables are required to be integers is called a mixed integer
• An integer programming problem in which all the variables must be 0 or 1 is called a binary IP or a
0-1 integer program.
MAX: 350 X1+ 300 X2 } profit
S.T.: 1 X1+ 1 X2200 } filters
9X1 + 6 X2≤ 1566 } labour
12 + 16 ≤ 2880 } bolts
X1 X2≥ 0 } non-negativity
X1,nd X2 must be integers } integrality
Integrality conditions are easy to state but make the problem much more difficult (and
sometimes impossible) to solve.
• Original ILP
MAX: 2X1+ 3X 2
S.T.: X + 3X ≤ 8.25
2.5X1+ X ≤28.75
X1, 2 ≥ 0
X1, 2 must be integers
• LP Relaxation
MAX: 2X1+ 3X 2
S.T.: X + 3X ≤ 8.25
2.5X1+ X ≤28.75 Omis2010 – Lecture 4 Integer Linear Programming
X1, 2 ≥ 0
When solving an LP relaxation, sometimes you “get lucky” and obtain an integer feasible solution.
But what if you don’t?
Integer Feasible vs. LP Feasible Region
• The optimal solution to an LP relaxation of an ILP problem gives us a bound on the optimal
objective function value.
• For maximization problems, the optimal relaxed objective function values is an upper bound on
the optimal integer value.
• For minimization problems, the optimal relaxed objective function values is a lower bound on the
optimal integer value.
• It is tempting to simply round a fractional solution to the closest integer solution.
• In general, this does not work reliably:
– The rounded solution may be infeasible. Omis2010 – Lecture 4 Integer Linear Programming
– The rounded solution may be suboptimal.
How Rounding Down Can Result in an Infeasible Solution
Example: All-Integer LP
• Consider the following all -integer linear program:
Max 3x1+ 2x 2
s.t. 3x 1 x <29
x1+ 3x 2 7
-x1+ x 2 1
x1, 2 > 0 and integer
• LP Relaxation Solving the problem as a linear program ignoring the integer constraints, the
optimal solution to the linear program gives fractional values for both x and x . From the graph
we see that the optimal solution to the linear program is: x = 2.5, x = 1.5, z = 10.5
1 2 Omis2010 – Lecture 4 Integer Linear Programming
If we round up the fractional solutio1 (x =
2.5, x = 1.5) to the LP relaxation problem,
we get x1= 3 and x2= 2. From the graph we
see that this point lies outside the feasible
region, making this solution infeasible.
By rounding the optimal solution down to
x = 2, x = 1, we see that this solution
indeed is an integer solution within the
feasible region, and substituting in the
objective function, it gives z = 8.
We have found a feasible a ll-integer
solution, but have we found the OPTIMAL
The answer is NO! The optimal solution is 1 = 3 and 2 = 0 giving z = 9, as evidenced in the next slide.
• Complete Enumeration of Feasible ILP Solutions
There are eight feasible integer solutions to this problem:
x1 x2 z
1. 0 0 0
2. 1 0 3
3. 2 0 6
4. 3 0 9 ← optimal solution
5. 0 1 2
6. 1 1 5
7. 2 1 8
8. 1 2 7 Omis2010 – Lecture 4 Integer Linear Programming
• The Branch-and-Bound (B&B) algorithm can be used to solve ILP problems.
• Requires the solution of a series of LP problems termed “candidate problems”.
• Theoretically, this can solve any ILP.
• Practically, it often takes LOTS of computational effort (and time).
• Because B&B can take so long, most ILP packages allow you to specify a suboptimality
• This allows you to stop once an integer solution is found that is within some % of the globa l
• Bounds obtained from LP relaxations are helpful here.
• LP relaxation has an optimal obj. value of $64,306.
• 95% of $64,306 is $61,090.
• Thus, an integer solution with obj. value of $61,090 or better must be within 5% of
the optimal solution.
An Employee Scheduling Problem: Air-Express
Defining the Decision Variables
X1 = the number of workers assigned to shift 1
X2 = the number of workers assigned to shift 2
X3 = the number of workers assigned to shift 3
X4 = the number of workers assigned to shift 4
X5 = the number of workers assigned to shift 5 Omis2010 – Lecture 4 Integer Linear Programming
X6 = the number of workers assigned to shift 6
X7 = the number of workers assigned to shift 7