Back to the on-screen lesson ·
Choosing a method from three questions, re-solving rather than solving, and reporting exactly what was established.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to classify a problem — continuous or discrete, convex or not, how large — and pick the method that fits from that alone; to run a study in the order its stages depend on each other; and to write a report that contains the recommendation, the strength of claim the run actually supports, the constraints worth relaxing, the inputs the answer depends on, and what the model could not see. You will also be able to say why a model is re-solved rather than solved, and to recognise the problems where building one earns nothing.
All of it. Formulating, convexity and optimality conditions, the continuous and discrete methods, and the honest handling of several objectives and of uncertainty. This lesson puts the pieces in the order they are used, and says what a finished piece of work looks like.
Classification decides the method. Three questions, asked before anything is chosen:
| Method | ||
|---|---|---|
| Continuous, convex, linear | any size | simplex or interior point |
| Continuous, convex, smooth | small $n$ | Newton |
| Continuous, convex, smooth | large $n$ | quasi-Newton, limited memory |
| Continuous, non-convex | any | local method, reported as local |
| Discrete, with a decent relaxation | moderate | branch and cut |
| Discrete, no usable bound | large | heuristic, reported as such |
Nothing about the application enters this. A routing problem and a scheduling problem with the same three answers get the same method.
Every method promises one of three things: a global optimum, a local one, or a feasible answer with a bound on how far from optimal it might be. Reporting the output of a method that promises the third as though it promised the first is the most expensive mistake in this subject, and it is made in words, not in arithmetic.
The data drifts. Costs, capacities and demands are measurements of a world that keeps moving. A plan is only as current as the data behind it, and nothing about an optimum degrades with time — the arithmetic stays correct while the question it answered goes out of date. Re-solving is not maintenance; it is how a model is used. A study that produces a plan and no way of producing the next one has produced half of what was needed.
And optimization earns nothing on some problems. Where the choices do not interact, sort the list. Where the objective cannot be written down honestly, the analysis will optimise whatever was written instead. Both are reasons to stop, and recognising them is as much a part of this subject as any method in it.
Another way: picture
A loop rather than a line: formulate, classify, solve, interpret, recommend — and then back to formulate, because the data has moved and someone has noticed a constraint that was missing. A study that runs the loop once has built a report; one that can run it again has built something usable.
Another way: steps
A whole study:
Not a number. Five things:
The recommendation, in the language of the decision rather than of the model — lease six thousand square feet at the northern site, not $x_3 = 6000$.
What is guaranteed. Optimal, because the problem is convex and was solved exactly. Or: within $2\%$, because the branch-and-bound gap closed to there. Or: feasible, with no optimality claim, because a heuristic produced it. These are three different sentences and only one of them is true of any given run.
What it is worth relaxing. The short list of binding constraints, their shadow prices, and the ranges those prices hold over.
What the answer depends on. Which inputs can move without changing the decision, and which cannot.
What the model could not see. Every model has a boundary, and the person acting on it needs to know where it is — because inside the boundary the model is authoritative, and outside it the model is silent while still producing numbers.
Reporting a number without its conditions. The failure that makes optimization untrustworthy to the people who have to act on it.
Solving once. A model with no re-solve path is a report; the value was in the ability to answer the question again next month.
Optimising a proxy nobody checked. The objective gets maximised whether or not it is what was wanted, and the mismatch surfaces as a recommendation people resist for reasons they cannot articulate.
Reaching for a model where a list would do. If the choices do not interact, there is nothing to optimise.
Letting the method choose the claim. The claim is decided by what was established before the run, and no amount of computation changes it.
Thirty lessons of methods make it easy to think the difficulty lives in the solving, and it does not — solvers are excellent and getting better, and the method is usually chosen by three questions with obvious answers. The difficulty is on either side of it. Before: deciding what is actually being chosen, what is actually being judged, and which rules are real — and noticing the constraint everyone in the building knows about that nobody wrote down. After: saying what was established without saying more, attaching the conditions, and knowing that the plan is only as current as the data behind it. A model whose formulation is right and whose report is honest is useful even when solved crudely; one with neither is a confident wrong answer, and it will be believed.
Convex, solved exactly: "Lease 6,000 sq ft north. This is optimal for the model, which assumes demand of 400 units a week and treats haulage cost as linear in distance."
Optimal, with the assumptions that make it so.
Integer, stopped at a gap: "Open sites 2, 5 and 9, at a cost of £412k. No configuration costs less than £404k, so this is within 2% of the best possible."
Bounded, with the bound stated.
Heuristic, no bound: "A feasible schedule with makespan 47, found by local search in the two minutes available. No bound was computed, so how close this is to the best possible is not known." Three runs, three different strengths of claim, and each sentence says exactly what its run supports.
Unbounded, and labelled.
Choose the cheapest of four quotes for one item. No interaction between the choices: sort and read the top. There is no model here worth building.
Sorting is the right method.
Choose which of four suppliers to build a relationship with. The objective is trust, reliability and flexibility over years. Nothing honest can be written as a single number, and writing one anyway does not make it true.
The objective cannot be written.
Split an order across four suppliers with capacities, minimum orders and a budget. The choices interact, the objective is cost, and the constraints are real. This is the one to model — and recognising which of the three you are looking at is the first thing this course taught and the last thing it is worth saying.
And this one is a model.
A convex quadratic program, solved with an interior point method, reported with a duality gap of $10^{-9}$. Convex objective, convex feasible set, and a gap that has effectively closed.
Check the two hypotheses, then the gap.
So: optimal. The gap is a proof, not an estimate, and the convexity was established before the run rather than inferred from it.
Now change one thing — five of the variables must be integers. The objective is unchanged and still convex; the feasible set is not. The same solver on the relaxation now supports only "a bound", and an honest claim needs branch and bound and whatever gap it reaches. One line of the model moved, and the sentence at the end of the report changed with it.
The problem is a linear objective, linear constraints, and forty variables that must be $0$ or $1$. Which method fits?
A plan was built on data $22$ days old, and it has now been in use for $88$ days. How old is the data the plan still rests on?
Answer:
Put the stages of an optimization study in order.
Number the steps in order (write the number in the box):
A branch-and-bound run stops at a $2$ percent gap with a plan worth $276$. What should the report say?
The problem is a linear objective over linear constraints, ten thousand variables. Which method fits?
Across this whole course, what decides whether a converged method's answer may be called optimal?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A plan was built on data $10$ days old, and it has now been in use for $30$ days. How old is the data the plan still rests on?
Answer:
You can classify a problem, choose a method, and report what a run established without overstating it. That is the course: formulate honestly, establish convexity or get a bound, and say exactly what you have.
9. Your turn: what is the strongest honest claim?, step 3