Big-M either-or constraint: an integer programming example, solved and checked
The big-M either-or constraint is a classic integer programming problem. Here it is solved by a real solver (HIGHS) and checked: every constraint, the dual, and the optimality certificate. Change the numbers below and solve your own.
Solve your own version free, no account needed
The problem
A buyer orders x tonnes of grade A and y tonnes of grade B (x, y >= 0) at $3 and $2 per tonne, and must take at least 1 tonne of grade B. The contract is met if either the total order is at least 6 tonnes, or at least 3 tonnes of grade A are ordered (or both). Minimize cost.
How the model was built
The objective as written from the problem, before the numbers are multiplied out:
- w picks which condition is enforced. x + y ≥ 6w: with w = 1 the total must be at least 6 tonnes; with w = 0 it says x + y ≥ 0, which always holds.
- x ≥ 3 − 3w: with w = 0 at least 3 tonnes of grade A are needed; with w = 1 it says x ≥ 0. The 6 and the 3 are the smallest big-M values that switch each condition off.
Assumptions:
- "either ... or (or both)" is modeled with a binary switch w. When w=1, x+y>=6 is enforced. When w=0, x>=3 is enforced. Both can still hold when one is selected.
The model
Each line has a plain-language note on the right.
| make as small as possible: total purchase cost (dollars) | |
| tonnes of grade B ordered (tonnes) is at least 1 | |
| limit 2: left side must reach at least the right side | |
| limit 3: left side must reach at least the right side | |
| tonnes of grade A ordered (tonnes) cannot be negative | |
| tonnes of grade B ordered (tonnes) cannot be negative | |
| yes (1) or no (0) |
In matrix form
With its numbers:
What is being decided
There are 3 decision variables.
| Variable | Type | Meaning |
|---|---|---|
| y | real number | tonnes of grade B ordered (tonnes) |
| x | real number | tonnes of grade A ordered (tonnes) |
| w | binary (0 or 1) | 1 if the contract is met via total order >= 6 tonnes, 0 if via grade A >= 3 tonnes (yes/no) |
Goal and limits
Minimize total purchase cost (dollars) subject to 5 constraints, of which 3 are simple bounds on a single variable.
Problem type
MILP, complexity level 5: integer variables with linear objective and constraints. Solved with HIGHS at the Medium solver tier.
The answer at a glance
The optimal value of each decision, as the solver returned it.
Which constraints hold the answer in place
Binding (no slack left): (1) y >= 1; (3) x >= 3 - 3*w. Changing a binding constraint changes the answer; a slack one can move a little without effect.
| # | Constraint | Value | Limit | Slack | Binding |
|---|---|---|---|---|---|
| 1 | y >= 1 | 1 | 1 | 0 | yes |
| 2 | x + y >= 6*w | 4 | 0 | 4 | |
| 3 | x >= 3 - 3*w | 3 | 3 | 0 | yes |
| 4 | x >= 0 | 3 | 0 | 3 | |
| 5 | y >= 0 | 1 | 0 | 1 |
Algebraic model (low level)
Decision variables, objective and every constraint written out; this is exactly what the solver receives.
Standard form
As a linear program: minimize cᵀx subject to A x ≤ b (the inequality rows) and A_eq x = b_eq (the equations); a maximization is written as minimizing the negative.
Model code (cvxpy)
The same model in cvxpy, ready to run.
import cvxpy as cp
y = cp.Variable(name='y') # tonnes of grade B ordered (tonnes)
x = cp.Variable(name='x') # tonnes of grade A ordered (tonnes)
w = cp.Variable(name='w', boolean=True) # 1 if the contract is met via total order >= 6 tonnes, 0 if via grade A >= 3 tonnes (yes/no)
objective = cp.Minimize(3*x + 2*y)
constraints = [
y >= 1,
x + y >= 6*w,
x >= 3 - 3*w,
x >= 0,
y >= 0,
]
problem = cp.Problem(objective, constraints)
problem.solve(solver='HIGHS')
print(problem.status, problem.value)
print('y =', y.value)
print('x =', x.value)
print('w =', w.value)The dual problem
Every constraint of the original (primal) problem gets a price, and every primal variable becomes a constraint on those prices. Integer variables are relaxed: this is the dual of the continuous (LP) relaxation, which gives a bound on the integer optimum, not its exact value. Only weak duality: the dual of the continuous relaxation gives an lower bound of 7 on the integer optimum 11, a duality gap of 4. Integer problems generally have a gap.
| Dual variable | Prices | Value |
|---|---|---|
| y1 | price of constraint 'y >= 1' (objective change per extra unit of its right-hand side) | 1 |
| y2 | price of constraint 'x + y >= 6*w' (objective change per extra unit of its right-hand side) | 1 |
| y3 | price of constraint 'x >= 3 - 3*w' (objective change per extra unit of its right-hand side) | 2 |
| y4 | price of constraint 'w <= 1' (objective change per extra unit of its right-hand side) | 0 |
Solve your own
This is the model as the app reads it. Change any number and solve it in the free box on the front page (no account needed).
minimize 3*x + 2*y
subject to
y >= 1
x + y >= 6*w
x >= 3 - 3*w
x, y >= 0
binary: w
# x = tonnes of grade A ordered (tonnes)
# y = tonnes of grade B ordered (tonnes)
# w = 1 if the contract is met via total order >= 6 tonnes, 0 if via grade A >= 3 tonnes (yes/no)
# objective = total purchase cost (dollars)
# assume: "either ... or (or both)" is modeled with a binary switch w. When w=1, x+y>=6 is enforced. When w=0, x>=3 is enforced. Both can still hold when one is selected.Checked: the app's answer matches the reference answer in our test set, which two solvers (HIGHS, SCIP) agree on. Built 2026-11-10.
Related examples
Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.