Integer programming studies optimization problems where some or all decision variables must take integer values. This cheat sheet helps students move from a linear programming model to a correct integer programming formulation and a branch-and-bound solution process. It is especially useful for scheduling, routing, assignment, production planning, and yes-or-no selection models.
The goal is to understand both how to write the model and how the algorithm proves optimality.
Key Facts
- A pure integer program has the form maximize or minimize z = c^T x subject to Ax <= b, x >= 0, and x_i integer for every decision variable.
- A mixed-integer linear program allows only some variables to be integer, so x_i integer for i in I and x_j continuous for j not in I.
- A binary variable must satisfy x_i in {0, 1}, making it useful for yes-or-no decisions such as choose, open, assign, or schedule.
- The LP relaxation is formed by replacing x_i integer with x_i continuous, often giving an optimistic bound on the integer optimum.
- For a maximization integer program, the LP relaxation value at a node is an upper bound on any integer solution inside that node.
- For a minimization integer program, the LP relaxation value at a node is a lower bound on any integer solution inside that node.
- A branch on a fractional variable x_k = v creates two child nodes: x_k <= floor(v) and x_k >= ceiling(v).
- A common relative optimality gap is gap = |best bound - incumbent value| / max(1, |incumbent value|).
Vocabulary
- Integer program
- An optimization model in which one or more decision variables are required to take integer values.
- LP relaxation
- The linear programming problem obtained by removing integer restrictions from an integer program.
- Incumbent
- The best feasible integer solution found so far during a branch-and-bound search.
- Branching
- The process of splitting a problem into smaller subproblems by adding constraints that exclude a fractional LP solution.
- Bounding
- The use of an LP relaxation or other estimate to limit how good any solution in a subproblem can be.
- Pruning
- The removal of a search node because it is infeasible, already integer feasible, or unable to improve the incumbent.
Common Mistakes to Avoid
- Treating the LP relaxation solution as automatically valid is wrong because fractional values may violate the integer restrictions.
- Using the wrong bound direction is wrong because maximization LP relaxations give upper bounds, while minimization LP relaxations give lower bounds.
- Branching with x <= v and x >= v is wrong when v is fractional because it does not force integrality; use x <= floor(v) and x >= ceiling(v).
- Pruning a node before checking feasibility and bound logic is wrong because a node can only be discarded for a valid reason such as infeasibility, integrality, or no possible improvement.
- Ignoring binary variable meanings is wrong because x = 0 and x = 1 must be tied to clear decisions, otherwise constraints may not model the real situation.
Practice Questions
- 1 A maximization integer program has an LP relaxation value of 47.8 at a node, and the best incumbent value is 42. Can this node be pruned by bound? Explain.
- 2 At a branch-and-bound node, the LP solution has x_3 = 6.25. Write the two branching constraints that would be used for x_3.
- 3 For a minimization integer program, the incumbent value is 120 and an open node has LP relaxation value 128. Can the node be pruned by bound? Explain.
- 4 Why can solving the LP relaxation help branch and bound even though the relaxation may give a fractional solution?
Understanding Integer Programming and Branch and Bound
The hardest part of integer programming is often choosing variables that match the real decision. A binary variable can represent whether a warehouse opens, whether a worker receives a shift, or whether a route is used. Its meaning must be written clearly before constraints are built.
Then each constraint should describe a real limit or rule. A capacity constraint links selected jobs to available time. A linking constraint prevents production unless a machine is opened.
A coverage constraint ensures every customer, task, or time period is served. Small wording errors matter.
If a decision is optional, an equality can accidentally force it. If a decision must happen exactly once, an inequality may allow missing or repeated assignments.
The linear programming relaxation is useful because it shows what would be possible if indivisible choices could be split. A model might suggest opening two point four facilities or assigning zero point six of a person to a job. These values are not valid decisions, but they reveal the best value available without the integer restriction.
The difference between this relaxed value and a valid integer solution is caused by the shape of the feasible region. Integer points are scattered within the continuous region.
Some models have a tight relaxation, meaning the relaxed solution is nearly integer. Others have a weak relaxation, meaning the relaxed answer is far too optimistic for a maximization problem or far too low for a minimization problem.
Branch and bound gradually removes this uncertainty. At each node, the solver handles a smaller version of the original problem with extra restrictions. When a relaxed solution contains a fractional variable, branching separates the possible integer values into two cases.
Every integer solution remains in one of those cases, so no valid answer is lost. A node can be pruned for several reasons. It can be infeasible, meaning its added restrictions cannot be satisfied.
Its relaxation can already be integer, producing a candidate solution. Or its bound can be worse than the best known integer solution, often called the incumbent. Pruning is what prevents a solver from checking every possible combination.
Students should keep maximization and minimization directions straight. In maximization, a node bound is a ceiling on what that node could still achieve. In minimization, it is a floor.
The incumbent is always a feasible integer value, while the best bound reflects the most promising remaining unexplored nodes. Together they measure how much uncertainty remains. A small relative gap means the current solution is close to provably optimal, even if the search has not finished.
This matters in real planning because an exact optimum may take much longer to prove than to find a very good solution. When checking solver output, inspect the reported status, incumbent, bound, gap, and any variables with unexpected values. A mathematically optimal answer can still be useless if the model omitted an important real-world rule.