Absolute value in the objective — Minimises total absolute deviation from a target vector. The absolute value is replaced by one auxiliary variable per term bounded below by both signs of the deviation; minimisation drives it down to the true absolute value. Replace |e| by t with t ≥ e and t ≥ −e when minimising.
Linear assignment — Matches agents to tasks at least total cost. The constraint matrix is totally unimodular, so the LP relaxation is already integral and the binaries are a modelling convenience rather than a necessity. A doubly-stochastic 0/1 matrix: one row sum and one column sum equal to 1.
Bin packing — Packs items into as few bins as possible. Each bin's capacity row is multiplied by its open indicator so an unused bin can hold nothing, which is the fixed-charge pattern applied per bin. Assignment binaries plus per-bin capacity gated on a bin-used binary.
Product of two binary variables — Maximises a quadratic objective over binary selections subject to a cardinality limit. The quadratic term is linearised exactly with one auxiliary binary per pair, which is tight because the three inequalities force z to equal the product at every 0/1 point. Replace the product x_i·x_j by an auxiliary binary z_ij with z ≤ x_i, z ≤ x_j, z ≥ x_i + x_j − 1.
Capacitated facility location — Opens facilities and assigns customers subject to each site's throughput limit. The capacity row folds the linking constraint into itself — an unopened facility has zero capacity, so assignments to it are already forbidden — but the disaggregated link is usually kept anyway because it strengthens the relaxation. Uncapacitated location plus a capacity row per facility: sum_i d_i x_{i,j} <= k_j y_j.
Capacitated lot sizing — Adds a production ceiling to uncapacitated lot sizing, which is what makes the problem hard: without it a period can always cover all future demand and the shortest-path reformulation applies. The big-M on the setup row is tightened to the smaller of the capacity and the demand still to be met, because a looser one weakens the relaxation for nothing. Wagner–Whitin balance plus a per-period capacity that the setup binary gates: x_t <= min(capacity, remaining demand) * y_t.
Chance constraint via scenario binaries — Requires a capacity limit to hold in at least a given fraction of scenarios rather than all of them. Each scenario gets an indicator that buys it out of the constraint, and a cardinality row caps how many may be bought out — the deterministic equivalent of "hold with probability at least 1 − alpha" when the scenarios are equally likely. A per-scenario binary z_s relaxes the constraint by big-M when the scenario is allowed to fail, and sum z_s bounds how many may.
Counting and cardinality — Selects exactly k items while an auxiliary count tracks how many of a distinguished subset were taken, which is then bounded. Counting is a plain sum of binaries; no auxiliary machinery is required. Constrain how many binaries may be 1 with a single sum, and count occurrences by summing indicators.
Secondary criterion moved into a constraint — Maximises profit subject to an explicit ceiling on total risk. Since only one objective may be declared, the second criterion becomes a constraint rather than a weighted term. This reaches efficient points a weighted sum cannot, including ones in a non-convex region, at the cost of one solve per bound value. Keep one criterion in the single objective row and impose the others as bounds, re-solving for different bound values.
Capacitated vehicle routing (MTZ load form) — Routes a fleet from one depot so every customer is visited once and no vehicle exceeds its capacity. The load variable does double duty — it rules out subtours the way MTZ does for the TSP, and because it accumulates demand along the route it enforces capacity at the same time, which is why this is the compact CVRP formulation of choice. Degree constraints per customer plus load potentials that both eliminate subtours and enforce capacity: u_j >= u_i + q_j - Q(1 - x_ij).
Diet / blending — Mixes ingredients at least cost while meeting minimum nutrient levels. The `>=` rows make this the covering counterpart of product mix, and the blend is naturally fractional. Minimise cost subject to lower bounds on each nutrient — a covering LP with `>=` rows.
Minimum dominating set — Chooses the fewest vertices such that every vertex is either chosen or adjacent to a chosen one. The closed neighbourhood of each vertex comes from a parametric set, so the constraint sums over a script-defined index domain rather than a literal set. Closed-neighbourhood covering using a parametric set function N(v) supplied by the script.
Maximum weight matching — Selects the heaviest set of edges with no two sharing a vertex. The incidence structure is a parametric set mapping each vertex to the edges it belongs to, which keeps the constraint one line regardless of graph density. Degree constraints written over a parametric incidence set inc(v), so each vertex bounds the edges touching it.
Disjunctive (either-or) constraints — Requires at least one of two resource constraints to hold rather than both. A binary selects which is active; the inactive one is relaxed by a big-M chosen large enough to be non-binding but no larger. Relax one of two constraints with a big-M term controlled by a binary, so exactly one is enforced.
Fixed charge with continuous production — Pays a setup cost to open a line and then produces any continuous amount up to its capacity. This is the genuinely mixed case — the setup is discrete, the quantity is not — and its optimum is fractional wherever demand does not land on a capacity boundary. A binary setup gating a continuous level: x ≤ U·y, mixing integer and continuous variables in one model.
Fixed-charge network design — Chooses which arcs to build as well as how much to send over them. The binaries are what take this out of the totally unimodular world — the flow part alone would be integral, but paying to open an arc makes it a genuine mixed-integer problem. A binary opens each arc and a big-M capacity link ties flow to it: f_a <= u_a · y_a, with the tightest valid M being the arc capacity.
Fixed-charge (setup) cost — Chooses production levels where each active line incurs a one-off setup cost plus a per-unit cost. The linking constraint uses the tightest valid upper bound, which is the line's own capacity rather than a generic big-M. Link a continuous activity to a binary setup with x ≤ U·y so the fixed cost is paid exactly when the activity is nonzero.
Soft constraints by goal programming — Hits production targets as closely as possible when hitting them exactly may be infeasible. Each target becomes an equality with a pair of non-negative deviations; penalising them keeps the model feasible and makes the trade-off explicit rather than hidden in constraint ordering. Add under/over deviation variables to a target and penalise them in the objective instead of enforcing the target strictly.
Graph colouring — Assigns colours so no edge is monochromatic, minimising colours used. The colour-used indicator is dominated by the assignment variables, which is what turns a feasibility question into a minimisation. One binary per (vertex, colour); adjacent vertices may not share a colour; a colour-used binary counts the palette.
Logical implication between binaries — Encodes prerequisite structure among selectable options: choosing a dependent option forces its prerequisite. The inequality form is exact and needs no auxiliary variable. x ⇒ y becomes x ≤ y; a conjunction premise needs x1 + x2 − 1 ≤ y.
Maximum weighted independent set — Selects the heaviest set of mutually non-adjacent vertices. Uses the same edge-to-endpoint mapping as vertex cover with the inequality reversed, which is the standard complementary formulation. The complement pattern of vertex cover: y_{alpha(e)} + y_{beta(e)} <= 1 forbids both endpoints of any edge.
Job shop, disjunctive formulation — Schedules multi-operation jobs across machines where each job visits the machines in its own order. Two constraint families do the work: precedence within a job is a plain inequality, while non-interference on a machine needs the disjunctive pair, since either operation may go first. Precedence rows inside each job, plus a big-M either-or pair for every pair of operations sharing a machine.
0/1 knapsack — Selects a subset of items maximising value within a weight budget. The canonical single-constraint integer program and the base case every other packing formulation specialises. One binary per item, a single capacity row.
Bounded knapsack — Packs multiple copies of each item, up to a per-item limit. The only structural change from the 0/1 case is the variable type and its bound; the capacity row is identical, which is why the bounded case is usually presented as a variant rather than a separate problem. Integer counts with per-item upper bounds instead of binaries — int 0 <= x <= b_i rather than bin x.
Multidimensional knapsack — Extends the knapsack to several simultaneous resource limits, so an item consumes a vector rather than a scalar. Adding rows does not change the variable structure, only the feasible region. Several independent capacity rows over the same binaries.
Unbounded knapsack — Packs unlimited copies of each item. Removing the per-item bound from the bounded case leaves the capacity constraint as the only thing limiting any variable, which is what makes the greedy density heuristic so nearly right here and badly wrong in the 0/1 case. Integer counts with no per-item limit — only the capacity row bounds them.
Aggregated (big-M) linking constraint — Links assignments to open facilities with one aggregated row per facility. Fewer constraints than the disaggregated form, and the same integer optimum, but a materially weaker bound — which is what a branch-and-bound search actually searches against. One row per facility: sum_i x_ij <= |C|·y_j. Compact, but the LP relaxation is weak because a single fractional y_j releases every assignment at once.
Disaggregated linking constraint — Links each assignment to its facility individually. It describes exactly the same integer feasible set as the aggregated form and reaches the same optimum, but its relaxation is at least as strong and usually strictly stronger, which is the classic size-versus-strength trade-off. One row per assignment: x_ij <= y_j. More rows, but the LP relaxation is tight — this is the ideal formulation of the same set.
Logarithmic encoding of a choice — Picks exactly one alternative while using logarithmically many binaries rather than one per alternative. The selection indicator is reconstructed from the bit pattern, trading a smaller variable count against a less transparent model. Select one of k alternatives with ceil(log2 k) binaries instead of k, using a binary expansion of the index.
Single-item lot sizing with setups — Decides when to produce and how much, trading setup cost against holding cost. The balance constraint uses index arithmetic to reference the previous period, with the first period split out because t-1 would fall outside the set. Inventory balance across periods with index arithmetic s_{t} = s_{t-1} + x_{t} - d_{t}, and production gated on a setup binary.
Multiple travelling salesman — Partitions customers among m salesmen, each starting and ending at the depot, minimising total distance. Structurally it is CVRP with unlimited vehicle capacity, which isolates what the load variable contributes: with capacity removed the potentials are doing only subtour elimination. CVRP with the capacity row dropped: exactly m routes leave the depot, and potentials handle subtours alone.
Maximum clique — Finds the largest mutually adjacent set of vertices. The constraint runs over the complement graph, which is the mirror of independent set — a clique in G is an independent set in the complement of G, and the two formulations differ only in which pairs they forbid. Forbid every NON-edge: y_u + y_v <= 1 for each pair with no edge between them.
Maximal covering location — Places a limited number of facilities to cover as much demand as possible within a service radius, rather than to minimise distance. Coverage is an indicator dominated by the open facilities that can reach the point, which is the covering counterpart of p-median. A demand point counts as covered when at least one facility within range is open: z_i ≤ sum of y_j over the covering set.
Maximum cut — Splits vertices into two sides maximising the weight of edges crossing. The cut indicator is linearised by two inequalities that together force it to zero unless the endpoints differ, which is exact at 0/1 points. Partition indicator per vertex plus an edge-cut variable sandwiched by z ≤ y_a + y_b and z ≤ 2 − y_a − y_b.
Maximum flow — Pushes as much as possible from source to sink. By max-flow min-cut the optimum equals the capacity of the lightest cut separating them, which is the LP dual of this program — the reference here checks the primal value against enumeration of every cut. Maximise the flow leaving the source subject to node balance at every intermediate node and arc capacities.
Maximising a minimum over continuous shares — Divides a divisible resource so the worst-off share is as large as possible. Because the quantities are continuous the optimum equalises the shares and is generally fractional, which an integer formulation of the same idea would round away. t ≤ e_i for every i with t continuous, maximised — the continuous form of the maximin pattern.
Maximising a minimum — Maximises the worst-off share in a fair-division problem. The mirror of the minimax pattern: a single auxiliary variable is dominated by every term, and maximisation lifts it to exactly the minimum. Replace min_i e_i by t with t ≤ e_i for all i, then maximise t.
Minimum-cost network flow — Routes supply to demand at least cost. This generalises transportation, transshipment and shortest path — each is this model with a particular supply vector and network shape. The node-arc incidence matrix is totally unimodular, so with integer supplies and capacities the LP optimum is already integral and no integer variables are needed. Node balance with arc capacities: outflow − inflow = supply at every node, flow bounded by capacity on every arc.
Minimising a maximum — Balances load across machines by minimising the largest load. The maximum becomes a single auxiliary variable dominating every term; minimisation pushes it to exactly the maximum. Replace max_i e_i by t with t ≥ e_i for all i.
Multi-period production planning — Plans production across periods where stock carries forward. Unlike lot sizing there is no setup binary, so the whole model stays an LP — the balance row is the only thing coupling periods, and it is what turns a sequence of independent decisions into one plan. Inventory balance links consecutive periods: s_t = s_{t-1} + x_t - d_t, with the first period split out.
Multi-commodity flow — Routes several commodities across one network where arcs are shared. The bundle constraint is what destroys total unimodularity: each commodity alone would be integral, but together they can force fractional extreme points, which is why indivisible commodities need integer variables here and not in single-commodity flow. One flow variable per (commodity, arc) with per-commodity balance rows and a shared bundle capacity coupling them.
Multiple knapsack — Packs items into several knapsacks of different capacities. Unlike bin packing, items may be left out entirely and the objective is the value packed rather than the number of bins — the constraint is `<= 1`, not `= 1`. Assignment binaries x_{i,k} with one capacity row per knapsack, and each item assigned at most once across all of them.
Mutual exclusion and complementarity — Selects from options where certain pairs cannot coexist. The pairwise form is the tightest encoding for isolated conflicts; a clique of mutually conflicting options is better written as one constraint summing over the clique. At most one of a conflicting pair may be chosen: x_i + x_j ≤ 1.
p-center (minimax location) — Places p facilities so the furthest customer is as close as possible. The objective is minimax where p-median is min-sum, so the same data and the same assignment variables give a different answer — this is the equity-oriented counterpart, driven by the worst case rather than the average. Minimise the worst assignment distance with an auxiliary variable: t >= d_{i,j} x_{i,j} for every pair, then minimise t.
p-median facility location — Places a fixed number of facilities to minimise average travel. Differs from uncapacitated location in that the count is a hard constraint rather than a cost, so there is no fixed charge to trade against. Open exactly p facilities and assign each demand point to an open one, minimising total weighted distance.
Piecewise-linear, incremental (delta) form — An alternative to the convex-combination form. The level is the sum of filled segment fractions, and ordering constraints force segments to be consumed left to right, so the cost picks up each segment's slope in turn. Locally ideal, and uses one binary fewer than the lambda form. Fill segments in order: delta_s in [0,1], and a segment may only start once the previous one is full, enforced by z_s.
Piecewise-linear cost, convex-combination form — Prices an activity along a piecewise-linear cost curve. Both the level and its cost are written as convex combinations of the same breakpoint weights, so any feasible weighting names a point on the curve. Adjacency is enforced with segment binaries, which is what makes the form exact for a non-convex curve rather than only for a convex one. Express x and f(x) as the same convex combination of breakpoints, with the lambda weights summing to 1 and at most two adjacent ones nonzero.
Prize-collecting / orienteering tour — Chooses which customers are worth visiting as well as the order. The degree constraints are equalities against y_i rather than against 1, so a skipped node has no arcs at all; that single change turns a routing problem into a selection-and-routing problem. Visiting is optional — a per-node binary y_i gates its degree constraints, and the objective trades collected prize against travel.
Product of a binary and a bounded continuous variable — Switches a continuous quantity on or off inside the objective. The four inequalities pin the auxiliary variable to the product at every integer point of the binary, which is the standard Glover linearization and is exact rather than a relaxation. z = y·x with y binary and 0 ≤ x ≤ U becomes z ≤ Ux, z ≤ y, z ≥ y − U(1 − x), z ≥ 0.
Product mix — Chooses how much of each product to make when several products compete for the same limited resources. The optimum generally lands on a vertex with fractional levels, which is why the variables are continuous rather than integer. Continuous activity levels limited by shared resource rows; the canonical linear program.
Robust counterpart under box uncertainty — Protects a capacity constraint against coefficients that may each vary within a known interval. Because the variables are non-negative, the worst case is attained at the upper corner of every interval independently, so the robust counterpart is another linear constraint with no extra variables — the simplest uncertainty set, and the only one whose counterpart stays an LP with no growth. Replace each uncertain coefficient by its worst-case value over the box: for a <= constraint with non-negative variables, the nominal coefficient plus its deviation.
Semi-continuous variable — Allows an activity to be switched off entirely or run at no less than a minimum viable level. Two linking constraints against the same binary give the disconnected domain {0} ∪ [L, U] exactly. x = 0 or L ≤ x ≤ U, written as L·y ≤ x ≤ U·y with y binary.
Weighted set covering — Chooses the cheapest collection of subsets whose union is the whole ground set. The element-to-subset incidence is supplied as a parametric set, which is the natural encoding when membership is data rather than structure. Cover each element by summing the indicator of every set that contains it, using a parametric set of covering sets per element.
Set partitioning — Chooses subsets so that every element is covered exactly once — no gaps and no overlap. The equality is what separates it from set covering, and it is the backbone of crew pairing and rostering, where a duty must be flown once rather than at least once. Cover every element exactly once: Ax = 1, rather than the Ax >= 1 of covering or the Ax <= 1 of packing.
Shortest path by arc selection — Finds a least-cost path as a unit flow. Arcs are a flat index set with script functions giving tail and head, and the balance constraint sums over parametric out/in arc sets per node. Flow conservation on node balances: outflow − inflow equals +1 at the source, −1 at the sink, 0 elsewhere.
Single-machine sequencing, disjunctive (big-M) formulation — Sequences jobs on one machine to minimise the makespan-equivalent completion of the last job. Time stays continuous and only the pairwise ordering is discrete, which keeps the model small — but the big-M rows give a weak relaxation, since a fractional y_ij releases both orderings at once. Continuous start times with a binary per pair deciding the order: s_j >= s_i + p_i - M(1 - y_ij) and the mirrored inequality.
At most one nonzero (SOS1 by binaries) — Permits at most one activity to take a nonzero value, the condition a solver would otherwise express as a special ordered set of type 1. Written with explicit binaries and variable upper bounds it needs no solver-specific declaration. Bound each continuous variable by its own indicator and allow at most one indicator to be 1.
Piecewise-linear via SOS2-style adjacency — Evaluates a piecewise-linear function using the adjacency condition a solver would express as a special ordered set of type 2. Written out with binaries it needs no solver-specific declaration, at the cost of one binary per segment — the same trade the SOS1 case makes. At most two lambda weights may be nonzero and they must be adjacent — written with one binary per breakpoint pair rather than a solver-native SOS2 declaration.
Minimum spanning tree — Connects every vertex at least total cost. The cardinality row alone would allow a forest plus a cycle, so the subset rows are what force acyclicity — the same family DFJ uses for tours, applied to trees. The LP relaxation of this description is integral, which is why a greedy algorithm solves it exactly. Pick exactly |V| - 1 edges and forbid a cycle in every subset: edges inside S number at most |S| - 1.
Subset sum — Selects items summing to exactly a target. Degenerate as an optimisation problem — the objective is a formality and every feasible point is optimal — which makes it the cleanest illustration that a MIP can be a pure feasibility question. A single equality over binaries: hit the target exactly, with no objective to optimise beyond feasibility.
Time-indexed scheduling — Schedules jobs by deciding which period each one starts in. Far more variables than the disjunctive form — one per job-period pair — but the relaxation is much tighter and resource limits become a single sum per period instead of a big-M pair per job pair. A binary x_{j,t} for starting job j in period t. Each job starts once; a machine-capacity row per period covers the jobs spanning it.
Transportation problem — Ships goods from plants to markets at least cost. With integer supplies and demands the constraint matrix is totally unimodular, so the LP optimum is already integral — the classic demonstration that not every whole-number answer needs integer variables. Supply rows, demand rows and continuous shipment quantities on every origin-destination pair.
Transshipment — Ships from plants to markets through intermediate warehouses. The only structural difference from transportation is the presence of nodes whose balance is zero: they neither produce nor consume, they relay. Still totally unimodular, so still integral without integer variables. Node balance where intermediate nodes have zero supply, so flow passes through rather than originating or terminating.
Travelling salesman, DFJ subtour elimination — The same tours as the MTZ formulation, described a different way. DFJ needs exponentially many constraints — one per subset — where MTZ needs a polynomial number of potentials, but DFJ's relaxation is strictly stronger. In practice the subsets are separated lazily; here they are all written out, which is only tractable because the instance is small. One constraint per proper subset: sum of arcs inside S is at most |S| - 1, so no subset can close a tour of its own.
Travelling salesman with MTZ subtour elimination — Finds a minimum-cost Hamiltonian tour. Degree constraints alone admit disconnected subtours; the MTZ potentials rule them out compactly, at the cost of a weaker relaxation than exponential subtour cuts. Sequence potentials u_i with u_i − u_j + n·x_ij ≤ n − 1 forbid subtours with a polynomial number of constraints.
Two-stage stochastic programme with recourse — Chooses a capacity before demand is known, then meets whatever demand arrives by buying the shortfall at a penalty. The first-stage variable is shared across every scenario while the recourse variables are indexed by scenario — that split is the whole formulation, and it is what makes the model larger than the deterministic version by a factor of the scenario count. One here-and-now decision, then a separate wait-and-see decision per scenario, with the objective weighting recourse cost by scenario probability.
Uncapacitated facility location — Opens facilities and assigns every customer to one, trading fixed opening cost against service cost. The disaggregated linking constraint is used rather than sum_i x_ij <= n·y_j, because the disaggregated form gives a substantially stronger LP relaxation. Variable upper bound x_{i,j} <= y_j links assignment to an open facility, which is tighter than aggregating into one big-M row.
Minimum weighted vertex cover — Chooses the cheapest set of vertices touching every edge. Because sets hold plain integers, the edge list is a flat index set and incidence is supplied by two script functions mapping an edge to its endpoints. Address node variables from an edge-indexed constraint via endpoint mapping functions: y_{alpha(e)} + y_{beta(e)} >= 1.
Weighted single objective over several criteria — Trades profit against risk inside one objective row. The language admits a single min or max per model, so combining criteria is done by weighting them rather than by declaring several objectives. Varying the weights traces the convex hull of the efficient set, though not points lying in a non-convex dent -- for those, bound the secondary criterion instead. A model has exactly one objective, so competing criteria are folded into it as a weighted sum with non-negative weights.
Zero-sum matrix game — Finds the optimal mixed strategy and value of a two-player zero-sum game. The minimax structure becomes an LP: one variable per pure strategy plus the game value, and one row per opponent reply. Its dual is the opponent's own problem, which is von Neumann's minimax theorem read off LP duality. Maximise the value v subject to v <= the payoff of every pure opponent reply, with the mixed strategy summing to 1.