What Is an Optimisation Problem? Finding the Best Option You Can Afford to Find

Every optimisation problem has the same structure. Decision variables are the things you control, such as how much of each product to make or which vehicle covers which route. The objective function is the single quantity being maximised or minimised, such as profit, cost, time or risk, and reducing a real situation to one number is frequently the hardest and most contested step, since organisations rarely want only one thing. Constraints are the conditions any acceptable answer must satisfy, including available materials, working hours, capacity, legal limits and the requirement that quantities not be negative. Together these define a feasible region containing every allowable combination, and the task is finding the point in that region where the objective is best. Stating a problem in this form is itself the substantial work, and a poorly specified objective will be optimised faithfully into an outcome nobody wanted, which is a failure mode with many real examples.

Problems that look similar can differ enormously in difficulty:

• •Linear programming, where the objective and constraints are all linear, is efficiently solvable even with enormous numbers of variables, and the simplex method developed by George Dantzig in 1947 made industrial-scale planning possible
• •Convex problems, a broader class with a single bottom to the valley, are reliably solvable because any local minimum is the global one
• •Non-convex problems have multiple local minima, so an algorithm can settle into a solution that is better than everything nearby and far from the best available
• •Integer programming, requiring whole-number answers because you cannot build half a factory or assign a third of a driver, is dramatically harder than its continuous version and is where many practical scheduling problems sit
• •Combinatorial problems, choosing among a finite but astronomically large set of arrangements, include routing and packing and are frequently computationally hard
• •Stochastic problems, where the inputs are uncertain, require optimising an expected outcome or a worst case rather than a known quantity

When exact solution is impractical, the approach shifts to finding a good answer and knowing how good it is. Heuristics apply sensible rules that usually work without guarantees, such as always serving the nearest unvisited customer. Metaheuristics search the space of solutions systematically while allowing occasional moves to worse positions in order to escape local minima, including simulated annealing, which is modelled on the physical process of cooling a metal slowly so its atoms settle into a low-energy arrangement, and genetic algorithms, which combine and mutate candidate solutions. Relaxation solves an easier version, typically by dropping the integer requirement, which gives a bound showing how far the best possible answer could be from what has been found. Branch and bound divides the space systematically and discards regions that cannot contain the optimum. Modern commercial solvers combine these and routinely handle problems that were intractable a few decades ago, which is why airline scheduling and logistics planning now operate at scales that would previously have been impossible.

Optimisation underlies far more of daily life than is visible: airline crew rostering and fleet assignment, delivery routing, electricity generation dispatch, portfolio construction, factory scheduling, telecommunications network design, and the training of machine learning models, which is optimisation of a very high-dimensional non-convex objective. The characteristic failure is not computational but definitional. Optimising a single measurable objective tends to sacrifice everything unmeasured, so a rota optimised purely for cost produces schedules people cannot live with, and a system optimised for one metric reliably degrades the things that metric does not capture, which is the mechanism behind Goodhart's observation that a measure used as a target stops being a good measure. Robustness is the related issue, since a solution sitting exactly at the optimum is frequently fragile, performing badly under small changes in conditions, which is why practitioners increasingly optimise for acceptable performance across a range of scenarios rather than for the best outcome under one.

An optimisation problem has decision variables, one objective and constraints defining what is allowed, and reducing a real situation to a single objective is the hardest step. Linear and convex problems are reliably solvable, while non-convex, integer and combinatorial ones are dramatically harder, which is why practical scheduling is difficult. Heuristics, simulated annealing and branch and bound find good answers with bounds on how good. The usual failure is optimising a measure that leaves out what matters.