Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 38 ยท Optimization

Linear and Integer Programming

Solve production planning, diet and knapsack problems with scipy.optimize.linprog (HiGHS) and milp, read status and shadow prices, and assign tasks optimally.

A huge share of business and engineering decisions look like this: you have limited resources, several activities that use them, and a goal such as maximum profit or minimum cost. How many chairs and tables should the workshop build? Which foods give the nutrients you need for the least money? Which tasks go to which workers? When both the goal and the limits are linear (sums of variables times constants), the problem is a linear program, and it can be solved fast and exactly, even with thousands of variables.

SciPy solves linear programs with linprog and mixed-integer ones with milp, both powered by the HiGHS solver library. A related special case, assigning items one-to-one at lowest cost, has its own function, linear_sum_assignment. This lesson also shows how to read the result: status, slack and the shadow prices that tell you what an extra unit of each resource is worth.

The standard form

linprog minimizes c @ x subject to:

  • A_ub @ x <= b_ub (inequality constraints),
  • A_eq @ x == b_eq (equality constraints),
  • lower and upper bounds on each variable (by default 0 <= x < infinity).

Maximizing? Negate the objective (c = -profit) and negate the result afterwards. A "greater than or equal" constraint is turned into "less than or equal" by multiplying both sides by -1.

flowchart LR
    P["Word problem"] --> V["choose variables<br/>x1, x2, ..."]
    V --> O["objective:<br/>c @ x to minimize"]
    V --> K["constraints:<br/>A_ub, b_ub, A_eq, b_eq"]
    V --> B["bounds on each x"]
    O --> L["linprog(c, ...)"]
    K --> L
    B --> L
    L --> R["x, fun, status,<br/>slack, marginals"]

From a word problem to linprog: decide the variables first, then fill the arrays.

A production-planning example

A workshop makes chairs (profit 30 each) and tables (profit 20 each). Assembly takes 2 hours per chair and 1 hour per table, with 100 hours available. Finishing takes 1 hour per chair and 2 per table, with 80 hours available. Each item uses one board and 100 boards are in stock. How many of each should it build?

Python Maximize profit with linprog

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 answer is 40 chairs and 20 tables for a profit of 1,600. Read the other fields:

  • status 0 with success True means an optimal solution was found. Other codes: 1 iteration limit, 2 infeasible, 3 unbounded, 4 numerical trouble.
  • slack is how much of each resource is left over. Assembly and finishing are fully used (slack 0), but 40 boards remain. Constraints with zero slack are binding: they are what stops you from earning more.
  • Shadow prices come from res.ineqlin.marginals (the dual values). HiGHS reports the change in the minimized objective per unit of right-hand side, which is negative for our negated profit, so we flip the sign. Here one extra assembly hour is worth about 13.33 in profit, one extra finishing hour about 3.33, and an extra board is worth nothing because there are already spare boards.

Shadow prices answer practical questions: if overtime costs 10 per assembly hour, buy it, since each hour returns 13.33; if boards cost anything at all, do not buy more. They are valid only for small changes, until a different set of constraints becomes binding.

The solution of a linear program always sits at a vertex (corner) of the feasible region, or along an edge between two equally good vertices. That is why the answer is exact rather than approximate, and why LP solvers are so reliable.

A diet problem

The diet problem is the oldest textbook LP: pick servings of foods to meet nutrition targets at minimum cost. Constraints here mix >= (minimum protein and calories) and <= (maximum fat), and each food is limited to 8 servings through bounds. Because A_ub only knows "less than or equal", we negate the >= rows.

Python Cheapest diet

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 optimal diet uses the cheapest calorie sources: all the oats the bound allows, a little beans, no milk or eggs. The calorie requirement is exactly met (the binding constraint), while protein and fat have room to spare. Models like this are rarely a realistic menu, but the pattern (cost vector, nutrient matrix, bounds) is the template for blending, feed mixing, portfolio and transport problems.

Equality constraints, infeasible and unbounded problems

A_eq and b_eq add exact requirements. Two other outcomes deserve to be recognized: a problem can be infeasible (the constraints contradict each other, so no solution exists) or unbounded (the objective can improve forever). Both are usually modeling mistakes and linprog tells you through status.

Python Equalities, infeasible and unbounded cases

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.

Always test res.success (or res.status) before using res.x; on failure x can be None. In the blend, the equality dual says that growing the batch by one kilogram, with the protein target unchanged, costs 0.50 more.

Integer programming with milp

Many decisions are whole numbers: you cannot build 2.4 factories or pick 0.4 of a laptop. scipy.optimize.milp (mixed-integer linear programming) adds an integrality array: 0 means a continuous variable, 1 means an integer variable. Combined with bounds (0, 1), an integer variable becomes a yes/no choice.

The classic example is the knapsack: choose items, each at most once, to maximize total value within a weight limit. milp takes c, constraints (a LinearConstraint), integrality and bounds.

Python Knapsack with milp

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.

Compare the two results. The relaxed problem is allowed to take a fraction of one item and reaches a higher value; the integer problem must commit to whole items and scores lower. The relaxation always gives an upper bound on the integer optimum, which is how real solvers work: they solve relaxations repeatedly and branch on fractional variables. Integer problems can be much harder than LPs (they are NP-hard in general), so keep them small or well structured.

Assignment: the special case

When you must match each worker to exactly one task, minimizing total cost, you do not need a general LP. scipy.optimize.linear_sum_assignment solves it directly with the Hungarian-style algorithm, very fast even for thousands of rows. It takes a cost matrix and returns the matched row and column indices.

Python Optimal assignment

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.

Brute force confirms the optimum, but it checks n! matchings (24 here, over 3 million for ten workers), while linear_sum_assignment runs in polynomial time. The same function is behind matching detections to tracked objects in computer vision. Assignment is also a graph problem; see Sparse Linear Algebra and Graph Algorithms for related graph tools.

Modeling tips

  1. Write the variables down first, with units. Most bugs are mixed-up columns.
  2. Keep numbers in similar ranges. Coefficients from 1e-6 to 1e6 in one model can upset the solver.
  3. Handle >= rows by negating, or use LinearConstraint objects with milp, which accept lower and upper limits directly.
  4. Check success and, for surprising answers, print slack and shadow prices; they usually reveal a mistake in a constraint.
  5. Reach for specialized libraries (PuLP, OR-Tools, CVXPY) when models grow to thousands of lines of constraints, since they provide algebraic modeling syntax. SciPy is excellent for compact problems.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. linprog always minimizes. How do you maximize a profit vector p?

    Maximizing p is the same as minimizing -p. Remember to flip the sign of res.fun to read the profit.
  2. 2. A resource constraint has slack 0 in the solution. What does this mean?

    Zero slack means the constraint holds with equality at the optimum. Binding constraints limit the objective and normally have nonzero shadow prices.
  3. 3. What does the integrality argument of milp do?

    integrality holds one entry per variable: 0 for continuous, 1 for integer. With bounds (0, 1) an integer variable is a yes/no decision.
  4. 4. Which problem is linear_sum_assignment designed for?

    It solves the assignment problem on a cost matrix, returning the matched row and column indices.

Summary

  • A linear program has a linear objective and linear constraints. linprog(c, A_ub, b_ub, A_eq, b_eq, bounds) minimizes c @ x; negate to maximize.
  • Always check res.success and res.status: 2 means infeasible, 3 means unbounded.
  • slack shows unused resources; the dual values in res.ineqlin.marginals (sign-flipped for a maximization) are shadow prices.
  • milp adds integer and yes/no variables through integrality and bounds; the LP relaxation gives an upper bound.
  • linear_sum_assignment solves one-to-one matching quickly, far better than trying all permutations.

This finishes the optimization chapter. Next up: Numerical Integration, where we compute areas under curves.