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
| Model | Primal | Dual | |
|---|---|---|---|
| Linear program, minimize | Solve 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, maximize | Solve 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 variables | Solve this | ||
| An equation gets a free price; a free variable gets an equation. Mixed models follow the sign rules below row by row. | |||
| Integer program | Solve 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 program | Solve 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 minimizes | Dual maximizes | Primal maximizes | Dual minimizes |
|---|---|---|---|
| constraint i is | constraint i is | ||
| constraint i is | constraint i is | ||
| constraint i is | free | constraint 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.