Integer programming

Why it matters

Many business decisions are not "how much" but "yes or no": open this warehouse or not, fund this project or not, assign this nurse to this shift or not. Fractions make no sense for them. Integer programming (IP) adds the rule that some variables must be whole numbers, and binary variables (0 or 1) turn logic such as "if A then B" into constraints a solver understands. Most of the high-value OR work in industry, from airline crew scheduling to supply-chain design, is integer programming.

Integer, binary and mixed models

• Integer variable: x in {0, 1, 2, ...}, for example the number of trucks.
• Binary variable: y in {0, 1}, a yes/no decision.
• Mixed-integer program (MIP): some variables are continuous, some integer.

Why not just solve the LP and round? Because rounding can be infeasible or far from optimal. Take maximize x + y subject to -2x + 2y >= 1 and -8x + 10y <= 13, with integer x, y >= 0. The LP optimum is x = 4, y = 4.5. Rounding y to 4 breaks the first constraint and rounding up to 5 breaks the second; the true integer optimum is x = 1, y = 2. The LP relaxation still helps: its value is an upper bound (for maximization) on the best integer value.

Modelling logic with binary variables

Let x_A, x_B, ... be 1 if a project is chosen and 0 if not.

Fixed costs use a "big-M" link. If a plant produces q units only when it is open (y = 1) and can make at most M units, write q <= M * y. Then the cost F * y + v * q charges the fixed cost F only when the plant is used. Choose M as the real capacity, not a huge number: a too-large M makes the LP relaxation weak and the solver slow.

Worked example: capital budgeting

A company has 12 ($M) to invest in five projects:

A uses software that B builds, so A needs B. C and D compete for the same team, so at most one of them.

maximize   9x_A + 7x_B + 5x_C + 10x_D + 3x_E
subject to 5x_A + 4x_B + 3x_C +  6x_D + 2x_E <= 12   (budget)
           x_A <= x_B                                 (A needs B)
           x_C + x_D <= 1                             (C or D)
           x_A, ..., x_E in {0, 1}

With five binary variables there are only 2^5 = 32 portfolios, so you can check them all. The best is {A, B, C}: cost 12, NPV 21. A greedy rule ("pick the best NPV per dollar first") picks A (1.8 per dollar) but then must also take B, and it can easily miss the optimum on other data. With a budget of 15 the answer changes to {A, B, D} with NPV 26.

How solvers handle integers: branch and bound

Enumeration doubles with every extra binary variable: 50 projects means about 10^15 portfolios. Solvers use branch and bound instead:

1. Solve the LP relaxation (allow fractions). If the answer happens to be integer, you are done.
2. Otherwise pick a fractional variable, say x = 2.4, and branch into two subproblems: one with x <= 2, one with x >= 3.
3. Keep the best integer solution found so far (the incumbent).
4. Bound: any subproblem whose LP value cannot beat the incumbent is pruned without exploring it.

Modern solvers add cutting planes, presolve and heuristics on top, and report a MIP gap: how far the incumbent might be from the best possible value. A gap of 1% is often good enough for a business decision.

In PuLP, a binary variable is one argument away: pulp.LpVariable("x_A", cat="Binary").

Common mistakes

• Rounding an LP answer and calling it optimal (or even feasible).
• Reversing an implication. "A needs B" is x_A <= x_B, not x_B <= x_A.
• Huge big-M values. They cause weak bounds and numerical trouble.
• Too many integer variables. Keep continuous whatever can be continuous; solvers handle those cheaply.
• Waiting for a zero gap on a large model when a 1% gap answers the business question.

Quick recap

• Integer variables model counts; binary variables model yes/no choices and logic.
• Rounding LP answers can fail; the LP relaxation gives a bound.
• Common binary patterns: at most k, exclusion, implication, and big-M fixed costs.
• Solvers use branch and bound and report the MIP gap.

Try it

In the Do tab, write the logic constraints for the capital budgeting model and find the best portfolio by enumeration.