Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 38 ยท Getting Started

Solving LPs with SciPy's linprog

Use scipy.optimize.linprog to solve linear programs: objective, A_ub, A_eq, bounds, maximizing, reading status, slack, duals and common input mistakes.

You can now model an LP and solve a two-variable one by hand. Real models have dozens to millions of variables, so you need a solver. In Python the standard entry point is scipy.optimize.linprog, which calls the open-source HiGHS solver (simplex and interior-point methods in optimized C++). This lesson teaches the API completely; later lessons build our own simplex to see what happens inside.

The general form linprog expects

linprog solves

TEXT
minimize    c . x
subject to  A_ub x <= b_ub
            A_eq x  = b_eq
            lower <= x <= upper
Argument Meaning
c Objective coefficients (always minimized)
A_ub, b_ub Matrix and vector for <= constraints
A_eq, b_eq Matrix and vector for = constraints
bounds (low, high) per variable; None means no limit. Default is (0, None)
method "highs" (default and recommended), "highs-ds" (dual simplex), "highs-ipm" (interior point)

Two conversions you will do constantly:

  • Maximize: pass -c and negate the result.
  • >= constraint: multiply both sides by -1, so x + y >= 3 becomes -x - y <= -3.

A mixed example

Minimize 3a + 2b + 4c subject to a + b + c = 10 (a fixed total), a >= 2, b - c <= 3, and all variables non-negative.

Python Equality, inequality and bounds together

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Putting a >= 2 in bounds is better than adding a row to A_ub: solvers handle simple bounds much faster than general constraints.

What the result object contains

res is an OptimizeResult with these useful fields:

  • res.status: 0 optimal, 2 infeasible, 3 unbounded, 1 iteration limit, 4 numerical trouble.
  • res.success and res.message: readable summary.
  • res.x: the solution vector (only meaningful when success is true).
  • res.fun: objective value of the minimization you passed.
  • res.slack, res.con: constraint slack and equality residuals.
  • res.ineqlin.marginals and res.eqlin.marginals: dual values (shadow prices) for the constraints. We interpret these in Chapter 4.
Python Maximize and read the dual values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shadow prices come out as 10 dollars per oven hour, 20 per labor hour and 0 for flour. In other words, one more labor hour is worth 20 dollars at the margin. We will derive these numbers by hand with duality.

Handling statuses

Never assume a solve succeeded. Check res.status before reading res.x.

Python Infeasible and unbounded outcomes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Forgetting the default bounds. Variables are non-negative unless you pass bounds. For a free variable use (None, None).
  • Passing a maximization as is. You will get the minimum instead, which may even look plausible. Negate c.
  • Wrong inequality direction. linprog only knows <=. Flip >= rows.
  • Lists of the wrong shape. A_ub must be 2D (a list of rows) even with a single row: [[1, 1]], not [1, 1].
  • Reading res.x after failure. It may be None.
  • Hidden scaling problems. Mixing coefficients like 0.0001 and 1e6 causes numerical trouble. Rescale units (thousands of dollars, not dollars).

When to leave SciPy

linprog is excellent for small and medium continuous LPs. For integer variables SciPy offers scipy.optimize.milp (we use it in Chapter 5). For modeling languages with named variables (PuLP, Pyomo, CVXPY, OR-Tools) you would install those packages locally; they cannot be loaded in this site's browser runner, so the course writes matrices directly. The ideas transfer one to one: a modeling language only builds c, A and b for you.

Build matrices from data with NumPy instead of typing them by hand. The row for constraint i and the column for variable j should come from loops or reshaping, so a bug in one place is not copied into many.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. You want to enforce x + 2y >= 6 with linprog. What do you pass in A_ub and b_ub?

    Multiplying a >= constraint by -1 turns it into <=: -x - 2y <= -6.
  2. 2. res.status is 3. What happened?

    Status 0 is optimal, 1 iteration limit, 2 infeasible, 3 unbounded, 4 numerical difficulties.
  3. 3. What is the default bound for each variable in linprog?

    Unless you pass bounds, every variable is constrained to be at least 0.
  4. 4. Why prefer bounds=(2, None) over adding the row x >= 2 to A_ub?

    Bounds are handled implicitly by the algorithm and do not enlarge the constraint matrix.

Summary

  • linprog minimizes c . x with A_ub x <= b_ub, A_eq x = b_eq and per-variable bounds.
  • Maximize by negating c; turn >= into <= by negating the row.
  • Always check res.status or res.success before using res.x.
  • res.slack and the marginals fields expose slack and dual values.
  • Common bugs: default bounds, wrong signs, 1D constraint lists and bad scaling.

Next: Standard Form and Slack Variables