flowchart LR
A[LP feasible polygon] --> B[Continuous optimum]
A --> C[Lattice of integer points]
C --> D[IP feasible set]
D --> E[Integer optimum]
B -.rounding.-> F[Possibly infeasible or suboptimal]
24 Integer Programming
24.1 What Integer Programming Is
Integer programming (IP) is linear programming with the extra requirement that some or all decision variables take integer values. The restriction is needed whenever a decision is inherently discrete: how many trucks to buy, whether to open a warehouse, which projects to fund, which product codes to assign to which workers. Land and Doig (1960) introduced branch-and-bound; Gomory (1958) introduced cutting planes; together they form the algorithmic backbone of modern mixed-integer solvers.
NoteWhen IP is the right tool
IP applies when the decision is inherently indivisible (a yes/no investment, a count of units, an assignment) and the LP relaxation would produce fractional values that cannot be implemented. The trade-off is computational: IP is NP-hard in general, so small problems solve in milliseconds and large problems may need hours or specialised solvers.
24.2 Why Not Just Round
A common first thought is to solve the LP relaxation (dropping the integrality requirement) and then round the fractional optimum. Rounding is dangerous for two reasons: the rounded point can be infeasible (it violates a constraint), or it can be feasible but far from the true integer optimum.
The LP relaxation suggests fractional decisions whose naive rounding either breaks the capacity constraint or lands on a worse integer point. Solving the IP directly finds the true best integer corner, which differs from any rounding of the LP answer.
24.3 Pure, Binary, and Mixed Integer
Three flavours are distinguished by which variables carry the integrality restriction. A pure IP restricts every variable to integers; a 0/1 (binary) IP restricts variables to \(\{0, 1\}\) and models yes/no decisions; a mixed-integer program (MIP) mixes continuous and integer variables in the same model (for example, binary open/close decisions with continuous shipment quantities in §8). Most business problems are MIPs; lpSolve::lp accepts int.vec for selected integer variables and all.bin = TRUE for fully binary problems.
TipSizing the difficulty
The LP relaxation gives an optimistic bound on the IP objective (for max problems). If the LP relaxation value is not attractive, the integer answer cannot be better, so the project can be dropped early. This relaxation bound also drives branch-and-bound pruning in §4.
24.4 Branch-and-Bound
Branch-and-bound builds a search tree whose root is the LP relaxation. At each node it picks a fractional variable, branches into two child nodes (one with the variable rounded down, one with it rounded up), and solves the LP relaxation at each child. A node is pruned when it becomes infeasible, when its LP bound is worse than the best integer solution found so far (the incumbent), or when its LP solution happens to be integer-feasible (in which case it updates the incumbent). Cutting planes (Gomory 1958) tighten the relaxation without changing the integer feasible set and usually speed up convergence. Modern solvers such as CBC, Gurobi, and CPLEX combine branch-and-bound with cuts, heuristics, and preprocessing.
24.5 Solving with lpSolve
lpSolve::lp signals integer variables via int.vec (zero-based or by position) or all.int = TRUE for a pure IP, and all.bin = TRUE for a 0/1 IP. All other arguments are the same as in Chapter 23.
all.int = TRUE enforces integrality on every variable. For a mixed-integer formulation, use int.vec = c(1, 3) to mark only the first and third variables as integer.
24.6 0/1 Knapsack
The knapsack problem picks a subset of items to maximise total value without exceeding a capacity. With \(n\) items of weights \(w_j\) and values \(v_j\) and a binary choice \(x_j \in \{0, 1\}\):
\[ \max_{x} \; \sum_j v_j x_j \quad \text{s.t.} \quad \sum_j w_j x_j \le W, \; x_j \in \{0, 1\}. \]
The selected subset respects the capacity and maximises total value. all.bin = TRUE converts every variable to \(\{0, 1\}\) so no explicit \(0 \le x_j \le 1\) bounds need to be written.
24.7 Assignment Problem
Assigning \(n\) workers to \(n\) jobs at costs \(c_{ij}\) is the classic balanced assignment problem. Decision variables \(x_{ij} \in \{0, 1\}\) mean “worker \(i\) does job \(j\)”; each worker does one job (\(\sum_j x_{ij} = 1\)) and each job is done by one worker (\(\sum_i x_{ij} = 1\)). Minimise total cost.
lp.assign is a thin wrapper that avoids building the 16-variable, 8-constraint LP by hand. The solution matrix is a permutation: each row and each column contains exactly one 1, identifying the optimal worker-to-job matching.
24.8 Facility Location
A retailer chooses which of \(p\) candidate warehouses to open (binary \(y_i \in \{0, 1\}\), with fixed cost \(f_i\)) and how much to ship from open warehouses to stores (continuous \(x_{ij} \ge 0\), with unit cost \(c_{ij}\)). The linking constraint \(x_{ij} \le M y_i\) forbids shipping from a closed warehouse. This is the canonical mixed-integer formulation.
Only a subset of warehouses opens, and every store’s demand is met from the open set. The solver made the open/close decision and the shipment plan simultaneously, which is the value of MIP over solving each piece in isolation.
24.9 Capital Budgeting
A firm picks a subset of candidate projects with net present values \(v_j\) and year-one costs \(c_j\) subject to a budget \(B\). Binary \(x_j \in \{0, 1\}\) selects each project; the formulation is a knapsack with NPV as value and year-one cost as weight. Multi-period budgets are modelled by adding one constraint per year.
The selected portfolio maximises NPV while respecting both the year-one and year-two budgets. Adding further constraints (must-pick pairs, precedence, mutually exclusive projects) follows the logical-constraints recipe in §10.
24.10 Logical Constraints
Many business rules are “if-then” or “either-or” statements that must be linearised before the solver can use them. Two common patterns.
- If-then: “if project \(i\) is chosen then project \(j\) must be chosen” translates to \(x_i \le x_j\) with \(x_i, x_j \in \{0, 1\}\).
- Either-or: “either constraint 1 or constraint 2 must hold” translates via big-M and a binary switch. For constraints \(a_1' x \le b_1\) or \(a_2' x \le b_2\), introduce \(z \in \{0, 1\}\) and write \(a_1' x \le b_1 + M z\) and \(a_2' x \le b_2 + M(1 - z)\) for a large \(M\).
The binary result respects both the budget and the implication rule. Constraint writing style matters: every business rule that sounds like “must”, “only if”, “at most two of”, or “exactly one of” maps to a small linear pattern that is easy to verify row by row.
24.11 Computational Complexity and Practical Tips
IP is NP-hard in general, which means solve time can grow exponentially in the number of binary variables. Well-posed business problems with up to a few thousand binaries are usually tractable; beyond that, solver choice and model tightness start to matter. Timing the LP relaxation against the full IP on growing problem sizes is a cheap way to feel the gap.
For small knapsacks the IP and LP solve in comparable time. The gap widens as \(n\) grows; real industrial MIPs routinely rely on presolve, cuts, and warm-starts to stay tractable. Williams (2013) and Wolsey (1998) are the standard references for tightening formulations so the branch-and-bound tree stays shallow.
24.12 Summary
A complete IP report names the decision variables with their types (continuous, integer, binary), writes the objective and every constraint with units, states the solver and any non-default options, reports the optimal decision vector and objective value, flags which constraints are binding, records the LP-relaxation bound (to show the integrality gap), and explains any logical rules in business terms. Nemhauser and Wolsey (1988) and Wolsey (1998) are the standard methodological references; Williams (2013) remains the most practical guide for formulation.
| Concept | Description |
|---|---|
| Foundations | |
| IP problem definition | LP plus integrality restrictions on some or all variables |
| Rounding pitfall | Rounding the LP optimum can be infeasible or suboptimal |
| Pure, binary, mixed | Pure IP, 0/1 IP, and mixed-integer MIP differ in variable scope |
| Solution Methods | |
| Branch-and-bound | Search tree with LP-relaxation bounds for pruning |
| lpSolve int.vec and all.bin | int.vec marks integer variables; all.bin makes all variables binary |
| Classic Formulations | |
| 0/1 knapsack | Pick items to maximise value under a capacity constraint |
| Assignment problem | Balanced binary matching of workers to jobs |
| Facility location (MIP) | Binary open/close with continuous shipments and big-M linking |
| Capital budgeting | Pick projects to maximise NPV under budget constraints |
| Modelling Tools | |
| If-then via x_i <= x_j | Implication encoded as x_i <= x_j on binary variables |
| Either-or via big-M | Disjunction encoded with a binary switch z and big-M slack |
| NP-hard complexity caveat | Worst-case time grows exponentially; tighten formulations first |
| Delivery | |
| Formulation checklist | Variables, objective, constraints, bounds, types, sizes |
| Reporting checklist | Decisions, plan, bounds, binding, LP gap, logical rules |