Recurring Shapes of Linear Programs

Two descriptions can read very differently and produce the same algebra. A feed mill meeting nutrient minima at least cost and a hospital meeting staffing minima at least cost are one shape wearing two stories.

The shape is visible before any coefficient is written, and it settles three things: which way the objective runs, which way the constraints point, and which terminal outcome is the one worth testing for. A description asking that requirements be met produces floors and a minimisation. One asking that scarce capacity be used well produces ceilings and a maximisation.

Getting this right early is cheap. Getting it wrong survives every arithmetic check, because a program with a reversed inequality is still a well-formed program. It simply answers a question nobody asked.

This unit assumes you can already turn a description into variables, an objective and constraints.

The language of a description usually settles the shape before any modelling begins.

Words that mean floors. Meet, cover, at least, requirement, demand, minimum standard. Something must be achieved, and the question is how cheaply. The objective minimises, the constraints read $\ge$, and the optimum pushes down until requirements bind.

Words that mean ceilings. Available, capacity, at most, budget of hours, limited. Something is scarce, and the question is how well it can be used. The objective maximises, the constraints read $\le$, and the optimum pushes up until resources bind.

Words that mean a fixed total. Divide, allocate, split, the whole budget. The total is not a limit to stay under but a quantity to distribute, so the constraint is an equality and the bounds sit on the individual shares.

The shape then predicts where the answer will sit. In the covering shape every unit of slack is paid for and not required, so the cheapest solution usually meets its requirements exactly. A blend that overshoots a nutrient minimum is buying something nobody asked for. In the packing shape the opposite holds: the optimum consumes what is available, so the binding constraints are the scarce resources.

It also predicts which failure to look for first. A covering problem cannot run to $-\mathrm{\infty }$ when costs are nonnegative, but it can be infeasible, because the floors may demand more than the activities can jointly supply. A packing problem is rarely infeasible, since producing nothing is usually allowed, but it can be unbounded, when some activity contributes to the objective without consuming anything scarce. Testing the shape's characteristic failure is faster than waiting for a solver to report it.

None of this substitutes for formulation. It gives an expectation to check the finished model against, and a model that contradicts its own shape has a reversed inequality somewhere.

Beyond the three templates themselves, what carries over is how each one's data is indexed and what its rows mean.

Covering. Row $i$ of $N$ answers: how much of requirement $i$ does one unit of each activity supply? The right-hand side $r_i$ is how much is required. A column is an activity's contribution profile.

Packing. Row $i$ of $A$ answers: how much of resource $i$ does one unit of each activity consume? The right-hand side $b_i$ is how much exists. A column is an activity's consumption profile.

The two matrices are indexed identically and mean opposite things, which is why a modeller who copies a template without re-reading the description can produce a program whose constraints point the wrong way while every number is correct.

Allocation. One row is the total, $\sum _j{w}_j=W$. The remaining restrictions are bounds on individual shares, ${\ell }_j\le w_j\le u_j$, not further rows mixing the variables. This is what makes the shape bounded without any resource constraint: the equality alone confines the feasible set.

Hybrids, and how to write them. A packing problem with a contractual minimum has both directions. Write the ceilings as $\le$ rows and the floor as its own $\ge$ row; do not negate the whole system to make it uniform at the modelling stage. Uniformity is a conversion step that belongs to standard form, where the direction is recorded deliberately rather than lost.

What the shape does not fix. Whether variables are divisible, whether the data is certain, and whether the objective is genuinely linear. A blending problem with a fixed setup charge per ingredient is still a covering shape and is no longer a linear program.

Covering: a feed blend. Three ingredients cost £0.80, £1.20 and £0.50 per unit. Each unit supplies protein 12, 20, 4 and fibre 3, 1, 6. A batch must supply at least 60 protein and at least 30 fibre.

The cheapest blend on a half-unit grid is $x=(4,0,3)$, costing $0.8(4)+0.5(3)=4.70$, supplying protein $12(4)+4(3)=60$ and fibre $3(4)+6(3)=30$. Both requirements are met exactly, which is the covering shape behaving as expected: overshooting a minimum costs money and buys nothing the problem asked for.

Packing: a two-product plan. Each unit of product 1 uses 3 machine hours and 1 labour hour; product 2 uses 2 and 4. There are 120 machine hours and 100 labour hours. Contributions are £25 and £30.

Solving the two constraints as equalities gives $y=(28,18)$, where $3(28)+2(18)=120$ and $28+4(18)=100$: both resources exhausted. The contribution is $25(28)+30(18)=1240$. Again the shape behaved as expected. The optimum sits where the scarce resources bind.

Allocation: a budget split. Three assets return 7%, 4% and 11%. The whole budget is placed, no asset takes less than 10%, and the highest-returning asset is capped at 25% by policy.

The best split is $w=(0.65,0.10,0.25)$, returning $0.07(0.65)+0.04(0.10)+0.11(0.25)=0.077$. The cap binds at $0.25$ and the weakest asset sits at its floor of $0.10$: with the total fixed, every share given to one asset is taken from another, which is what distinguishes this shape from a packing problem.

What to notice across the three. Each optimum sits where the shape predicted, on the floors, on the ceilings, on the bounds. None of that required solving the programs; it followed from reading which way the constraints point.

Description. A bakery has 2,400 oven-minutes and 900 kg of flour next week. A tray of sourdough uses 30 oven-minutes and 12 kg and contributes £18; a tray of rye uses 20 oven-minutes and 9 kg and contributes £13. A standing wholesale order requires at least 20 trays of rye. Plan the week to maximise contribution.

---

Step 1: read for the verb. "Has 2,400 oven-minutes and 900 kg" is capacity language: scarce things, stated as what exists. "Requires at least 20 trays" is requirement language: a floor. "Maximise contribution" fixes the objective direction.

Step 2: name the shape. Predominantly packing, a scarce-resource problem with a maximisation, carrying one covering row. It is a hybrid, and saying so is part of the answer: forcing the rye minimum into a $\le$ row to keep the system uniform would assert a ceiling of 20 trays, which the description does not say.

Step 3: state what the shape settles.

Step 4: write it. Let $s$ and $r$ be trays of sourdough and rye per week.

Step 5: test the shape's prediction. Try the corner where both resources bind. Solving $30s+20r=2400$ and $12s+9r=900$ gives $s=60$, $r=30$. Check the order row: $r=30\ge 20$, satisfied. Contribution is $18(60)+13(30)=1080+390=1470$.

Check the resources at that point: oven $30(60)+20(30)=2400$, flour $12(60)+9(30)=900$. Both exhausted, as the packing shape predicted, and the covering row is slack.

Step 6: what the classification supplied. Three directions were fixed before any arithmetic, and the expectation, that the scarce resources would bind, gave a specific corner to test first. The order row turned out not to bind, which is information: the wholesale commitment costs the bakery nothing this week, and would only start to matter if rye became less attractive or oven time scarcer.

A check worth running. Had the order required 40 trays of rye instead, the both-resources-tight point $r=30$ would violate it, and the optimum would move onto the order row. The shape does not tell you which constraints bind; it tells you which ones to examine first.

Classifying by subject rather than by structure. "This is a production problem, so it is a packing shape." Production usually is, and a plant asked to meet a delivery schedule at least cost is a covering problem wearing production vocabulary. The industry supplies the nouns; the verbs supply the shape.

Forcing a hybrid into one template. A packing problem with a contractual minimum is written with every row as $\le$, so the minimum becomes a maximum. The program parses, solves, and reports a plan that quietly breaches the contract. Nothing in the arithmetic objects, because a reversed inequality is still a valid constraint.

Treating the allocation equality as a ceiling. Writing $\sum _j{w}_j\le W$ for "divide the whole budget" permits leaving part of it unplaced. With a maximisation and positive returns the optimum usually spends it all anyway, so the model appears to work, until returns can be negative, or a policy makes holding cash preferable, and the model silently answers a different question.

Reading the objective direction off the coefficients. "The numbers are costs, so this minimises." A problem may maximise a margin that has costs inside it, or minimise a shortfall whose coefficients are quantities rather than money. What the objective does comes from what the description asks for, not from what the coefficients are called.

What unites the four is that each produces a solvable program. The classification cannot be checked by running the model, because a misclassified model runs perfectly well; it is checked by reading each constraint back as a sentence and asking whether the description says that.

A feed mill has three ingredients with known costs and known protein and fibre contents. Two different questions can be asked about exactly the same data.

The coefficient tables are the same numbers and the programs are different, because the rows have swapped roles: nutrient content read as supply in one, stock levels read as consumption in the other.

Where the two meet. A real feed mill faces both at once, meet the nutrient minima, using no more than the stock on hand. That is a hybrid with covering rows and packing rows, and it can be infeasible in a way neither pure shape can: the stock may be insufficient to reach the nutrient floors. Recognising both sets of rows is what makes that failure diagnosable rather than mysterious.

Why the distinction is worth making early. The two programs have different sensitivities. In the covering problem the binding quantity is a requirement, so the question "what would relaxing this cost?" is about the specification. In the packing problem it is a resource, so the same question is about procurement. A model that has the shape wrong answers the wrong management question even when its arithmetic is impeccable.