Formulating Optimization Problems
A solver can only answer the question you actually ask it. The hardest — and most valuable — step in optimization is rarely the arithmetic; it is turning a messy real decision into three precise mathematical objects: the variables you may set, the single quantity you want best, and the rules you must respect. This chapter is a workshop in that craft — the three-step recipe, the standard form every solver expects, the modeling tricks that tame awkward requirements, and the classic templates you will meet again and again.
- The three-step recipe for formulation: define the variables, write the objective, express the constraints.
- How to choose good decision variables — continuous, integer, or binary — and index them cleanly.
- The four working kinds of constraint: resource (\(\le\)), requirement (\(\ge\)), balance (\(=\)), and simple bounds.
- How to reach LP standard and canonical form using slack, surplus, and free-variable splitting.
- Modeling tricks that linearise awkward requirements: maximization, absolute values, minimax, and fixed-charge (binary) logic.
- The classic templates — product mix, diet/blending, transportation, assignment, and knapsack — that recur across engineering.
Why Formulation Matters
Chapter 1 named the three ingredients of any optimization problem. This chapter is about assembling them — the skill of formulation, or mathematical modelling. It is where most of the real difficulty (and most of the exam marks) actually lives. A perfect algorithm applied to a wrong model gives a wrong answer with total confidence; a rough algorithm applied to a faithful model still points you in the right direction. The model is the leverage point.
Formulation follows one disciplined recipe, applied in order. First decide what you may choose and give each choice a symbol — the decision variables. Then write the single number you are trying to make best — the objective. Finally list every rule the choice must obey — the constraints. Only when all three are on paper is the problem "well-posed" and ready for a method.
Always in this order. You cannot write an objective until you know what the variables are, and you cannot write constraints until you know both. Skipping straight to equations is the commonest source of a broken model.
Step 1 — Choosing the Decision Variables
The decision variables are the quantities you are free to set; everything else in the model is expressed in terms of them. Good variable choice is half the battle. Each variable needs a clear meaning and explicit units — "let \(x_j\) be the tonnes of alloy \(j\) produced per day" is a variable; "let \(x\) be production" is a future bug. Use indices for families of similar quantities: \(x_j,\ j = 1,\dots,n\).
Variables come in three flavours, and the flavour decides which part of the book solves the problem. Continuous variables take any real value in a range (a flow rate, a length). Integer variables take whole numbers (how many trucks). Binary variables \(y \in \{0,1\}\) encode yes/no decisions (build the plant or not) and are the key to modelling logic.
Binary variables turn words like "either/or", "if we open it", and "at most three of these" into arithmetic. Introducing even one integer or binary variable moves a problem from the (easy) linear-programming world into the (harder) integer world of Part 4 — so add them only when the decision genuinely is discrete.
Step 2 — Writing the Objective Function
The objective is the one scalar that ranks any two feasible choices. It must be a single number: cost, profit, weight, time, error, energy. When it is a weighted sum of the variables — the most common case — we write it compactly as
where \(c_j\) is the cost (or profit) coefficient of variable \(x_j\). Two cautions. First, the objective must contain every variable that affects goodness and only the goodness measure — do not smuggle a constraint into it. Second, if you find yourself wanting two objectives at once ("cheap and light"), you have a multi-objective problem: either combine them into one weighted objective now, or defer to the Pareto methods of Chapter 27. A single run of any solver optimizes exactly one scalar.
Step 3 — Expressing the Constraints
Constraints carve the feasible region out of all conceivable choices. In practice they come in four working kinds, and recognising which is which is the fastest route to a correct model.
| Kind | Form | Reads as | Example |
|---|---|---|---|
| Resource / capacity | \(\mathbf{a}^{\mathsf T}x \le b\) | "use no more than" | Machine hours available |
| Requirement / demand | \(\mathbf{a}^{\mathsf T}x \ge b\) | "supply at least" | Minimum nutrient, meet demand |
| Balance / conservation | \(\mathbf{a}^{\mathsf T}x = b\) | "must equal" | Flow in = flow out |
| Bounds | \(\ell \le x_j \le u\) | "between limits" | \(x_j \ge 0\), tank 0–100% |
Almost every real restriction is one of these. The near-universal non-negativity bound \(x_j \ge 0\) is so common it is easy to forget — and forgetting it lets a solver "produce" negative tonnes of steel. When a decision is logical rather than numerical ("if we open the depot, it can ship up to \(M\) units"), a binary variable links to a continuous one through a constraint such as \(x \le M y\); we return to this in Section 2-6.
Standard and Canonical Forms
Solvers expect a tidy input. The standard form of a linear program minimizes, uses only equalities, and keeps all variables non-negative; the canonical form is the "\(\le\), maximize" shape used to set up the simplex tableau in Part 2. Any problem converts to either using a handful of mechanical moves.
| Have | Move | Get |
|---|---|---|
| \(\max\ f\) | negate objective | \(\min\ (-f)\) |
| \(\mathbf{a}^{\mathsf T}x \ge b\) | multiply by \(-1\) | \(-\mathbf{a}^{\mathsf T}x \le -b\) |
| \(\mathbf{a}^{\mathsf T}x \le b\) | add slack \(s\ge 0\) | \(\mathbf{a}^{\mathsf T}x + s = b\) |
| \(\mathbf{a}^{\mathsf T}x \ge b\) | subtract surplus \(s\ge 0\) | \(\mathbf{a}^{\mathsf T}x - s = b\) |
| \(x\) free (any sign) | split \(x = x^{+} - x^{-}\) | \(x^{+},\, x^{-} \ge 0\) |
The slack \(s\) is not just algebraic bookkeeping — it is the amount of that resource left over. When \(s = 0\) the constraint is active (fully used); when \(s > 0\) there is spare capacity. Reading slacks after solving tells you which resources are the bottlenecks.
Modeling Tricks and Transformations
Many requirements look nonlinear or logical at first glance but can be reshaped into the clean linear form solvers love. Four tricks cover a great deal of ground.
Maximize as minimize. As in Chapter 1, \(\max f = -\min(-f)\). Absolute value. To minimize \(|x|\), introduce \(t\) and write \(\min t\) with \(t \ge x\) and \(t \ge -x\); at the optimum \(t = |x|\). Minimax. To minimize the worst of several terms, \(\min_x \max_i f_i(x)\), introduce a single ceiling \(t\) and push it down:
Fixed-charge / logical links. When producing anything of product \(j\) triggers a one-off setup cost \(F_j\), introduce a binary \(y_j\) and couple it to the continuous amount \(x_j\) with a big-M constraint. Then charge the setup only when \(y_j = 1\):
If \(y_j = 0\) the link forces \(x_j = 0\) (nothing made, no setup charged); if \(y_j = 1\) then \(x_j\) may rise up to the large bound \(M\) and the setup \(F_j\) is paid. Choose \(M\) just large enough to never bind on its own — an unnecessarily huge \(M\) weakens the model and slows the solver.
Classic Formulation Templates
A handful of templates reappear across nearly every application area. Recognising which one a new problem resembles gives you its variables, objective, and constraints almost for free.
Choose how much of each product to make to maximize profit subject to shared resource limits. Variables = quantities; constraints = \(\le\) capacities.
Choose amounts of ingredients to minimize cost while meeting quality or nutrient requirements (\(\ge\)) and sometimes composition balances (\(=\)).
Ship from supplies to demands at least total cost. Balance constraints at every source and sink; the subject of Chapter 12.
Match \(n\) agents to \(n\) tasks one-to-one at least cost — binary \(x_{ij}\) with one-per-row and one-per-column constraints (Chapter 13).
Pick a subset of items to maximize value within a capacity or budget — binary variables and a single \(\le\) constraint (Chapter 15).
Choose shifts or facilities so every requirement is covered at least cost — \(\ge 1\) covering constraints with binary choices.
Worked Examples
Problem. A plant makes alloys A and B, earning ₹500 and ₹400 profit per tonne. Each tonne of A needs 2 h of furnace and 1 h of rolling; each tonne of B needs 1 h and 3 h. Only 100 furnace-hours and 90 rolling-hours are available per day. Formulate.
Solution. Let \(x_1, x_2 \ge 0\) be tonnes of A and B per day.
Every coefficient came straight from the table of resource usage — the recipe (variables, then objective, then constraints) turned the paragraph into a linear program almost mechanically.
Problem. Two foods cost ₹4 and ₹3 per unit. Each unit of food 1 gives 2 g protein and 2 g calcium; each unit of food 2 gives 1 g protein and 4 g calcium. A meal must supply at least 8 g protein and 12 g calcium. Formulate to minimize cost.
Solution. Let \(x_1, x_2 \ge 0\) be units of each food.
Note the requirements are "\(\ge\)" — the mirror image of the product-mix "\(\le\)". The word "at least" made the direction.
Problem. Put into LP standard form: \(\max\ z = 3x_1 + 2x_2\) s.t. \(x_1 + x_2 \le 4\), \(x_1 - x_2 \ge 1\), \(x_1 \ge 0\), \(x_2\) free.
Solution. Negate the objective; add slack \(s_1\) to the "\(\le\)"; subtract surplus \(s_2\) from the "\(\ge\)"; split the free variable \(x_2 = x_2^{+} - x_2^{-}\).
Now everything is a minimization over equalities with non-negative variables — exactly what the simplex method of Part 2 expects.
Problem. Reformulate \(\min_x \max(2x,\ 8 - x)\) as a linear program and solve it.
Solution. Introduce a ceiling \(t\):
Pushing \(t\) as low as possible forces both constraints tight, so \(2x = 8 - x \Rightarrow x^\star = \tfrac{8}{3}\) and \(t^\star = \tfrac{16}{3}\). This is exactly the bottom of the V-shaped envelope in the figure above — the worst of the two terms is made as small as it can be.
Problem. A product costs ₹20 per unit to make, plus a one-off ₹500 setup if any is made at all. At most 60 units can be produced. Write the cost model.
Solution. Let \(x \ge 0\) be units made and \(y \in \{0,1\}\) signal "we produce."
If \(y = 0\), the link \(x \le 0\) forces \(x = 0\) and no setup is paid. If \(y = 1\), then \(x\) may reach 60 and the ₹500 is charged once. The binary variable is what makes "pay only if we produce" expressible.
Problem. A drone can carry 10 kg. Four sensor packages have values (₹) 60, 100, 120, 80 and weights (kg) 2, 5, 4, 3. Choose packages to maximize value within the weight limit.
Solution. Let \(x_j \in \{0,1\}\) mean "carry package \(j\)."
This is the classic 0–1 knapsack — one capacity constraint, all-binary variables. It looks tiny but is genuinely combinatorial, which is why Part 4 devotes real machinery to it.
Chapter Summary
Formulate in order: variables → objective → constraints. The model, not the algorithm, is the leverage point.
Continuous, integer, or binary; binaries encode yes/no logic and raise difficulty.
Resource (\(\le\)), requirement (\(\ge\)), balance (\(=\)), and bounds — read the verbs to pick the type.
\(\min\ c^{\mathsf T}x\), \(Ax=b\), \(x\ge0\) via slack, surplus, and free-variable splitting.
Max→min, absolute value, minimax epigraph, and fixed-charge big-M links.
Product mix, diet/blending, transportation, assignment, knapsack, covering.
Problems
For each item, apply the three-step recipe explicitly: define the variables (with units), write the objective, then the constraints. Difficulty rises down the list.
- A carpenter makes chairs (profit ₹150) and tables (profit ₹400). A chair needs 3 h; a table needs 5 h; 40 h are available weekly. Wood allows at most 10 pieces total. Formulate the profit-maximizing mix.
- Rewrite in LP standard form: \(\max\ 2x_1 + 5x_2\) s.t. \(x_1 + x_2 \le 6\), \(x_1 \ge 2\), \(x_1,x_2 \ge 0\).
- Three grades of coal with costs and sulphur contents must be blended into 100 t of feed with average sulphur ≤ 2%. Formulate the least-cost blend (state the balance and quality constraints).
- Reformulate \(\min_x |x - 3| + |x - 7|\) as a linear program using two ceiling variables.
- Reformulate \(\min_x \max(x,\ 6 - 2x,\ 1)\) as an LP and find \(x^\star\).
- A factory may run machine \(k\) only if it is switched on (setup cost \(F_k\)); running it produces up to \(C_k\) units at unit cost \(c_k\). Write the fixed-charge model for three machines meeting a demand \(D\).
- Five projects have costs and expected returns; the budget is ₹50 lakh and at most three projects may be chosen. Formulate the return-maximizing selection (capital budgeting).
- Explain, with a one-line model fragment each, how you would encode: (a) "choose at least two of options 1–4", (b) "if project A is chosen then project B must be too".
- A power utility must dispatch three generators to meet a fixed load exactly, minimizing total fuel cost; each has a min and max output. Formulate (state which constraints are \(=\), which are bounds).
- Convert to standard form and identify the slack/surplus for each row: \(\min\ x_1 + x_2\) s.t. \(x_1 + 2x_2 \ge 4\), \(3x_1 + x_2 \le 6\), \(x_1 - x_2 = 1\), \(x \ge 0\).
- Give the general 0–1 knapsack model for \(n\) items with values \(v_j\), weights \(w_j\), and capacity \(W\), then state what changes if an item may be taken in any non-negative integer quantity.
- A delivery firm has 4 vans and 4 zones; assigning van \(i\) to zone \(j\) costs \(c_{ij}\). Formulate the least-cost one-to-one assignment with binary \(x_{ij}\), writing the row and column constraints, and explain why the non-negativity of \(x_{ij}\) alone (dropping the integrality) still tends to give 0–1 solutions here.