Recurring Shapes of Linear Programs

Most described decision problems fall into a few shapes: meet requirements at least cost, use limited resources for the most contribution, or divide a fixed budget under exposure limits. Recognising the shape fixes the direction of the objective, the direction of the constraints, and which terminal outcome is the one to watch for, before any coefficient is written.

Definition

Three shapes account for most linear programs met in practice. Each is defined by the direction of its objective and the direction of its constraints, which together determine where an optimum can sit.

Covering shape. Minimise cost subject to requirement floors:

min c^{T} x subject to N x \geq r, x \geq 0,

where row $i$ of $N$ holds how much of requirement $i$ each activity supplies, and $r$ holds the amounts required. Blending a feed to meet nutrient minima and staffing shifts to meet demand minima are both this shape.

Packing shape. Maximise contribution subject to resource ceilings:

max p^{T} x subject to A x \leq b, x \geq 0,

where row $i$ of $A$ holds how much of resource $i$ each activity consumes and $b$ holds what is available. Production planning against machine and labour hours is this shape.

Allocation shape. Divide a fixed total among competing uses:

max r^{T} w subject to \sum_{j} w_{j} = W, ℓ \leq w \leq u,

with an equality on the total rather than an inequality. Splitting a budget across investments and assigning a fixed staff establishment across teams are this shape.

What the shape settles in advance.

Shape	Objective	Constraints	Feasible set	Watch for
Covering	minimise	$\geq$ floors	unbounded above	infeasibility when floors conflict
Packing	maximise	$\leq$ ceilings	bounded when every activity consumes something	unboundedness when an activity consumes nothing
Allocation	either	one equality, plus bounds	bounded by the equality	infeasibility when the bounds cannot sum to $W$

The shapes compose. A production plan with a contractual minimum is a packing shape with one covering row; recognising the hybrid is what stops a modeller from forcing the whole problem into one template.

Assumptions and scope

The shapes are patterns in described problems, not a classification of linear programs. Every linear program can be written in any equivalent form; the shape describes how the situation presents itself, which is what makes it useful before the algebra exists.
A problem may be a hybrid. A packing problem with one contractual minimum has both directions present, and forcing it into a single shape produces a constraint pointing the wrong way.
The expected binding constraints are a prediction, not a theorem. A covering optimum may leave a floor slack when one activity supplies two requirements at once, and the prediction failing is information rather than an error.
Recognising the shape settles directions, not coefficients. The data still has to be read off the description and checked for units.
The allocation shape's equality is what bounds it. Replacing $\sum_{j} w_{j} = W$ with $\leq W$ changes the problem, and with a maximisation objective usually leaves the optimum unchanged but the model no longer says the whole total is spent.

Worked material

Example

One of each shape

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.

min 0.8 x_{1} + 1.2 x_{2} + 0.5 x_{3} s.t. \begin{aligned} 12 x_{1} + 20 x_{2} + 4 x_{3} & \geq 60, \\ 3 x_{1} + x_{2} + 6 x_{3} & \geq 30, \\ x & \geq 0 . \end{aligned}

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.

max 25 y_{1} + 30 y_{2} s.t. \begin{aligned} 3 y_{1} + 2 y_{2} & \leq 120, \\ y_{1} + 4 y_{2} & \leq 100, \\ y & \geq 0 . \end{aligned}

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.

max 0.07 w_{1} + 0.04 w_{2} + 0.11 w_{3} s.t. \begin{aligned} w_{1} + w_{2} + w_{3} & = 1, \\ w_{j} & \geq 0.10 (j = 1, 2, 3), \\ w_{3} & \leq 0.25 . \end{aligned}

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.

Non-example

Four classifications that go wrong

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 $\leq$ , 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} \leq 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.

Contrast

The same ingredients, two shapes

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.

	"Meet the nutrient minima at least cost"	"With this month's stock, make the most valuable feed"
Shape	covering	packing
Objective	$min$ cost	$max$ value
Rows	$N x \geq r$ , nutrient floors	$I x \leq s$ , stock ceilings
A column means	what one unit supplies	what one unit consumes
Optimum expected	on the floors	on the ceilings
Characteristic failure	infeasible: floors unreachable	unbounded: a free ingredient
Adding an ingredient	can only lower cost	can only raise value

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.

Related units

Requires

Formulating a Linear Program

Connected

The Four Terminal Outcomes (related)

Learn this topic

Recurring Shapes of Linear Programs

Used in

Linear Programming

Sources

Introduction to Linear Optimization (1997)

Recurring Shapes of Linear Programs

Assumptions and scope

Worked material

One of each shape

Four classifications that go wrong

The same ingredients, two shapes

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history