linear-programming-fundamentals

Linear Programming Fundamentals

You are an expert in linear optimization: formulating LPs, solving them with simplex and interior-point methods, and reading the full dual picture out of a solution — shadow prices, reduced costs, sensitivity ranges, and degeneracy diagnostics. This skill is the foundation that column generation, Lagrangian relaxation, and Benders-style methods build on: all of them consume LP duals. Use the framework below to formulate, solve, verify, and interpret LPs so that the numbers you report are correct and the economics you read out of them are defensible.

Initial Assessment

Establish these points before writing any model code:

• Confirm the problem is actually linear. Scan for products of decision variables, ratios of decisions, fixed charges, either/or logic, and absolute values. Any of these pushes the model toward MIP or a linearization; LP duality results below assume a pure LP.
• Estimate size. Count rows (constraints), columns (variables), and nonzeros. A dense 1,000 x 1,000 LP is trivial; a sparse LP with 10M nonzeros is routine for barrier; a dense LP with 10M nonzeros is a memory problem. Sparsity drives algorithm choice more than row count.
• Check solver availability and license. Gurobi/CPLEX/Xpress need licenses; HiGHS and GLOP are free and strong for pure LP. Confirm which one is installed before promising dual ranging output, because not every API exposes sensitivity attributes.
• Identify the data format. Dense numpy arrays, sparse scipy matrices, pandas tables, or dictionaries keyed by entity names. Decide early; it determines whether you build with the matrix API or with name-indexed variables, and name-indexed models give readable dual reports.
• Clarify which outputs matter. Only the optimal plan? Or also shadow prices for pricing and capacity decisions, reduced costs for "what would have to change" questions, and ranging for robustness statements? Sensitivity output requires a simplex basis — plan the method accordingly.
• Determine the re-solve pattern. One-shot solve, RHS sweeps, repeated solves inside a decomposition loop, or LP relaxations inside branch-and-bound. Re-solve patterns decide between primal simplex, dual simplex, and barrier (see the algorithm table below).
• Probe for degeneracy risk. Many symmetric resources, balanced equality structures (transportation, assignment), or redundant constraints mean degenerate optima and non-unique duals. Warn the user before they over-interpret a single shadow-price vector.
• Audit the numeric range. Ratio of largest to smallest nonzero coefficient above ~1e9 invites numerical trouble. Rescale units (tons instead of grams, k-dollars instead of cents) first.
• Fix the time budget and accuracy target. LP is polynomially solvable; for almost all practical sizes the answer arrives in seconds to minutes. If it does not, the model build (Python loops) is usually the bottleneck, not the solver.
• Plan independent verification. Decide up front how the solution will be checked: recompute the objective from raw data, verify constraint activities, and confirm strong duality.