Integer and Mixed-Integer Programming

Ordinary linear or quadratic programming happily hands back a fractional answer — buy 47.3 shares, allocate 12.6% of a portfolio to sector X. Often that's fine, but sometimes it isn't: you can't trade a fraction of a futures contract, and "should we include this bond in the index or not" is a genuine yes/no, not a dial you can set to 0.4. Whenever some variables must be whole numbers — counts, or on/off decisions — the smooth machinery of continuous optimization stops directly applying, because the feasible region is now a scattered cloud of discrete points rather than a solid, continuous shape.

An analogy: rounding a recipe vs. genuinely limited ingredients

If a recipe calls for 2.3 eggs, you just round to 2 and adjust the rest slightly — close enough, no real harm done. But if you're deciding which of ten possible ingredients to include at all (each either fully in or fully out, because half-measures don't make sense for that ingredient), you can't just "round" your way to the right combination — the number of possible combinations to check explodes, and a solution that's excellent when you allow fractional inclusion can be wildly different in cost and quality once you force each one to be a hard yes or no. That's the qualitative jump from continuous to integer optimization: it's not a rounding problem, it's a fundamentally different search.

The method, one symbol at a time

A mixed-integer program (MIP) has the same shape as a linear program — minimize $c^T x$ subject to $Ax \leq b$ — but adds the requirement that some subset of variables must be integers: $x_i \in \mathbb{Z}$ for $i$ in some index set, and possibly $x_i \in \{0,1\}$ for pure yes/no decisions. The standard solution method, branch and bound, works by first solving the "relaxation" — the same problem but with the integer requirement dropped, solved instantly by ordinary linear programming. If the relaxed solution happens to already be integer-valued, you're done. If not, pick a fractional variable (say $x_i = 2.6$) and branch: create two sub-problems, one adding the constraint $x_i \leq 2$ and one adding $x_i \geq 3$, splitting the fractional possibility out. Solve each relaxation; if either yields an already-worse objective value than the best integer solution found so far, prune that branch — no need to explore it further, since nothing inside it can beat what you already have. Repeat, building a search tree, until every branch is either solved or pruned.

Worked example 1: a small knapsack-style selection

A desk has $100 to allocate across three trade ideas, each an all-or-nothing bet (fractional positions not allowed for this decision): idea A costs $60, expected profit $50; idea B costs $50, expected profit $45; idea C costs $40, expected profit $30. The LP relaxation (allowing fractional inclusion) would happily take 100% of A and 80% of B, giving relaxed profit $50 + 0.8(45) = 86$ — but that's not a real option here. Checking the actual integer combinations within budget: {A, C} costs $100, profit $80; {B, C} costs $90, profit $75; {A} alone costs $60, profit $50. The best true integer solution is {A, C} with profit $80 — noticeably below the fractional relaxation's optimistic $86, illustrating why rounding the relaxed answer (which might suggest "almost all of A and B") can badly mislead.

Worked example 2: branch and bound sketch

Minimizing cost with one variable relaxed to $x=2.6$ (must be an integer count of futures contracts), branch-and-bound creates two children: "$x\leq2$" and "$x\geq3$." Solving the LP relaxation of the first child gives an achievable cost of 14; the second gives 15. Suppose the current best known integer solution found elsewhere in the tree already achieves a true cost of 14.5. Since the second child's relaxed (best-case) cost of 15 is already worse than 14.5, that entire branch is pruned without ever exploring further — potentially eliminating a huge number of combinations in one comparison. The first branch (relaxed cost 14) is explored further since it could still beat 14.5.

What this means in practice

MIP shows up whenever a portfolio decision is genuinely discrete: lot-sized trading, index-tracking with a cap on the number of names held, cardinality-constrained portfolio construction ("hold at most 30 stocks"), and combinatorial trade-execution scheduling. Modern solvers (CPLEX, Gurobi) handle problems with thousands of integer variables using highly refined branch-and-bound, but runtime can still blow up unpredictably on hard instances — unlike continuous LP or QP, there's no polynomial-time guarantee.