Practice: Modelling with Binary Variables

Variables. $w,s,g\in \{0,1\}$, equal to $1$ if wind, solar, gas respectively is built. $q_w,q_s,q_g\ge 0$, the MW supplied by each.

At least two of the three.

Forbids: building none or exactly one.

Gas only if wind.

Forbids: $g=1$ with $w=0$, and nothing else. Note it leaves wind-without-gas permitted, as the sentence intends.

Capacity links, upper.

Forbids: supplying from an unbuilt source, and exceeding a built source's rating. Each $M$ comes from the stated rating, which is where a bound should come from.

Minimum output when built.

Forbids: building a source and running it below 10 MW. When the binary is $0$ these read $q\ge 0$, already true, so they impose nothing on unbuilt sources.

Total capacity.

Forbids: any plan supplying under 60 MW.

Objective, if minimising cost.

The fixed charges sit with their binaries, and the capacity links make them payable, without $q\le Mw$ the model would supply wind power with $w=0$ and never pay the £3m.

A check. $w=1,s=1,g=0$ with $q_w=40$, $q_s=25$, $q_g=0$: two sources built, gas implication holds vacuously, each quantity inside its sandwich, total $65\ge 60$. Feasible, cost £5m.

What the model permits. $y=0$ with $q=500$. The depot is not opened, the £2,000 is never paid, and five hundred tonnes ship from it. Since the objective minimises cost, this is exactly what a solver will return: there is no reason to set $y=1$ when doing so costs £2,000 and buys nothing.

The missing constraint. Nothing connects $q$ to $y$. The condition "nothing ships from a closed depot" was never encoded. It needs a linking constraint:

With $y=0$ this forces $q=0$; with $y=1$ it is the capacity limit, so it also replaces the standalone $q\le 500$.

Reviewing the constraints that are present.

• $q\le 500$: true, and forbids $q=600$. Genuine work, though subsumed once the link is added.
• $q\ge 0$: forbids nothing. The variable was already declared nonnegative.
• $y\le 1$: forbids nothing. The variable was already declared binary.

Two of the three constraints are true statements that restrict nothing the model could otherwise have done.

What is wrong with the justification. "Every constraint is true" cannot detect this fault, because the fault is not a false statement. It is a missing one. A review that reads each constraint and confirms it is true will pass this model every time.

The review that works. Two passes. First, for each constraint, name an assignment it forbids that the rest of the model would permit; a constraint with no such assignment is doing nothing. Second, for each condition in the description, name the constraint that enforces it. "Nothing ships from a closed depot" has no answer in this model, and that second pass is what exposes it.

Why fixed charges are where this bites hardest. A cost in the objective with no linking constraint is always declined by an optimiser. The binary becomes pure cost with no consequence, so the charge is never incurred and the activity runs free.

Variables. $x_j\in \{0,1\}$ for $j=1,\dots ,6$, equal to $1$ if proposal $j$ is funded.

Objective.

Budget.

Forbids: any selection costing more than the budget.

Duplication.

Forbids: funding both, while permitting either alone or neither.

Precursor.

Forbids: funding proposal 6 without proposal 2. It leaves 2 fundable alone, which is correct. A precursor need not lead anywhere.

What this is. A knapsack problem with two side conditions: maximise value subject to a single capacity constraint, with items indivisible.

The fractional version. Replace $x_j\in \{0,1\}$ with $0\le x_j\le 1$. The problem becomes a linear program, and it is solved by a simple rule: order the proposals by value-per-pound $v_j/c_j$ and fund them in that order until the budget runs out, with at most one proposal funded partially at the end. The side constraints complicate this slightly but the problem remains a linear program.

Why the fractional version is far easier. Its feasible set is a polyhedron, so the optimum sits at a vertex and the geometry does the work. Restoring integrality removes that: the feasible set becomes the $2^6$ corner points of the unit cube that satisfy the constraints, with no direction to move in and no vertex guarantee.

The consequence. The greedy value-per-pound rule is optimal for the fractional problem and can be arbitrarily bad for the integer one. A proposal with the best ratio may consume so much budget that two lesser proposals would have scored higher together, and no amount of care in applying the ratio rule finds that, because it requires declining the item the rule ranks first.

Why this is the transfer. The patterns here are the ones already met, a selection count, an implication, a budget, arriving in a named problem family under different vocabulary, with the integrality question carrying real consequence.