Rows, Columns, and What They Cost

TL;DR

• There is no universal formula that reliably converts a new LP into wall-clock seconds. Worst-case bounds, condition measures and empirical estimates exist, but they depend on the algorithm, tolerance, implementation, machine and problem family.
• Rows, columns and non-zero coefficients all matter, but none is a difficulty score. Dimensions help determine the sizes of the linear systems; non-zeros measure stored direct coupling. Percentage density can fall while both the model and the work grow.
• Where the non-zeros sit—and the values they contain—can matter more than their count. Fill-in, scaling, conditioning, degeneracy, presolve and algorithm choice can dominate memory and time.
• Polynomial-time describes worst-case scaling with the problem description and requested accuracy. It is not a stopwatch prediction, nor a guarantee enjoyed by familiar simplex pivot rules.

The first piece followed George Stigler's diet problem from a hand-built answer to a proof. In 1945 Stigler asked for the cheapest combination of foods that would meet nine minimum nutritional requirements. He had 77 foods to choose from, no general method for finding the minimum, and enough economic instinct to get remarkably close by inspection.

His basket cost $39.93 a year. Two years later, by George Dantzig's later account, nine clerks at the National Bureau of Standards spent about 120 man-days putting the full problem through the new simplex method. They found a diet costing $39.69. The twenty-four cents was not what justified the labour. The calculation also produced nine shadow prices which, multiplied by the nutrient requirements and added, matched the cost of the diet. The basket and the prices certified one another: no cheaper diet satisfying all nine requirements existed.

That established what optimal meant, but it left the machine closed. What did the simplex method actually receive, and what did the size of that input say about the work ahead? Start with Stigler's table of 77 foods and nine nutrients. To turn it into the matrix an optimiser uses, put one nutrient requirement in each row and one food choice in each column. The result has nine rows, 77 columns and 693 cells.

Four objects make one model

An optimisation model begins with three kinds of ingredients. The variables are the numbers the solver may choose: here, 77 daily expenditures, one for each food. The objective is the single quantity to minimise: the sum of those expenditures. The constraints are the promises every answer must keep: one minimum for each of nine nutrients. A diet is feasible if it keeps all nine promises; it is optimal if no feasible diet costs less.

In symbols, the variables form a vector x. Because each entry of x is already an expenditure, the objective c^Tx uses a vector c containing 77 ones: it simply adds the expenditures. The nine constraints are collected in Ax ≥ b: A is the nutrient table and b contains the nine required floors.

One coefficient records how one variable affects one constraint. The calorie–flour coefficient is 44.7: one dollar spent on flour supplies 44.7 thousand calories. The vitamin-A–flour coefficient is zero in this table, so flour contributes nothing recorded to that requirement. If a coefficient is non-zero, the decision is directly connected to the requirement. I will call that connection a touch: a column touches a row when their coefficient is non-zero.

Stigler's nutrient table contains 570 non-zero coefficients. Its density is the share of the rectangle that is filled: 570 divided by 693, or 82.3 per cent. We now have several descriptions before an algorithm has done anything. Rows count promises, columns count choices, non-zeros count direct relationships, and density gives the fraction of possible relationships that are present. None is, by itself, a difficulty score.

Ninety-eight models on the same shelf

To know whether 82.3 per cent tells us anything, we need a comparison set. Netlib is a public archive of numerical software and test data. Its linear-programming directory supplies 98 named problems that solver developers can run against the same recorded answers.[1] That makes it a benchmark—a repeatable test shelf—not a random sample of every model used in industry.

Each problem on that shelf has a short file name. AFIRO is the smallest entry in the summary table, contributed from Stanford's Systems Optimization Laboratory: 28 rows by 32 columns. The archive records its provenance but does not explain what the name expands to or what application, if any, sits behind it. STOCFOR3 is documented more fully. It is the third and largest of a family of seven-period forestry-planning models in which forest fires are random: 16,676 rows by 15,695 columns. AFIRO and STOCFOR3 are not algorithms or technical terms. They are two named test files, one small and one large.

One bookkeeping choice matters before we compare. Netlib includes the objective coefficients in its row and non-zero totals, but excludes the slack and surplus columns created when inequalities are rewritten as equations. That convention is neither more correct nor more natural; it is simply how the archive reports its models. Applying it to Stigler adds one cost coefficient for each of the 77 foods. His 9 × 77 nutrient table becomes a reported 10 × 77 matrix with 647 non-zeros: 84.0 per cent filled and 8.4 non-zeros per column. Without the cost row, the same diet has 570 non-zeros and 7.4 per column. Nothing about the model changed; only the bookkeeping did.

Why care about non-zeros per column? It asks how many reported rows one decision is wired into—one cost row plus the constraint rows under Netlib's convention. Those connections must be stored and eventually enter the solver's linear algebra. The median model has 4.8 non-zero coefficients per column, with a middle half from 4.0 to 7.4. Stigler is more locally connected than a typical problem on this shelf, but not fantastically more: 21 of the 98 models have more non-zeros per column.

What looks extreme is the percentage, because Stigler has only ten reported rows. As row counts grow, a typical column can remain connected to about five rows while density collapses: the same numerator is divided by a much taller rectangle. Among the 27 Netlib entries with fewer than 100,000 cells, the median is 5.1 non-zeros per column; among the ten with more than ten million, it is 5.0. This is a pattern in one old benchmark collection, not a law of industry. Density mainly describes how much of the rectangle is occupied; non-zeros per column begin to describe local coupling. Neither predicts runtime alone.

The zeros are not empty storage waiting to be filled. They say that a decision made over here has no direct effect on a promise made over there. A large network model can be manageable because locality keeps most of those relationships absent. A much smaller matrix can be painful because almost everything talks to everything else.

From inequalities to a basis

To explain what the simplex method manipulates, rewrite the model in standard form: equality constraints and non-negative variables. This is mathematical bookkeeping; modern software can do it internally. Begin with the nine-requirement system Ax ≥ b. Define the surplus vector s = Ax − b: its nine entries record the amount supplied above each floor. If a diet supplies 1.1 grams of calcium against a 0.8-gram minimum, the calcium entry of s is 0.3; if it supplies exactly 0.8, that entry is zero.

There is one surplus variable for each of the nine nutrient constraints. Surpluses cannot be negative and have zero cost in the objective. Subtracting them turns the nine inequalities into nine equations:

The resulting standard-form matrix is [A −I]: the original 77 food columns followed by nine surplus columns, one for each row. It therefore has 77 + 9 = 86 columns and nine equations.

With nine independent equations, a basis is a selection of nine columns whose 9 × 9 matrix is invertible. Set the other 77 variables to zero, then solve the nine equations for the nine selected variables. The result is a basic solution. If all nine solved values are non-negative, it is a basic feasible solution—the algebraic description of a vertex of the feasible region.

Before checking invertibility or feasibility, how many unordered nine-column selections are possible? Order does not matter, so the relevant count is “86 choose 9”:

These are raw candidate column sets, not 459 billion bases or vertices. Some selections are singular and therefore not bases. Some are invertible but yield a negative variable and are therefore not feasible. At one microsecond per raw selection, enumeration would still take 5.3 days; the solve on my laptop takes milliseconds.

A selected, or basic, variable may itself equal zero. That is degeneracy: fewer than nine variables are positive, and more than one basis may describe the same vertex. Classical primal simplex avoids enumeration by pivoting between bases and using reduced costs to decide which column should enter next. A non-degenerate pivot reaches an adjacent vertex; a degenerate pivot may change the basis without leaving the vertex. It does not scan the catalogue.[2]

This is why “77 variables” is not an account of the computation. The original coefficient matrix is 9 by 77. The standard-form matrix [A −I] is 9 by 86. There are almost half a trillion raw nine-column selections, but simplex searches through a sequence of bases instead of enumerating them. Four true descriptions, four different numbers.

Why the answer contains five foods

The definitions now pay for themselves. The fundamental theorem of linear programming says that, when an LP has an optimum, at least one optimum is a basic feasible solution.[3] In such a solution the 77 variables outside the basis are zero, so at most nine of the 86 food-and-surplus variables can be positive. Degeneracy can make that count smaller.

At Stigler's optimum, protein, iron, thiamine and niacin exceed their floors. Their four surplus variables are positive and must occupy four basic positions. At most five positive positions remain for foods. The computed optimum uses exactly five: wheat flour, cabbage, spinach, dried navy beans and beef liver. This proves that a sparse optimum exists; it does not say that every optimum must be sparse.

The original, or primal, problem chooses food purchases. Its dual prices requirements instead. Give each nutrient floor a non-negative shadow price λ_i. The condition A^Tλ ≤ c says that, for every food, the shadow value of the nutrients bought with one dollar cannot exceed that dollar. The dual maximises b^Tλ, the total shadow value of all nine required floors:

Complementary slackness links the two answers through two either-or rules.[4] If a food is purchased, its dual inequality is tight: its nutrients are worth exactly its cost; if they are worth strictly less, that food is not purchased. If a nutrient has positive surplus, its shadow price is zero; if its shadow price is positive, that floor is met exactly. Here five foods are purchased and five nutrient prices are positive, while four surpluses are positive and their four prices are zero. Those matching counts are a feature of this non-degenerate optimum, not a general identity. Equality of primal cost c^Tx and dual value b^Tλ is the certificate recalled at the opening.

There is another qualification worth keeping. If the objective is flat along a face, a dense mixture of optimal vertices is optimal too. If a buyer wants a balanced allocation across suppliers, that preference belongs in the model. The unadorned LP has no reason to invent it.

Two algorithms, two routes

The basis story is the natural language of the simplex method. Classical primal simplex stays on the boundary and swaps columns in and out of the basis. A non-degenerate pivot moves to an adjacent vertex; a degenerate pivot changes the basis while remaining at the same vertex. The method normally returns a vertex.

Simplex, however, is not the whole story. By the late 1970s, linear programming had an awkward split. Simplex was extraordinarily effective in practice, but Klee and Minty had shown that Dantzig's original pivot rule could require exponentially many steps—and no familiar pivot rule came with a polynomial worst-case guarantee.[6] In 1979 Leonid Khachiyan's ellipsoid algorithm established that rational LP could nevertheless be solved in polynomial time.[7] The ellipsoid method was a separate algorithmic family, not an interior-point method.

Then, in 1984, Narendra Karmarkar introduced a different polynomial-time projective algorithm whose iterates remain inside the feasible region. It was not the first use of a barrier or an interior trajectory, but it helped launch the modern interior-point era: the possibility of combining a polynomial guarantee with a computational alternative to simplex.[8] This was not another rule for choosing the next vertex. It changed the route through the problem.

Modern interior-point implementations typically use later primal-dual methods, not Karmarkar's original algorithm. They update the original variables and their dual prices together, drive the duality gap toward zero and obtain each search direction by solving a Newton linear system.[4] Geometrically, they move through the interior instead of walking from basis to basis along the boundary. They may approach a point in the middle of an optimal face; an optional crossover phase can then recover a basic solution. The enormous C(86, 9) count and the five-food argument therefore explain the structure of basic solutions, not the route taken by every LP algorithm.

The pattern behind the count

Non-zeros are a better first question than rows times columns, but they are still only a first question.

Simplex repeatedly solves with a changing basis matrix; a primal-dual interior-point method repeatedly solves a Newton system. Their starting matrices are sparse. Their factors need not be.

Elimination creates new non-zeros where the original matrix had zeros. Sparse linear algebra calls this fill-in. The amount depends on the pattern, the order in which rows and columns are eliminated and, for unsymmetric systems, numerical pivoting—which is why solvers spend real effort choosing permutations.[5] Two matrices can have the same dimensions and exactly the same number of non-zeros, yet produce factors with very different sizes.

For symmetric elimination, a small graph gives the intuition used by Cholesky-style methods. Eliminating a node forces its surviving neighbours to become connected to one another. Remove the hub of a star first and the leaves become a clique. Remove the leaves first and almost nothing has to be added. The original node and edge counts are identical; only the elimination order changes. Unsymmetric LU has extra complications, including numerical pivoting, but the ordering lesson survives.

So the first useful inspection of a slow model is not “how many variables?” It is the distribution of non-zeros by row and column, the block or network structure, the numerical scaling, and what presolve removes. None of these alone predicts runtime. Together they are closer to the object the solver actually sees than m × n.

This does not mean that theory or forecasting is silent. Complexity bounds exist for specified algorithms. Condition measures quantify how close an LP is to becoming ill-posed and enter finer bounds.[13] Solver developers can also build empirical predictors for a fixed code and a familiar model family. What does not exist is a universal, solver-independent conversion from rows, columns, non-zeros or density to elapsed seconds.

Polynomial and fast are different claims

Linear programming owns one of the better misunderstandings in applied mathematics.

1. The simplex method is famously fast.
2. Linear programming is polynomial-time.

The first sentence is an empirical statement about simplex implementations. The second is a worst-case theorem about other LP algorithms. They concern different methods, different measures and different kinds of evidence.

That distinction reminds me of an introductory convex-optimisation lecture I took with Professor Daniel Kuhn at EPFL.[14] He drew a numerical method as a black box: feed it a problem P and a tolerance ε, then count the arithmetic operations needed to return an ε-suboptimal solution. That count is the method's arithmetic complexity. In this approximate-arithmetic model, a method is efficient if its worst-case count is bounded by a polynomial in the number of parameters describing the problem and the number of accuracy digits required—roughly log(1/ε).

This is a scalability guarantee, not a stopwatch. It does not predict how long this particular diet LP will take: elapsed time also depends on constants, sparse linear algebra, presolve, software and hardware. For rational LP, the classical polynomial-time result instead counts the full binary encoding of the input, including coefficient bit-length. In neither model does “polynomial-time” automatically describe simplex; familiar pivot rules still have no known polynomial worst-case bound.

Kuhn then made the practical consequence vivid. Hold the solution time and all other inputs fixed, then double the available computing performance. If work behaves like S^k, the largest manageable size S is multiplied by 2^1/k; if work behaves like a^S, only log_a2 is added to S. This is an asymptotic comparison, not a promise that doubling a computer lets a real LP double every dimension.

Klee and Minty constructed a distorted cube in 1972 on which Dantzig's original pivot rule visits every one of its 2ⁿ vertices.[6] Related lower bounds exist for several other pivot rules. In three dimensions the path has eight vertices; add one dimension and the count doubles. This is a worst-case construction about a particular route through a polytope, not a prediction for Stigler's diet or a modern solver.

Those historical milestones answer a worst-case question, but only in the weakly polynomial sense: their bounds depend on the full binary input length, so the sizes of the coefficients matter. Whether general LP has a strongly polynomial algorithm—one whose number of arithmetic operations is independent of coefficient bit-length—remains open. Smale put it ninth on his list of problems for this century.[9]

From speed-up to solvability

Worst-case theory and measured progress can both be true. Koch and co-authors compared virtual-best solver portfolios from around 2001 and 2020—a hypothetical selector that takes the fastest solver for each instance.[10] In small isolation tests, old LP code ran about 20 times faster on modern hardware. Across 56 LP instances both portfolios solved within 24 hours, newer software was about nine times faster by a shifted geometric mean. Multiplying the two estimates gives roughly 180 in combination.

Those numbers need their denominator too. Easy cases were excluded, benchmark choice affects the result, the virtual-best selector is not one purchasable solver, and the averages have high variance. The LP advance was not merely speed: 64-bit systems and much larger memory made models with tens of millions of rows or columns tractable. On the shared test set, the slowest LP that old codes solved in a day took the newer portfolio less than three minutes.

The larger discontinuity was in mixed-integer programming, the subject of the next piece. Of 240 MIPLIB 2017 instances in their comparison, 149 could not be solved by any old code within 24 hours; the new codes solved those instances in a geometric-mean time of 104 seconds. That is why the authors resist turning timeouts into an inflated speed-up score. Their more memorable summary is qualitative:

“Nowadays, one is unpleasantly surprised if none of the solvers can tackle it.”

No single line in that history says which algorithm will win on the next model. Modern solvers keep simplex and barrier methods because structure decides. “Polynomial” is a guarantee about how a bound scales. “Fast” is an observation made on a machine, a model family and a tolerance.

Four convex dialects, one kind of proof

Linear objectives and constraints are only the first rung. The other common convex forms buy more expressive syntax while keeping a route to a primal-dual certificate.

The table mixes one problem form, QP, with cone-defined classes on purpose. A convex quadratic can be rewritten with a rotated second-order cone; an SOCP can be written as an SDP. This gives a representational ladder, not an instruction to send every LP to an SDP solver. A specialised algorithm lower down will usually exploit structure the general reformulation hides.

Interior-point theory makes part of the price precise. The standard barrier for one non-negative orthant in n dimensions has parameter n. A single second-order-cone block has parameter 2, independent of that block's dimension. A positive-semidefinite cone of k by k matrices has parameter k.[11] Parameters add across cone blocks and help bound the number of Newton steps. They do not measure runtime. Forming and factorising one SDP Newton system can cost far more than taking one LP step.

Markowitz sits on the second rung when Σ is positive semidefinite: minimise w^TΣ w under a return target and a budget. Under the factor model and uncertainty sets specified by Goldfarb and Iyengar, robust versions of that portfolio problem become SOCPs.[12] Change the uncertainty set, especially by putting a general semidefinite condition directly on the covariance, and the reformulation changes with it. The geometry chosen for what you do not know becomes part of the computational model.

The certificate also needs a qualification. LP strong duality is unusually well behaved. In general conic problems, a condition such as strict feasibility is what makes the primal and dual optima meet; semidefinite programs can exhibit a positive gap or fail to attain an optimum when regularity fails.[4] Convexity keeps the local-versus-global promise. It does not waive the hypotheses of duality.

Everything so far still lives on Rockafellar's cooperative side of the watershed. The matrix may be large, sparse, badly ordered or expressed through a more expensive cone, but the feasible set has no holes. The next piece adds one innocent-looking instruction: this warehouse is open or closed; this gene is deleted or it is not. Half a warehouse is no longer a point you can visit. The rows and columns remain, and the proof becomes a gap.

Data and code

The matrix calculations and all quantitative figures are reproducible in the Post 2 folder of github.com/Denis-Joly/what-optimal-means. The optimal diet itself is solved in the Post 1 folder; the basis figure uses its four-surplus, five-food result. The opening caricature is deliberately illustrative rather than data-driven; its exact generation prompt and exported image are committed alongside the code.

analyze_structure.py reads the Stigler table used in the first piece and a dated copy of Netlib's official summary. It prints the standard-form basis count, the matrix statistics and every threshold used above. verify_klee_minty.py reproduces all eight vertices under Dantzig's pivot rule using exact rational arithmetic. make_figures.py turns those results and the documented Post 1 solution into responsive article fragments and a local interactive demo; article-viz.js adds the Netlib metric switch and exact-value explorer without a charting library. Netlib's convention of including the objective row is kept in the code rather than corrected silently.

The comparison has limits. Netlib is a classic benchmark set assembled from older academic and operational models, not a random sample of today's supply chains. The split at 100,000 and ten million cells is descriptive. It shows that non-zeros per column stay almost unchanged within this collection; it does not claim a universal constant.

References

1. Netlib, linear-programming directory and LP/DATA problem summary table. The directory describes the collection as test problems in MPS, the old machine-readable interchange format for linear programs. The table currently lists 98 problems, names AFIRO's Stanford source, and describes STOCFOR1–3 as Gus Gassmann's seven-period forestry models with random forest fires. Its notes state that row and non-zero counts include the cost row, while column and non-zero counts exclude slack and surplus columns. The statistics here are my calculations from that table, downloaded 11 August 2026.
2. George B. Dantzig, Linear Programming and Extensions (Princeton University Press, 1963), especially the geometric and revised-simplex treatments.
3. David G. Luenberger and Yinyu Ye, Linear and Nonlinear Programming, 3rd ed. (Springer, 2008), §2.3–2.4, pp. 19–21. The theorem guarantees an optimal basic feasible solution when an optimum exists.
4. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, 2004. Complementary slackness is §5.5.2; certificates and strong duality are treated in chapter 5; barrier and primal-dual interior-point methods are developed in chapter 11.
5. Timothy A. Davis, Sivasankaran Rajamanickam and Wissam M. Sid-Lakhdar, “A survey of direct methods for sparse linear systems”, Acta Numerica 25 (2016): 383–566. Fill-in and permutations are introduced at pp. 8–9.
6. Victor Klee and George J. Minty, “How Good Is the Simplex Algorithm?”, in Inequalities III (Academic Press, 1972), 159–175. Benjamin Grimmer's freely adaptable Johns Hopkins handout supplies a visual reference for the independently rendered three-dimensional figure.
7. Leonid G. Khachiyan, “A Polynomial Algorithm in Linear Programming,” Soviet Mathematics Doklady 20 (1979): 191–194.
8. Narendra Karmarkar, “A New Polynomial-Time Algorithm for Linear Programming”, Combinatorica 4 (1984): 373–395. Karmarkar's paper supplies the projective polynomial-time result; earlier barrier methods are surveyed in Boyd and Vandenberghe, Convex Optimization, §11.1.
9. Stephen Smale, “Mathematical Problems for the Next Century,” The Mathematical Intelligencer 20 (1998): 7–15.
10. Thorsten Koch, Timo Berthold, Jaap Pedersen and Charlie Vanaret, “Progress in Mathematical Programming Solvers from 2001 to 2020”, EURO Journal on Computational Optimization 10 (2022): 100031; author preprint. Hardware isolation is §2.1, the shared-instance comparison is §3.2 and the LP conclusion is §4.1.
11. Boyd and Vandenberghe, Convex Optimization, examples 11.5–11.7, pp. 597–598; Aharon Ben-Tal and Arkadi Nemirovski, Lectures on Modern Convex Optimization (SIAM, 2001), lecture 4.
12. Donald Goldfarb and Garud Iyengar, “Robust Portfolio Selection Problems”, Mathematics of Operations Research 28, no. 1 (2003): 1–38.
13. James Renegar, “Incorporating Condition Measures into the Complexity Theory of Linear Programming”, SIAM Journal on Optimization 5, no. 3 (1995): 506–524. Renegar replaces a size-only view with condition measures related to the data accuracy needed for the computational goal.
14. Daniel Kuhn, Convex Optimization (MGT-418), introductory lecture on efficient numerical methods, EPFL; official course description and public lecture record. I took this course; the arithmetic-complexity black-box framing above is my paraphrase of Professor Kuhn's introductory lecture. The official course description separately notes that formulation can separate seconds from days.