Integer Programming
This week we study how to solve general integer linear programs. While there are many tools and tricks out there to solve integer pro- grams, we will concentrate on the branch and bound framework.
7.1 Introduction to integer programs
Generally speaking an integer linear program has the form
minimize subject to
Its linear relaxation is minimize
subject to
x ∈ Z n+ c · x
Ax ≥ b x ∈ R n+
Both program optimize the same objective function, but the feasible region of the integer program is
S = x ∈ Zn+ : Ax ≥ b while the feasible region of its linear relaxation is
X=x∈Rn+ :Ax≥b.
Since S ⊆ X, it follows that the value of the integer program is great than or equal to the value of its relaxation.
When trying to solve an integer program, we can always solve its relaxation first. If the optimal solution of the relaxation hap- pens to be integral, then we are done. If the optimal solution of the relaxation is fractional, then we only learn that the value of the op- timal integral solution is lowerbounded by the cost of the optimal fractional solution, in which case more work needs to be done.
7.2 The branch and bound framework
A branching algorithm is a simple divide and conquer algorithm that recursively breaks down the problem into smaller subprob-
In this example, the feasible region of the linear relaxation is denoted in gray. Integer solution are denoted with a dot and integer feasible solution with a circled dot .
© Copyright 2021 Julián Mestre.
This work is licensed under a Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License.
week 7 – integer programming
discrete optimization 2
lems. For example, suppose S ⊆ {0, 1}n and we would like to solve z = min {c · x : x ∈ S}
WecanselectavariablexjanddivideSintoS1 =x∈S:xj=0 and S2 = x ∈ S : xj = 1. If we can solve each of the subproblems zi =min{c·x:x∈Si},thenzisthesmallestofz1 andz2.
In general, if we have a decomposition S = S1 ∪···∪Sk, and we can compute zi = min{c·x : x ∈ Si} then
z = minzi i
Of course, the subproblems are only marginally easier to solve. In order to compute zi we need to further decompose the subprob- lems. Obviously, this leads to exponential running time. Solving an integer linear program is NP-hard, so we should not expect this scheme to run in polynomial time. The best we can do is to try to contain the exponential growth as much as possible. This is where the bounding in branch and bound comes into play.
Imagine that we could upperbound and lowerbound the value
of each subproblem in the decomposition. In other words, suppose that for a decomposition S = S1 ∪ · · · ∪ Sk we could compute (zi, z ̄i) such that
zi ≤min{c·x:x∈Si}≤z ̄i.
If we cannot find a upperbound for subproblem Si then we set z ̄i = ∞; if the problem happens to be infeasible (Si = ∅) and we can detect this fact then we set zi = ∞. It is easy to see that if we definez=minizi andz ̄=miniz ̄i weget
z ≤ z ≤ z ̄
Once this information is computed, we can prune some of the
subproblems in the decomposition using the following basic rules: 1. Prune by optimality (zi = z ̄i): If we find the value of the sub-
problem then there is no point in further decomposing Si.
2. Prune by infeasibility (zi = ∞): If Si = ∅ then there is no point
in further decomposing Si.
3. Prune by bound (zi ≥ z ̄): If we have already found a solution with cost less than zi then there is no point in further decompos- ing Si.
7.3 Branch and bound with linear programming
Notice that the branch and bound framework as described in the previous section can be run in conjunction with any method for computing upper and lower bounds for the value of the subprob- lems.
Linear programming is well suited for computing lower bounds: We can solve the relaxation of the integer problem associated with
Suppose S ⊆ {0, 1}2 then the search tree where we decompose S based on the values of each binary variable, looks as follows
x2=0 x2=1 S3 S4
x2=0 x2=1 S5 S6
week 7 – integer programming
discrete optimization 3
the subproblem we are to solve. For computing upper bounds, we typically resort to heuristics, or simply hope that the linear relaxation of a subproblem returns an integral solution.
Even if we decide to use linear programming as our main upper- bounding and lowerbounding tool, there are many aspects of the branch and bound framework that need further specification. At a minimum we should decide how to:
1. Choose the subproblem to decompose. A common strategy is
to decompose the subproblems in a depth-first fashion. The obvious benefit is that the number of subproblems we must store is at most the height of the search tree.
We can also use a breadth-first strategy, but this will quickly generate too many problems to store in memory. However, there is a trade-off here: Breadth usually leads to tighter upper and lower bounds, which can translate into more pruning by bound.
2. Decompose subproblems. Suppose the optimal solution of the relaxation is x∗. One popular heuristic is to pick a variable such that xj∗ ∈/ Z and then define
S1 = x∈S:xj ≤⌊xj∗⌋ andS2 = x∈S:xj ≥⌈xj∗⌉
3. Re-optimize subproblems. If we are using Simplex to solve the linear relaxations, a number of tricks can save a great deal of computation. For example, if we optimize the primal problem, when we add a new constraint the current optimal solution will become infeasible in one or more of the subproblems, which will force us to re-optimize from scratch. A better strategy is
to optimize the dual problem. When we add a new constraint
to the primal, we only gain a new variable in the dual, so the previous optimal dual solution is still feasible. There is a version of Simplex that works with the dual, which can exploit this fact thus reducing the number of iterations needed to find the new optimal solution.
Integer program solvers comes with generic strategies for mak- ing this decision, but usually can be overridden with user-defined routines.
7.4 Strengthening linear relaxations
The key to the success of any linear-programming-based branch and bound scheme is a strong linear relaxation. Suppose the dis- crete set of feasible solution S admits two formulations
n n S= x∈Z+ :Ax≥b = x∈Z+ :Ax≥b
nn x∈R+ :Ax≥b ⊂ x∈R+ :Ax≥b .
A tighter relaxation for our example fromthefirstpage.
week 7 – integer programming
discrete optimization 4
Therefore, we expect the relaxation of the first formulation to yield better lowerbounds than the relaxation of the second formulation. In general we would prefer working with the tighter relaxations1.
To make the discussion more concrete, let use apply this idea to a specific optimization. Imagine we wanted to solve the maximum weight bipartite matching problem using branch and bound2. The definition of a matching is that no two edges in the matching share an endpoint. Thus we could use the following formulation
|E| S= x∈Z+ :xe+xf ≤1 ∀e,f∈E:e∩f̸=∅
The relaxation of this formulation, however, is terrible: We can set xe = 21 for all e ∈ E, which is feasible, to get half the cost of all edge weights! A much better formulation is
1 However, there is a trade-off since tighter relaxations some times mean more constraints, which makes solving the relaxation harder.
2 This is not as crazy as it sounds, maybe the real problem we want to solve is a generalization of bipar- tite matching where we have some additional constraints.
|E|
Indeed, consider the following polyhedra
xe≤1 ∀u∈V.
Q= x∈R+ :xe+xf ≤1 ∀e,f∈E:e∩f̸=∅ ,
xe≤1 ∀u∈V.
It is easy to see that P ⊂ Q, so the second formulation leads to a tighter relaxation. In fact, we already know that P is integral when the underlying graph is bipartite. For general graph, however, we need to add more constraints to get a tighter relaxation:
more than |S| many edges inside a set of vertices S—every edge 2
has two endpoints and matching edges do not share endpoints. It is easy to see that for complete graphs3 T ⊂ P.
Good integer program solvers have routines for generating valid inequalities on the fly that are guaranteed to strengthen your re- laxation. There is, however, no replacement for having a strong formulation to begin with.
1. Consider the integer program
T= x∈R|E|: +
x(δ(u)) ≤ 1
∀ u ∈ V ∀ S ⊆ V
The new set of constraints are valid because no matching can have
minimize subject to
x ∈ {0,…,T}n
x(E[S]) ≤ |S| 2
3 In fact, this new formulation is integral for general graphs.
week 7 – integer programming
discrete optimization 5
where f : Z+ → Z+ is an arbitrary function.
Prove that such a program can be reduced to a binary linear
program with nT variables.
2. In the facility location problem we are given a set of point S,
connection costs c : S×S → R+, and facility costs f : S → R+; the
objective is to pick a subject X ⊆ S minimizing
minimize subject to
minimize subject to
minimize subjectto
c(i, X) + i∈S
where c(i, X) = minj∈X c(i, j).
Consider the following formulations for the facility location
Here X represents a set of location where we will open facilities to pro- vide some sort of service to the points. Opening a facility at j carries a cost f(j), and providing service to a point
i from facility j also carries a cost ci,j. Clearly, there is a trade-off: As we open more facility, we increase the total facility cost, while decreasing the client connection cost. The problem
is to find the set of location X that minimizes the combined cost.
i,j c(i, j)xi,j + x ≥1
∀i∈S i xi,j ≤|S|yj ∀j∈S
xi,j, yj ∈{0,1} ∀i,j∈S
i,j c(i, j)xi,j + j fjyj
x ≥1 ∀i∈S
xi,j ≤yj ∀i,j∈S
xi,j , yj ∈{0,1} ∀i,j∈S
Prove that both are valid integer linear formulations. Prove that
the second one leads to a stronger relaxation.
3. LetG = (V,E)beagraphwithedgeweightsw : E → R+. Con- sider the following integer linear formulations for the minimum spanning tree problem.
subjectto xe≥1 ∀∅⊂S⊂V
xe ∈{0,1} ∀e∈E minimize e∈E wexe
e∈E wexe e∈δ(S)
subjectto e∈δ(S)
xe≥1 ∀∅⊂S⊂V xe =|V|−1
xe ∈{0,1} ∀e∈E
xe ≤|S|−1 ∀∅⊂S⊂V e∈E(S)
xe ∈{0,1} ∀e∈E
Prove that all three are valid integer linear formulations. Prove that each provides a stronger relaxation than the previous.
week 7 – integer programming
discrete optimization 6
4. Let G = (V , E) be a complete undirected graph with edge weights w : E → R+. The traveling salesman problem is to find a tour
of V of minimum weight. Consider the following integer linear formulations for the problem.
relaxations are equivalent.
minimize e∈E wexe subjectto xe=2
∀u∈V ∀∅⊂S⊂V ∀e∈E
∀ ∅ ⊂ S ⊂ V ∀e∈E
5. Let G = (V,E) be an undirected graph with edge weights w :
E → R+. Consider the following integer linear formulations for the maximum weight perfect matching problem.
e∈E(S)xe ≤|S|−1
subjectto xe=2
xe ∈{0,1} e∈E wexe
Prove that both are valid integer linear formulations, and that their
maximize e∈E wexe subjectto xe=1
∀ odd S ⊆ V ∀e∈E
maximize e∈E wexe subjectto xe=1
Prove that both are valid integer linear formulations. Prove that the second one leads to a stronger relaxation than the previous for general graphs.
week 7 – integer programming
discrete optimization 7
Solutions of selected exercises
1. For each i ∈ {1,…,n} and j ∈ {1,…T}, we introduce a new variables yji ∈ {0, 1}. The meaning that we would like to assign to these variables is that xi = k if and only if yji = 1 for j = 1,…,k and yji = 0 for j = k+1,…,T. Therefore, we need to enforce that onlyaprefixofthevariablesy1i,…,yTi aresetto1.Wecanachieve this with the following constraints
yj ≤ yj−1 for all i = 1,…,n and j = 1,…,T. ii
Finally, we replace every occurrence of xi with Tj=1 yji in the constraints and redefine the objective function as
f(0) + (f(j) − f(j − 1)) yji.
A solution x is feasible to the original program if and only if the corresponding y solution is feasible to the second program and their cost is the same.
2. In both formulations xi,j captures to the decision of assigning client i to facility j, while yj captures the decision of opening fa- cility j. The first set of constraints in both programs enforces that each client is assigned to at least one facility. The second set of con- straints enforces that if some client is assigned to a facility j then j has to be opened. Finally, the objective equals the cost of assigning clients to facilities plus the cost of opening facilities. In an optimal integral solution each client will be assigned to a single facility, its closest open facility.
Now let us argue that the second formulation is at least as good
as the first. To do that we need to argue that if (x, y) is a feasible
solution for the second program, then it is also feasible for the first
program. This follows from the fact that for a fixed facility j adding
upconstraintsx ≤y fori=1,…,|S|givesus x ≤|S|y . i,j i ii,j j
Finally, let us argue that the second formulation is strictly better than the first. Consider the solution that sets y1 = 1 and xi,1 = 1
for all i = 1, . . . , |S| and zero for the remaining variables. It is easy
to check that this solution is feasible for the first program but not for the second one. Therefore the feasible region of the second program is a strict subset of the first program.