Linear Programming (LP) optimises over continuous variables — decisions can be any real number. Mixed-Integer Programming (MIP) extends LP by allowing some variables to be integer (whole numbers: 0, 1, 2, ...) or binary (0 or 1 only). This small change unlocks decision types that LP cannot model: Is a warehouse open or closed? How many machines should run? Which customer is served by which warehouse?
The difficulty is that adding integrality constraints turns polynomial-time LP into NP-hard MIP. The standard exact solution method is branch-and-bound, which recursively splits the problem on fractional variables while pruning subproblems that cannot improve the best known solution. How tightly the LP relaxation bounds the integer optimum — the integrality gap — determines how much branching is needed.
Decision variables: Binary variables for 10 potential warehouse locations (y_i = 1 if warehouse i opens, 0 otherwise) and continuous variables for flows (x_ij = quantity shipped from warehouse i to customer j).
Constraints: Each customer's demand must be met. Flows from warehouse i can only occur if warehouse i is open (written as x_ij ≤ demand_j × y_i). Fixed costs apply if y_i = 1.
Optimisation: Minimise total cost = fixed opening costs + variable transportation costs. The binary variables force the "yes/no" decision: either a warehouse is open (incurring its fixed cost and serving customers) or it is closed (incurring no cost but serving no demand). Continuous LP cannot model this trade-off — it would fractionally open warehouses, leaving a fractional solution meaningless.
Common misconception: "Our MIP formulation is too hard; let's relax the integer constraints and round the solution." This treats integrality as an inconvenience, not a feature.
Reality: MIP is hard because it models decisions that are inherently discrete. Rounding an LP solution often violates constraints (a warehouse fractionally open cannot serve a customer). The difficulty of solving an MIP depends on how loose the LP relaxation is — the integrality gap. A tight formulation (one where the LP relaxation naturally stays close to integer values) solves in seconds; a loose formulation explodes exponentially.
The skill is in formulating tight MIPs, not in solver tuning. This means choosing variable definitions, constraints, and objective structures that make the LP relaxation a good approximation of the integer problem. A solver cannot overcome a poor formulation.
A tight MIP formulation with a small integrality gap solves faster than a loose one on faster hardware — formulation quality matters more than solver speed.