Ann-Brith Strömberg February 5, 2002

Integer linear programs

Suppose that we have a linear program,

[LP] z^{LP} = min {c^{T} x : Ax ≥ b, x ≥ 0} ,

where A is an m × n-matrix, c is an n-vector, b is an m-vector, and x is an n-vector of variables. Adding the restriction that the variables must take integer values we get an integer linear program,

[IP] z^{IP} = min {c^{T} x : Ax ≥ b, x ≥ 0, x integer} .

If all variables are restricted to the values 0 or 1, we have a binary linear program,

[BP] z^{BP} = min {c^{T} x : Ax ≥ b, x ∈ {0, 1}} .

Since integer linear programs look very much like linear programs, linear programming theory and practice are fundamental in the understanding and solution of integer linear programs. However, the simple idea of “rounding” the values of a solution to [LP] is almost never sufficient to find an optimal, or even good or just feasible, solution to [IP]. Consider the following [IP]:

min −1.00x_{1} −0.64x_{2}
s.t.  50x_{1} +31x_{2} ≤ 250
3x_{1}  −2x_{2} ≥ −4
x_{1}, x_{2} ≥ 0 and integer

The linear programming solution x_{LP} = (\frac{376}{193}, \frac{950}{193}) ≈ (1.95, 4.92) is far from the optimal integer solution x_{IP} = (5, 0), and neither rounding x_{LP} to (2, 5) nor truncating it to (1, 4) is even feasible. The feasible solution x = (2, 4), that is the “closest” one to x_{LP}, has objective value −4.56, which is far from optimal. The objective values at x_{LP} and x_{IP} are −\frac{984}{193} ≈ −5.10 and −5, respectively.

Considering a binary linear program, an optimal solution to the corresponding linear program (where the constraints x ∈ \{0, 1\} are relaxed to x ∈ [0, 1]) may very well be (\frac{1}{2}, …, \frac{1}{2}), which tells absolutely nothing about an optimal solution that we did not know before.

A general procedure for solving integer linear programs to optimality is the branch–and–bound concept.

Branch–and–bound–algorithms

Branch–and–bound (B&B) is a general principle for finding optimal solutions to integer linear programs. It can be adapted to different types of models and it may also be combined with other (e.g., non-optimizing) algorithms. (Synonyms in the literature are, e.g., tree search and implicit enumeration.) Consider the integer linear program

[IP]  z^{∗} = min c^{T} x

s.t. x ∈ X, where, e.g., X = {x ∈ ℜ^{n} | Ax ≥ b, x ≥ 0, x integer}.

The basic idea of B&B is to enumerate all feasible solutions through the successive partition of X into a family of subsets. The enumeration is organized in a tree, using graph search, and is made implicit by utilizing estimates of z^{∗}; these estimates are received from solutions to relaxations of [IP]. B&B algorithms have an exponential worst case–complexity, since it may occur that all feasible solutions are explicitly enumerated.

Example: Partition of a set of binary variables via branching: X = {{0, 1}^{3} | x_{2} + x_{3} ≤ 1}. (In each branching one of the variables is fixed to 0 in one branch and to 1 in the other.)

[figure: x_{1} =0; x_{1} =1; x_{2} =0; x_{2} =1; x_{3} =0; x_{3} =1; x_{3} =0; x_{3} =1; x_{3} =0; x_{2} =0; x_{2} =1; x_{2} =0]

Four concepts must be specificed to define a complete B&B–algorithm:

• Relaxation: a simplification of [IP] through the removal of constraints.

– Purpose: to receive simple (i.e., polynomially solvable) subproblems, and optimistic estimates of z^{∗}.

• Branching strategy: rules for partitioning of a subset of X.

– Purpose: to exclude the optimal solution to a relaxation of [IP] if this solution is not feasible in [IP]; to shrink the subsets until only feasible solutions are left.

• Tree search strategy: defines the order in which the nodes in the B&B–tree are created and searched.

– Purpose: to quickly find good feasible solutions; to restrict the size of the tree.

• Criteria for cutting off nodes: rules to decide whether or not a subset of X should be partitioned further.

– Purpose: to avoid the search through branches that cannot contain a candidate to an optimal solution.

• Relaxation

A relaxation of [IP] consists of removing som of its constrants, and by that actually enlarge the feasible set, or, letting X^{R} ⊃ X,

[R-IP]  z^{R} = min c^{T} x

s.t. x ∈ X^{R}.

However, the main purpose of relaxation is to receive a more easily solveable so called subproblem. Examples of relaxations of [IP] are

– removal of integrality requirements ⇒ linear continuous subproblems

– removal of complicating continuous constraints ⇒ simpler subproblems

– Lagrangean relaxation of complicating continuous constraints ⇒ simpler subproblems and possibility to get better optimistic estimates of z^{∗}

If an optimal solution to a relaxation of [IP] problem is not feasible in the original [IP], then we try to fulfil the relaxed constraints through a branching in the B&B–tree.

The optimal value of a subproblem is an optimistic estimate of the value of any feasible solution that can be achieved in the corresponding branch in the tree, since each branching brings more restrictions.

The simplification of [IP] through the relaxation may not be too severe, because then one would probably have to make very many branchings to receive solutions to the relaxations that are feasible also in the original [IP], i.e., the tree would grow too large and deep.

• Branching strategy

A branching is used to strengthen a relaxation. The branching should correspond to a partition of the present subset of X^{R}, such that each feasible solution to [IP] can be found in exactly one branch of the tree (a proper partition).

The branching must imply that the optimal solution to the subproblem, which is infeasible in the original problem, is cut off; however, no solution that is feasible in the original problem is allowed to be cut off.

• Tree search strategy

The B&B-tree is not given in advance, but it is created during the execution of the algorithm. To construct the tree and search through its nodes, graph search is used.

[figure: root; created; not created; visited; not visited; searched; not searched; cut off]

Branching priority: indicates whether the subsequent nodes in the tree are to be created simultaneously or not, and the order in which they are created.

– Deep–first–order: only one of the successors of each node is created.

– Breadth–first–order: all the successors of a node are created simultaneously.

Visiting priority: indicates which of the active (i.e., created but not visited nor searched) nodes that is no be visited next. Hybrids exist, but mainly the following two are used:

– Deep–first–order (for both branching and visist): Yields quickly feasible solutions; deep and narrow trees.

– Best–first–order: choose the active node that corresponds to the currently best optimistic estimate of z^{∗}. This is the branch most likely to contain an optimal solution. Demands large memory; yields the smallest tree.

• Criteria for cutting off nodes

If the solution x^{P} to a relaxed problem is not feasible in [IP], but has an objective value z^{P} that is lower (for a minimization problem) than the objective value \overline{z} (pessimistic estimate) for the best known feasible solution to [IP], then the node P may not be cut off.

Cutting rules: cut off a node P in the B&B–tree if the corresponding subproblem

– contains no feasible solution,

– has an optimal solution that is feasible in the original [IP] ⇒ x^{P} is a a candidate for an optimal solution (a pessimistic estimate), or

– has an optimal objective value, z^{P} ≥ \overline{z}, where \overline{z} is the objective value of the best known feasible solution to [IP].

For none of these cases a feasible solution to [IP], having a lower objective value (for a minimization problem) than the best known (pessimistic estimate), can be found after a further branching at node P.

To find pessimistic estimates of z^{∗} (corresponding to feasible solutions to [IP]) heuristics are often used.

Solve the integer linear program below using the Branch & Bound–algorithm

max z = 5x_{1} + 3x_{2}
då 2x_{1} − x_{2} ≥ 2 (1)
−x_{1} + 3x_{2} ≥ 3  (2)
5x_{1} + 6x_{2} ≤ 60  (3)
x_{1}, x_{2} ≥ 0, integer

[figure: (1); (2); (3); x_{1}; x_{2}]