How to Learn Linear Programming Algorithms: Feasible Regions, Simplex, Duality and Numerical Reality

Wait, What?

A linear program is not solved by “trying lots of combinations.” Its geometry lets an algorithm move through a tiny structural subset of an enormous search space.

Linear programming appears wherever limited resources must be allocated under linear constraints: production, transport, scheduling, blending, portfolio models and network optimisation. The equations can look like ordinary algebra, but the algorithmic question is different: how do we move from a mathematical model to an optimal feasible point with a defensible certificate?

Quick Answer

Learn linear programming through the route decision variables → objective → constraints → feasible region → corner-point geometry → slack and standard form → simplex pivot → improvement and stopping rule → dual interpretation → degeneracy/unboundedness/infeasibility → numerical solver checks → real workload. Begin in two dimensions so the geometry is visible before the tableau becomes symbolic.

1. Model Before You Optimise

Give the learner a small resource-allocation story: two products share limited machine hours and material. Define one variable per production quantity. Write a profit objective and one inequality per resource limit. Ask what each coefficient means in the real situation.

• Decision variables: what can the system choose?
• Objective: what quantity is being maximised or minimised?
• Constraints: what limits or requirements must every acceptable solution obey?
• Domain: are variables continuous, nonnegative, integer, bounded or unrestricted?

Many failures blamed on optimisation are actually modelling errors. An algorithm can solve the wrong linear program perfectly.

2. Draw the Feasible Region

In two variables, graph each constraint as a half-plane. Their intersection is the feasible region. Move an objective line across that region and watch where the best value occurs. This geometric stage gives meaning to later algebraic operations.

The key insight is that for a linear objective over a polyhedral feasible region, an optimum—when one exists under the usual finite conditions—can be found at an extreme point. The simplex method exploits that structure by moving from one basic feasible solution to another rather than exploring every point.

3. Standard Form Turns Geometry Into an Algorithmic State

Inequalities can be converted using slack variables so the system can represent unused capacity explicitly. A basic feasible solution chooses a set of basic variables and solves the corresponding equations. The tableau or revised-simplex representation is bookkeeping for that state.

Do not introduce a large tableau first. Let the learner connect one corner point on the graph to one basic feasible solution. Then the algebra has something concrete to represent.

4. A Simplex Pivot Is a Controlled Change of Basis

At each simplex step, one nonbasic variable is chosen to enter the basis because moving in that direction can improve the objective. Another variable leaves so feasibility is preserved. The pivot updates the representation of the same linear system under a new basis.

• Which variable can improve the objective?
• How far can it increase before a constraint becomes tight?
• Which current basic variable must leave?
• After the pivot, is the new solution feasible?
• Did the objective improve, remain tied because of degeneracy, or reveal a special case?

5. Trace One Pivot by Geometry and Algebra Together

For a small two-variable example, draw the edge along which the solution moves. Then perform the corresponding pivot. Ask the learner to name the old vertex, new vertex, entering variable and leaving variable. This dual representation prevents the tableau from becoming meaningless symbol manipulation.

Princeton’s Algorithms reference provides a bare-bones simplex implementation and returns both primal and dual solutions. It also warns that the educational implementation is not intended for large inputs and is not robust to floating-point roundoff. See Princeton Algorithms: LinearProgramming.

6. The Stopping Rule Must Mean Something

A simplex run should not stop because “the table looks finished.” The reduced-cost or equivalent optimality condition must show that no allowable local basis change can improve the objective under the chosen formulation. Learners should explain the stopping condition in words before trusting the final number.

7. Duality Turns a Solution Into an Explanation

Every linear program has a related dual problem. Informally, the primal asks how to use resources; the dual can be read as assigning values to the constraints or resources. Weak duality provides bounds. Under the usual conditions of strong duality, optimal primal and dual objective values agree.

This is professionally important because an optimiser should not only produce a candidate solution. It should provide evidence about optimality, sensitivity and which constraints are economically significant.

8. Complementary Slackness Connects Structure Across the Pair

Complementary slackness links unused primal resources with dual prices and active primal decisions with dual constraints. It gives learners a way to cross-check a solution pair without rerunning the whole algorithm. Treat it as a reasoning tool, not another formula to memorise.

9. Infeasible, Unbounded and Degenerate Are Different States

A professional learner must recognise special outcomes.

• Infeasible: no point satisfies all constraints.
• Unbounded: feasible solutions exist but the objective can improve without finite limit in the optimisation direction.
• Degenerate: a basic feasible solution has one or more basic variables at zero; pivots may fail to improve the objective immediately.
• Multiple optima: more than one feasible point attains the same best objective value.

Do not label all unusual solver messages as “failed optimisation.” Each state says something different about the model or algorithm path.

10. Cycling Shows Why Pivot Rules Matter

With degeneracy, careless pivot choices can revisit earlier bases. Anti-cycling rules such as Bland’s rule exist to guarantee progress in the combinatorial state space. Princeton’s educational implementation explicitly uses Bland’s rule. This is a good example of a small implementation choice carrying a correctness guarantee.

11. Simplex Is Not the Entire Field

Interior-point methods approach optimisation differently, moving through the interior of the feasible region rather than following edges vertex by vertex. Modern solvers may use presolve, scaling, sparse linear algebra, crossover, heuristics and specialised routines. The learner should understand simplex deeply without concluding that every professional linear program is solved by one classroom tableau.

12. Numerical Reality Changes the Meaning of “Correct”

Real solvers use finite-precision arithmetic. Constraint violations may be judged against tolerances; nearly dependent constraints can create numerical difficulty; badly scaled coefficients can degrade reliability. A mathematically valid model can still be numerically troublesome.

At professional level, report objective value together with feasibility residuals, tolerances, solver status and relevant sensitivity information. “The software returned a number” is not an optimisation certificate.

13. Linear Programming and Integer Programming Must Stay Separate

If variables must take integer values, ordinary linear programming no longer solves the complete problem. The LP relaxation may still be useful, but branch-and-bound, cutting planes or specialised integer-programming machinery is needed. This boundary prevents a common modelling error: accepting fractional people, machines or indivisible decisions because the continuous model was easier.

14. Common Learning Failure States

• Optimising before checking that variables and constraints represent the real problem.
• Memorising tableau rules without linking them to movement between feasible vertices.
• Choosing an entering variable but ignoring the feasibility-limiting ratio.
• Confusing infeasible with unbounded.
• Assuming every pivot must strictly improve the objective.
• Ignoring dual information and losing an optimality cross-check.
• Treating integer decisions as continuous because the LP solver accepts them.
• Reporting a solver result without checking status or residuals.

15. A Scaffold-Fade Learning Ladder

• Level 1: translate a two-variable story into variables, objective and constraints.
• Level 2: graph the feasible region and find corner points.
• Level 3: connect one corner point to a basic feasible solution.
• Level 4: trace one simplex pivot with geometry and algebra side by side.
• Level 5: solve a small LP and construct or interpret its dual.
• Level 6: diagnose infeasible, unbounded, degenerate and multiple-optimum cases.
• Level 7: formulate a realistic model, use a professional solver, and validate status, residuals, scaling and sensitivity.

For complex symbolic procedures, faded worked examples can keep novice attention on the meaning of each state change rather than overwhelming working memory. Shin and colleagues found that faded worked examples combined with metacognitive scaffolding supported programming problem solving and self-regulation. See Shin et al. (2023). As support fades, learners should reconstruct why each pivot is valid rather than imitate a solved tableau.

16. Practice With Models That Fail in Different Ways

Use one bounded feasible model, one infeasible pair of constraints, one unbounded objective, one degenerate vertex and one model with multiple optima. Ask the learner to predict the state from geometry before running any solver. This develops diagnosis rather than button-pushing.

17. Immediate, Delayed and Transfer Checks

• Immediate: identify feasible points and perform one pivot.
• Delayed: explain why an optimum can be sought at extreme points.
• Dual: interpret a dual variable as a constraint value or bound.
• Failure: distinguish infeasible from unbounded using a new model.
• Transfer: decide whether a new allocation problem is continuous LP, integer optimisation, flow, matching or another model.

18. AI Assistance Boundary

AI can help check algebra, generate small LP examples, translate a solved tableau back into a geometric explanation and produce counterexamples. It should not replace formulation ownership. The learner must be able to state what each variable and constraint means and verify that the returned solution answers the intended real-world question.

Professional Direction

Advanced study includes revised simplex, sparse factorisation, interior-point methods, sensitivity analysis, decomposition, network LPs, robust optimisation, mixed-integer programming and large-scale solver engineering. Stanford’s convex-optimisation tradition places linear programs inside a wider family of convex problems with duality and interior-point methods, while production solvers add extensive numerical machinery around the mathematics.

Algorithm-learning rule: optimisation expertise begins when the learner stops asking only “What is the best number?” and asks “What model produced it, why is it feasible, what certifies optimality, and how trustworthy is the numerical computation?”