∇ProvenDecisions
Ctrl K

Primal and dual

Every optimization problem with constraints has a dual: a second problem whose variables are prices on the original (primal) constraints. Its optimum bounds the primal optimum, and for the models below the two are equal at the optimum, which is how ProvenDecisions proves an answer is optimal. Each row shows the primal and its dual in matrix form; Solve this opens a small example in Solve with its dual and how it is built, step by step.

Model types

ModelPrimalDual
Linear program, minimizeSolve this
The textbook pair. Every dual value is a lower bound on the primal optimum (weak duality); at the optimum they are equal (strong duality).
Linear program, maximizeSolve this
The same pair read the other way: every dual value is an upper bound. Each y is the price of one constraint.
Equations and free variablesSolve this
An equation gets a free price; a free variable gets an equation. Mixed models follow the sign rules below row by row.
Integer programSolve this
The dual of the LP relaxation (the same model without the whole-number condition). It bounds the integer optimum; the difference is the duality gap, which can be positive.
Absolute values (and max, min)Solve this
First written as a linear program with a helper t for each |.| (t at least the term and at least its negative), then dualized. Each w says which side of its point x sits on; the dual constraint says the pulls balance.
Convex quadratic programSolve this
The Lagrangian dual: minimize the Lagrangian over x (x = −Q⁻¹r) and maximize what is left. With linear constraints the optimal values are equal whenever the primal has an optimum.

The sign rules

For a linear program with mixed constraints and variables, each constraint gives one price (a dual variable) and each variable gives one dual constraint, by these rules. The right-hand side of variable j's dual constraint is its coefficient c_j in the objective.

Primal minimizesDual maximizesPrimal maximizesDual minimizes
constraint i is constraint i is
constraint i is constraint i is
constraint i is freeconstraint i is free
free free

In the app

After a solve, Formulate the dual (or walkthrough depth 6 and up) adds the dual to the walkthrough, with How the dual is built: the matrix form with your numbers, the prices, the sign rules used, and the check that the dual optimum equals the primal optimum. The model step has the primal in matrix form.

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: