Driving a Linear Programming Solver

A correctly formulated program and a correctly operated solver can still produce the wrong answer, because the two have to agree about conventions neither one states.

A solver that minimises will accept a maximisation's coefficients without complaint and return the worst available plan, reporting success. A constraint entered in the wrong array describes a restriction the situation does not have. Neither is a modelling mistake or an arithmetic mistake; both are failures of translation at the boundary between a model and an interface.

This is applied practice rather than theory. Nothing else in the subject depends on it, and the specific menus and argument orders will change. What survives is the habit of asking what convention a tool imposes, and of reversing every conversion made on the way in.

Before touching the tool. Write the model on paper: variables with units, objective with a direction, every constraint with its direction and right-hand side. Everything below is translation, and translating an unfinished model produces a confident answer to an unasked question.

Step 1: read the tool's convention. Three questions, answered from the vendor's documentation rather than from memory:

• Which direction does it optimise, and can that be changed?
• How are constraint directions expressed, separate arrays for inequalities and equalities, a comparison operator per row, or a required rewriting?
• Are variables nonnegative by default, or must bounds be stated?

Step 2: convert. Apply exactly the conversions the answers demand. Negating the objective to match a minimising tool, moving equalities into their own array, stating $x\ge 0$ explicitly where it is not assumed. Record each conversion, because each must be reversed on the way out.

Step 3: fix the correspondence. Decide which column index is which decision variable and which row is which constraint, and write it down. Every array must use the same order. This mapping exists nowhere in the tool.

Step 4: enter and run. Supply the arrays. Check the shapes agree before running: the objective vector's length is the number of variables, each constraint row has that same length, and the right-hand side has one entry per row.

Step 5: read the status first. Before looking at any number, read what the solver claims: an optimum found, infeasible, unbounded, or a limit reached. A point reported alongside a non-optimal status is not an answer, and on a limit status it is the best found so far rather than the best there is.

Step 6: reverse the conversions. Map the returned components back to named decisions. If the objective was negated, negate the reported value. If a variable was split or shifted, reassemble it.

Step 7: verify against the original model. Substitute into the constraints as first written, recompute the objective, and judge whether the status is credible. These checks belong to verification and are applied here to the original model, never to the solver's restatement of it. A transcription error is invisible to any check performed on the transcription.

The model. A workshop makes two products. Each unit of A takes 2 machine-hours and 1 labour-hour and contributes £30; each unit of B takes 1 and 1 and contributes £20. There are 100 machine-hours and 80 labour-hours, and at most 40 units of A can be sold.

Step 1: the convention. The tool minimises, takes inequalities as $Ax\le b$ in one array, equalities in another, and requires bounds to be stated explicitly.

Step 2: convert. The objective is a maximisation, so negate it:

The conversion to record: objective negated; the reported value must be negated back. All three constraints are already $\le$, so they need no change. There are no equalities. Bounds are $a,b\ge 0$ with no upper bounds. The limit $a\le 40$ is a constraint row here, though it could equally be stated as an upper bound; either is correct provided it appears exactly once.

Step 3: the correspondence. Column 1 is $a$, units of product A per week. Column 2 is $b$, units of B. Row 1 is machine-hours, row 2 labour-hours, row 3 the sales limit on A.

Step 4: the arrays.

Shapes agree: $f$ has 2 entries for 2 variables, $A$ is $3\times 2$, $b$ has 3 entries for 3 rows.

Step 5: the status. The solver reports an optimum found. Proceeding.

Step 6: the reported answer, and reversing. The solver returns $x=(20,60)$ and objective $-1800$.

Reversing the one recorded conversion: the objective was negated, so the contribution is $-(-1800)=1800$. Reading the correspondence back: make 20 units of A and 60 units of B, for a contribution of £1,800 per week.

Reporting $-1800$ as the answer would be the characteristic error here. A negative contribution from a profitable plan, which is the signal that a conversion was not reversed.

Step 7: verify against the original model.

• Machine-hours: $2(20)+60=100\le 100$ (binding)
• Labour-hours: $20+60=80\le 80$ (binding)
• Sales limit: $20\le 40$ (slack of 20)
• Nonnegativity: both positive
• Objective: $30(20)+20(60)=600+1200=1800$, matching the reversed value

What the check found beyond agreement. Both resource constraints bind and the sales limit does not. So the plan is limited by capacity, not by demand, and the question worth asking next is what an extra machine-hour or labour-hour would be worth. A sensitivity question the solver can answer, and one that would be misdirected if the binding pattern had been misread.

What is not established. That 100 and 80 are this week's real capacities, that contributions are genuinely linear in volume, or that A and B are the only products competing for these hours. The solver was never in a position to check any of them.

Details below follow each vendor's own documentation and will drift; the conventions are the point, not the keystrokes.

MATLAB linprog. The routine solves a minimisation, with the problem expressed as a coefficient vector and separate arrays for inequality constraints, equality constraints and bounds:

The consequences for a modeller are three. A maximisation is entered as $-f$ and the returned value negated. Equalities go in their own array, and putting an equality into the inequality array asserts only half of it. Nonnegativity is not assumed, it is stated as $\ell =0$, so omitting bounds allows negative production. The routine returns the point, the objective value at it, and an exit flag distinguishing an optimum from infeasibility, unboundedness and a limit reached.

Excel Solver. The model lives in cells rather than arrays. Decision variables are a range of changing cells, the objective is a formula cell referring to them, and each constraint is a row in a dialog naming a cell, a relation and a bound. The direction is chosen explicitly as Max, Min or a target value, so no negation is needed.

Two conventions matter more here than the arithmetic. The solving method must be set to the linear option for a linear program. The default is a nonlinear method that may stop at a point it cannot certify as optimal. And nonnegativity is a checkbox, not an assumption, so leaving it clear permits negative values in the changing cells.

Because the model is formulas over cells, a mis-typed cell reference produces a different program that still computes. This is the analogue of a positional error in an array interface, and it is harder to see: the spreadsheet displays values rather than the relationships between them.

What the two share. Each fixes a direction convention, a place for each kind of constraint, and a default about sign restrictions, and in each, the correspondence between positions and decisions exists only in the modeller's notes.

A status of optimal is a claim about one thing: the solver found the best point of the program it received. Four things it is regularly taken to mean, and does not.

That the program is the model you wrote. A transcribed coefficient, a constraint entered in the wrong array, a missing row. Each yields a valid program with a genuine optimum. The status reports on the transcription, and no check performed inside the tool can compare it against your intent.

That the data is right. A capacity of 1,000 entered as 10,000 optimises perfectly against a factory that does not exist. Dimensional errors survive too: a rate per hour against a budget per week is arithmetic the solver will do without objecting.

That the model represents the situation. Linearity, certainty of the data, and divisibility of the variables are modelling assumptions. A plan of 20.4 lorries is optimal for the program and unimplementable.

That the answer is unique. Many linear programs have a face of optima. The solver returns one of them, and a second run with different settings may return another with the same objective value. Treating the reported point as the answer, rather than an optimal answer, misleads anyone who has to act on which routes or products were chosen.

The one exception worth naming. A status of infeasible is more informative than it looks, because it is often a claim about the transcription rather than about the situation. Before concluding that a business problem has no solution, check the entry: a reversed inequality or a constraint in the wrong array makes a perfectly feasible situation unsatisfiable.

Numerical tolerance. A reported point may satisfy constraints only to within a tolerance. A value of $79.9999999$ against a limit of $80$ is a floating-point artefact, not a breach; a value of $85$ is a breach. Deciding which you are looking at requires knowing the tolerance the tool used, and it is why verification compares against the original model with a stated tolerance rather than demanding exact equality.

The error profile inverts. Hand computation fails noisily: a wrong ratio test produces an infeasible point that the next step exposes. Tool use fails silently, because the tool has no view of what you meant and every syntactically valid program has an answer.

Why hand methods are still learned. Not as a substitute, nobody pivots a thousand-variable program by hand, but because the reported output is written in their vocabulary. A shadow price is a dual variable; a degenerate warning is a basic variable at zero; a variable at its bound is nonbasic. Without the methods, those outputs are strings rather than information.

What the tool adds that hand methods cannot. Sensitivity analysis on a realistic model, re-solving under changed data in seconds, and scale. The workshop example's binding pattern, capacity limiting, demand not, invites asking what an extra machine-hour is worth, and that question is answerable in one further run.

Where the competences meet. Verification is the same work in both cases: substitute into the constraints as written, recompute the objective, judge the status. The difference is that a hand solution's arithmetic is also open to inspection, whereas a solver's is not, which makes verification against the original model more important with a tool, not less.