Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 49 ยท Linear and Integer Programming

Integer Programming and Branch and Bound

See why rounding an LP solution fails, how the LP relaxation gives bounds, and how branch and bound proves an integer optimum, with code that prints the tree.

You cannot buy 2.3 delivery vans, hire 4.6 nurses or open half a warehouse. Many decisions are whole numbers, and models with whole-number variables are called integer programs. At first sight they look like linear programs with one extra rule, and a tempting plan is to solve the LP and round the answer. Sometimes that works. Often it gives a plan that breaks a constraint or leaves a lot of value on the table. In this lesson you will see why, and learn branch and bound, the main method that solvers use to find provably optimal integer solutions.

Lattice points inside a feasible region with the LP optimum, the best integer plan and a small branch-and-bound tree
Left: the LP optimum lies between lattice points. Right: branch and bound cuts the region with x โ‰ค 1 and x โ‰ฅ 2 until every branch is solved or pruned.

What you will learn

  • What the LP relaxation is and why it gives an upper bound.
  • Why rounding can fail.
  • How branch and bound branches, bounds and prunes.
  • How to read a solver's "gap" and why tight formulations matter.

Key terms

Integer program (IP): an LP in which some or all variables must be integers; "mixed" if only some.

LP relaxation: the IP with the integer requirement removed; its optimum bounds the IP optimum.

Incumbent: the best integer-feasible solution found so far.

Branching: splitting a problem into two by forcing a fractional variable down or up, such as x โ‰ค 1 or x โ‰ฅ 2.

Pruning: discarding a branch that cannot contain a better solution.

The LP relaxation gives a bound

If you drop the integer requirement of a maximization IP, the set of allowed plans can only grow, so the best value can only increase. Therefore the LP relaxation value is an upper bound on the integer optimum (for minimization it is a lower bound). If the relaxation happens to give integers, you are done. Otherwise the relaxation tells you how good the integer solution could possibly be.

Rounding can fail

Suppose Sunrise Bakery can only bake whole batches, and its limits change to an oven of 15 hours and a baker of 13 hours: maximize 60x + 40y subject to 2x + y โ‰ค 15 and x + 2y โ‰ค 13. The LP relaxation gives x = 17/3 โ‰ˆ 5.67 and y = 11/3 โ‰ˆ 3.67 with profit 486.67. Now try rounding:

  • Round both up to (6, 4): oven use 2ยท6 + 4 = 16 > 15. Infeasible.
  • Round both down to (5, 3): feasible, but profit only 420.
  • Mixed rounding (5, 4) gives 460 and (6, 3) gives 480.

Of the four neighbours, only two are feasible, and which one is best is not obvious without trying them. In larger problems with hundreds of variables, the number of neighbours is astronomical, so rounding is hopeless as a systematic method.

Another example: buying printers

A print shop will buy x large and y small printers. A large printer adds $12 thousand a year of profit, a small one $8 thousand. There are 4 floor bays: x + y โ‰ค 4. The budget is $21 thousand: large printers cost 7 and small ones 4: 7x + 4y โ‰ค 21. (All numbers are invented for the example.)

The LP relaxation gives x = 5/3 โ‰ˆ 1.67 and y = 7/3 โ‰ˆ 2.33 with profit 38.67. Rounding to (2, 2) costs 14 + 8 = 22 > 21: over budget. The best whole-number plans are (1, 3) and (3, 0), both with profit 36. The integer optimum is 2.67 below the relaxation: this is the integrality gap for this problem.

Branch and bound

Branch and bound explores the problem as a tree.

  1. Solve the LP relaxation of the current problem (the root at first). Call its value the node's bound.
  2. If the LP is infeasible, the branch contains no solution: prune it.
  3. If the bound is no better than the incumbent, nothing in this branch can beat what you already have: prune it.
  4. If the LP solution is integer, it is a new incumbent (it beats the old one, since step 3 did not fire): record it.
  5. Otherwise branch. Pick a variable with a fractional value, say x = 1.67. Every integer plan has either x โ‰ค 1 or x โ‰ฅ 2, so create two child problems by adding each of these constraints, and process both.

When no unexplored branch is left, the incumbent is optimal, and the bounds prove it.

For the printer problem the tree looks like this (computed by the program below):

Node Added constraint LP value Decision
root none 38.67 at (1.67, 2.33) branch on x
left x โ‰ค 1 36 at (1, 3) integer: incumbent 36
right x โ‰ฅ 2 38 at (2, 1.75) branch on y
right, down x โ‰ฅ 2, y โ‰ค 1 37.14 at (2.43, 1) branch on x
right, up x โ‰ฅ 2, y โ‰ฅ 2 none infeasible
next x โ‰ค 2 32 at (2, 1) bound 32 โ‰ค 36: pruned
next x โ‰ฅ 3 36 at (3, 0) bound 36 โ‰ค 36: pruned

Seven LPs, and the answer 36 is proven optimal. A full enumeration would have visited every lattice point; for large problems the pruning removes almost all of them.

Python Branch and bound that prints its tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the log from top to bottom. Each indented line is a child of the line above it. Notice that the second pruning rule (bound no better than the incumbent) saves the work of exploring two more subtrees.

Check with a real MILP solver

milp implements a refined version of the same idea (branch and cut, with presolve and heuristics). Use it to confirm the result and to solve the bakery with whole batches:

Python Confirm with milp

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the printers, milp may return (1, 3) or (3, 0): both are optimal.

Seeing the geometry

The picture shows what branching does. Each constraint x โ‰ค 1 or x โ‰ฅ 2 slices off a strip of the feasible region that contains no lattice points between the two cuts, here the strip 1 < x < 2. Each cut removes the fractional LP optimum without removing any integer plan.

Python Lattice points, LP optimum and the integer optimum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why integer programs are hard

LPs can be solved in polynomial time, but general integer programs are NP-hard: no method is known that is guaranteed to be fast on all instances. Each integer variable can double the amount of work in the worst case, as the number of branches grows exponentially with depth. Solvers cope with several devices:

  • Good bounds. Tighter relaxations prune more. Add cutting planes, extra valid inequalities that cut off fractional solutions without removing integer ones (Gomory introduced them in 1958). Combining branching and cuts is called branch and cut.
  • Good incumbents. Heuristics find feasible integer solutions early, so the bound rule prunes more. This is the topic of Chapter 8.
  • Good branching. Choosing which variable to branch on, and which node to explore next, can change run time by orders of magnitude.
  • Tight models. Small big-M values (see the binary-variables lesson) and strong formulations make a huge difference.

Solvers report the gap: (best bound โˆ’ incumbent) รท incumbent. A gap of 0% means the incumbent is proven optimal; a gap of 2% means you are within 2% of the best possible. In practice you often stop at a small gap.

Easy integer problems: when the LP is already integer

Some structures guarantee that every corner of the LP relaxation has integer coordinates, provided the right-hand sides are integers. These include the shortest path, maximum flow, transportation and assignment problems that you will meet in Chapter 4. For them you can simply solve the LP, with no branching at all. Recognizing such structure is a valuable skill.

Common misconceptions

"Round the LP answer and you are done." Rounding may be infeasible or poor, and it never comes with a proof of optimality.

"An integer program is just a bigger LP." The difference between polynomial and exponential worst-case time makes it a different class of problem.

"Branch and bound examines all possible plans." It prunes whole families of plans using bounds, and usually examines a small fraction.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. For a maximization IP, the LP relaxation value is...

    Dropping the integer requirement can only enlarge the set of plans, so the best value cannot decrease.
  2. 2. In the printer example, why does rounding the LP solution (1.67, 2.33) to (2, 2) fail?

    7ยท2 + 4ยท2 = 22 > 21, so the plan breaks the budget constraint.
  3. 3. When is a branch pruned by bound?

    If even the relaxation of the branch cannot beat the incumbent, the branch cannot contain a better integer plan.
  4. 4. A fractional LP value x = 2.43 leads to which two branches?

    Every integer value is either at most 2 or at least 3, so those two constraints cover all integer plans.
  5. 5. A solver stops with a gap of 0%. What does this mean?

    A zero gap means the best bound equals the incumbent, so the incumbent is optimal.

Summary

  • Integer programs restrict variables to whole numbers; the LP relaxation gives an upper bound (for maximization).
  • Rounding can be infeasible or suboptimal and proves nothing.
  • Branch and bound solves LPs on a tree: branch on fractional variables, prune infeasible nodes and nodes whose bound cannot beat the incumbent.
  • Integer programming is NP-hard in general; cuts, good heuristics and tight formulations make solvers effective.
  • Network problems have integer LP corners, which is why Chapter 4 methods are fast.

Next: Chapter 3 Review