Optimisation

Goal

Optimisation answers a question of proportions: what quantities to produce, what resources to assign to which use, which mix to settle on, when the feasible combinations are too many to compare one by one.

The deliverable comes in two parts. The optimal plan gives a value to each decision variable: produce so many of this and so many of that. The reading of the constraints says which of the limits is holding the result back and what loosening it by one unit would be worth. The second part opens the discussion with the decision-maker: a binding constraint with its shadow price turns "we are short of capacity" into an amount that can be set against the cost of buying more.

Usage

When to use it

• A shared resource: a workshop, a budget, a team to be split between uses that do not pay the same.
• An objective and limits that can be put in figures: a margin, a total cost, a gap to a target; measured capacities, contractual commitments, regulatory ceilings.
• Too many combinations to enumerate: from three or four variables on, comparing plans by hand stops working.
• A decision that comes round again: a monthly production plan, a daily delivery round, a roster; the model pays for itself at every run.
• A contested trade-off between departments: the discussion moves off preferences and onto the constraints and the objective.

When not to use it

• Several criteria with no common measure: weighing cost, risk and reputation against one another calls for multi-criteria decision analysis.
• Uncertainty that sits in the data rather than in the choice: business simulation returns a distribution where optimisation returns a point.
• A handful of options already listed: four supplier variants are settled in a decision matrix.

Description

The three elements and the model

The decision variables are the quantities the decision-maker controls: how many units of each item to produce, the hours assigned to each site, the share of each security in a portfolio. Each carries a type, which governs how hard the calculation is: continuous for a quantity taking any value in an interval, litres or hours; integer for objects counted in whole units; binary for an all-or-nothing decision, opening a site or not. In the training of a machine-learning model, that role falls to the weights given to the explanatory variables.

The objective function states in one formula what is to be made as large or as small as possible. A model carries exactly one. Depending on the field, it is called the decision function, the cost function or the loss function. An objective such as "maximise margin and minimise lead times" does not solve as it stands: one of the two becomes a constraint, or both enter a weighted sum whose weights are themselves a decision.

The constraints bound what is feasible. Each is written as an inequality or an equality over the decision variables: a capacity that caps, a delivery commitment that imposes a floor, a composition that has to add up exactly. The IIBA guide attaches the analyst's contribution to the constraints: they are uncovered through elicitation and in the business rules that business rules analysis documents.

The optimisation model is one objective line, a list of inequalities, a type declaration for each variable. That text is what the solver consumes. It fits on one page for most of a company's planning problems.

Writing the constraints

A usable constraint carries four pieces of information: the quantity being limited, how much of it each unit of each variable consumes, the bound and where that bound comes from. The first three are measurements. The fourth is the name of a person or of a document, failing which the constraint cannot be told apart from a figure put forward in a meeting.

The bounds come from different people: machine capacity from the workshop, the purchasing ceiling from procurement, the legal obligation from the lawyer. The consumption coefficients are measured on past production runs: an error in one moves the constraint line and therefore the coordinates of the optimal vertex. A coefficient of the objective function is more forgiving: it can often move by a quarter or more before the plan moves to another vertex. Implicit constraints are the costliest to leave out: a changeover time between two items, a minimum headcount per shift, an exclusivity clause that forbids mixing suppliers.

Two solver answers signal a faulty formulation rather than bad news. Infeasible means no combination satisfies all the constraints at once, because two limits contradict each other or an imposed minimum exceeds a capacity. Unbounded means the objective grows without end, the sign of a missing constraint, most often the one that caps demand or supply.

The decisive check is human. The optimal plan is shown to the people who would have to hold to it and they are asked whether they could. What they object to is the missing constraint, in their own words.

Two families under one name

The IIBA guide separates problems by the degree of uncertainty they carry.

When the objective and the constraints are linear, the problem belongs to linear programming: maximising or minimising a linear function over the convex region that linear inequalities cut out. George Dantzig devised its solution method, the simplex method, in 1947 on planning problems for the United States Air Force; the name "linear programming" goes back to Tjalling Koopmans in 1948. Polynomial-time algorithms followed: Khachiyan's ellipsoid method in 1979, then Karmarkar's interior point method in 1984. The IIBA guide notes its wide use in logistics, in production and in project management.

When the relationship stops being linear, the optimum is looked for step by step. A machine-learning model adjusts its weights to reduce a loss function by gradient descent, following at each iteration the direction of steepest decrease. The same holds for portfolio volatility: it depends on the composition through a relationship that is not proportional. The IIBA guide draws a limitation from this: the optimised solution is not necessarily the best solution that exists. It adds that these calculations consume machine time on large data sets.

Why the optimum sits on a vertex

With two variables the geometry can be drawn. Each linear constraint cuts the plane in two and keeps one half of it. The intersection of all those half-planes is the feasible region, a convex polygon holding every plan that can be carried out. The objective function traces a family of parallel lines on it, one per level of result. That family is slid towards higher values until its last contact with the polygon. That last contact is a vertex.

A vertex is the point where several constraints cross, so an optimal solution makes as many constraints binding as there are variables, non-negativity constraints included; that is what makes optimal plans so clear-cut, with product lines at zero where intuition expected a bit of everything. The simplex method exploits the same property: it moves from one vertex to a neighbour until none does better, so it never explores the inside of the region.

Reading the solution

A solver returns more than a plan. The value of each variable is the plan itself. The binding constraints are those the solution consumes right up to the bound; the others keep some slack, an unused reserve there is no point in enlarging. The shadow price of a binding constraint puts a figure on the gain in the objective function that one more unit of the resource would bring, to be set against the purchase price of that unit. The ranges of optimality say how far a margin or cost coefficient can move before the optimal plan moves to another vertex. The difference from the current plan is the only figure the committee will remember.

The traps

The implicit constraint

The IIBA guide counts the exact formulation of the constraints among the technique's prerequisites. A limit nobody thought to state, because it goes without saying on the floor, produces a plan that is mathematically optimal and operationally impossible. The plan is then rejected, and with it the method.

The proxy objective

Maximising this month's margin is easy to write and rarely what the company wants. The model will obey to the letter: it will drop a low-margin customer on whom a volume of after-sales work depends or fill a machine that is booked for servicing. What the objective leaves unsaid has to go into the constraints, as service floors or minimum shares.

Rounding the integers

Solving in continuous variables and then rounding is the commonest shortcut. It leaves the feasible region as soon as the constraints are tight: 80.4 units rounded to 81 exceed the capacity. Solvers handle integer variables natively, at a higher computational cost that stays modest on models of this size.

The solver's precision taken for the data's

A solver displays CHF 43'200 on margin coefficients estimated to within 10%. The number of decimals belongs to the machine, the reliability belongs to the inputs. The counter-measure is to replay the model with the coefficients at the ends of their range and see whether the plan holds, which is what sensitivity analysis covers.

The local optimum taken for the optimum

On a non-linear problem, a gradient descent stops at the bottom of the valley it found, without knowing whether a deeper one exists elsewhere. Restarting from several starting points and comparing where they land is the usual check. That precaution goes away in linear programming, where the convexity of the region guarantees that the optimum found is the global one.

The model nobody can explain

The IIBA guide sets this among the limitations: complex formulations are hard to explain to stakeholders. A decision-maker does not sign a plan when they cannot see where it came from. The counter-measure is to present the model through its constraints, which everyone recognises, before its machinery.

AI considerations

The first useful application is turning words into a formulation. A language model converts "we cannot go past 640 workshop hours a month" into an inequality over the declared variables and writes the few lines of code that call a solver. The result can be verified, since an optimisation model is a short text whose lines can each be checked against the constraint they claim to express.

The second is estimating the coefficients from past runs, the actual assembly time per item or the material consumption per unit: a statistical fit on data the company already holds. The third is generating variants: reformulate the objective, add a second shift, relax a ceiling, run the series of scenarios and present the differences. The fourth is putting the result into words from the binding constraints and the shadow prices, where the numbers are supplied and nothing is invented.

Two limits hold. The constraints belong to the organisation: a contractual clause, the capacity of a calibration bench, a ceiling in a cantonal permit. A language model proposes plausible ones, which speeds up the first list and does not replace validation by the person who answers for each figure. Asked "what is the optimal plan", a language model writes a plausible-looking plan without having solved anything: no constraint is guaranteed satisfied. That the training of such a model itself rests on an optimisation does not make it able to solve the reader's.

Examples

An electronics workshop in the Jura assembles two models of measuring instrument, Standard and Connected. Assembly and calibration go through the same resources and a radio module goes only into the connected model.

The reading that decides is the one on the two binding resources. One more hour of assembly is worth CHF 45, one more hour of calibration bench CHF 60, in a workshop with four people on assembly for a single bench running two shifts. The shadow price is compared with the purchase price of the unit, and the two units are not bought in the same way.

An hour of assembly is bought by the hour, as overtime or through an agency, at a known rate that can be set against the CHF 45. An hour of bench cannot be bought: the bench already runs eleven hours a working day, and the smallest quantity available on the market is a whole second bench, an investment to be written off over several years. So the resource to loosen first is assembly, despite its lower amount; the bench is an investment decision. Negotiating a larger quota of radio modules would return nothing, since that constraint is not binding.

The unit margins remain estimates. The CHF 75 to CHF 150 range is on the Standard margin coefficient, today CHF 120. Since the margin is the selling price less the variable unit cost, a revision of that cost moves the margin by the same amount in the opposite direction: as long as the margin stays inside those limits, the model is not reopened.

Visualisations

One thing alone calls for a drawing: the step from the constraints to the solution. The inequalities are written in rows and the solution in columns, but why the optimum lands on a vertex rather than in the middle of the region can only be read off a plane. The formulation and the reading of the result stay tables, each with its provenance or its interpretation alongside.

Cost

Tooling

The spreadsheet with a solver is the way in. Excel's Solver, developed by Frontline Systems, handles linear, linear integer, quadratic and non-linear problems. The IIBA guide cites it as a demonstration tool. Management accounting already reads the workbook, so a two-variable model shown there builds more confidence than a presentation of the method. LibreOffice Calc carries a comparable solver.

Programming libraries take over as soon as the model has to be versioned, replayed or wired into a system. PuLP and Pyomo in Python state the model in a syntax close to its algebraic form; scipy.optimize.linprog covers the simple linear case; Google's OR-Tools adds routing and scheduling problems; lpSolve does the same job in R. The code file becomes the documentation of the model.

Dedicated solvers sit behind those libraries when the size demands it: Gurobi, IBM CPLEX and FICO Xpress on the commercial side, HiGHS, CBC and GLPK on the open-source side. In industrial production, the advanced planning modules grafted onto an ERP carry the model natively, with the capacity and bill-of-materials data already in place. On the iterative side, machine-learning libraries such as scikit-learn, PyTorch and TensorFlow carry gradient descent and its variants.

Sources

• IIBA, Guide to Business Data Analytics, §3.14 Optimization: the definition, the three elements and their assembly into a model, the split between low and high uncertainty, the analyst's role in uncovering the constraints, the strengths and the limitations.
• MacTutor History of Mathematics, George Dantzig, University of St Andrews: the design of the simplex method in 1947 on military planning problems and the attribution of the name "linear programming" to Tjalling Koopmans in 1948.
• Wolfram MathWorld, Linear Programming: the standard form of the problem, the convex region defined by the inequalities, the simplex method, Khachiyan's ellipsoid method and Karmarkar's interior point method, both in polynomial time.
• Frontline Systems, Linear Programming in Excel: the documentation from the designers of Excel's Solver and the scope of problems its engines handle.