GLPK/Background theory

It can be useful, on occasion, to provide background theory for material located elsewhere in this wikibook. This page affords a place. But this page should not be used to blindly replicate foundation material from the official GLPK manuals, nor to write general entries on linear programming.

Orientation

Readers seeking orientation can consult the following wikipedia pages:

linear programming (LP)
mixed-integer programming (MIP) (a class of linear programming)
pure integer programming (IP) (a subset of which is amiable to linear programming)
network flows (normally a specialization of linear programming)
graph theory and combinatorial optimization (a subset of which is amiable to linear programming)

Note also that mixed-integer programming (MIP) and mixed-integer linear programming (MILP) are treated here as synonyms. And that the term pure linear programming is used to exclude mixed-integer problems.

Karush-Kahn-Tucker (KKT) optimality conditions

In the general case of nonlinear programming (NLP), the Karush-Kuhn-Tucker optimality conditions (KKT) provide the necessary first-order conditions for a solution to be locally optimal (together with some regularity conditions that also have to be satisfied). Linear programming (LP) is a special case of NLP in which both the feasible region and the objective function are convex. In this particular case, the KKT conditions alone are necessary and sufficient for the solution to be globally optimal.^[1] The KKT conditions can be applied to the basic and interior-point solutions of any LP problem, but may not be applied to the solutions from mixed-integer linear programming (MIP). That said, the first two KKT conditions can be applied to mixed-integer programs to confirm that the solution is feasible.

This wikibook also describes the specifics of KKT reporting by GLPK and also provides a typical example.

KKT optimality conditions

Take a primal LP problem in standard form: ^[2]

minimize	$z=\mathbf {c} ^{\top }\mathbf {x}$
subject to	${\begin{aligned}A\mathbf {x} &=\mathbf {b} \\\mathbf {x} &\geq \mathbf {0} \end{aligned}}$

where $\mathbf {x}$ is the vector of primal variables. The dual LP problem becomes:

maximize	$p=\mathbf {b} ^{\top }\pi +\mathbf {0} ^{\top }\lambda$
subject to	${\begin{aligned}A^{\top }\mathbf {\pi } +\lambda &=\mathbf {c} \\\mathbf {\lambda } &\geq \mathbf {0} \\\pi &\quad {\text{of any sign}}\end{aligned}}$

where $(\pi \,|\,\lambda )\,\!$ is a vector of dual variables,^[3] $\pi \,\!$ is a vector of Lagrange (or simplex) multipliers (shadow prices) for the equality constraint $A\mathbf {x} =\mathbf {b}$ and $\lambda \,\!$ is a vector of Lagrange multipliers (reduced costs) for the inequality constraint $\mathbf {x} \geq \mathbf {0}$ .

The Karush-Kahn-Tucker optimality conditions for an LP make use of all the constraints from the primal and dual formulations and include a complimentary slackness condition. The five KKT optimality conditions conditions are:

`KTT.PE`	$A\mathbf {x} =\mathbf {b}$
`KTT.PB`	$\mathbf {x} \geq \mathbf {0}$
`KTT.DE`	$A^{\top }\mathbf {\pi } +\lambda =\mathbf {c}$
`KTT.DB`	$\lambda \geq \mathbf {0}$
`KTT.CS`	$x_{j}=0\ {\text{or}}\ \lambda _{j}=0\ {\text{for all}}\ j\ {\text{(or both)}}$

The KKT.CS condition can be rewritten as $x_{j}\lambda _{j}=0\,\!$ or $\lambda ^{\top }\mathbf {x} =\mathbf {0}$ meaning vectors $\mathbf {x}$ and $\lambda \,\!$ must be orthogonal.

The implementation of the KKT conditions within GLPK is a little more complicated because GLPK supports variables with lower $l_{j}\,\!$ and upper $u_{j}\,\!$ bounds, which also implies no bounds. In general:

minimize or maximize	$z=\mathbf {c} ^{\top }\mathbf {x}$
subject to	${\begin{aligned}&(I\;\|\;-\!A)\mathbf {x} =\mathbf {0} \\&\mathbf {l} \leq \mathbf {x} \leq \mathbf {u} \end{aligned}}$

where $\mathbf {x}$ (as earlier) is the vector of structural and auxiliary variables and $I\,\!$ is an identity matrix. Nonetheless the conditions used in GLPK are equivalent to those shown above and have the same meaning.

Finally, be aware that the KKT conditions KKT.PE and KTT.PB can be calculated for an MIP solution and GLPK will do this on request. In this case, these two conditions are described as "integer feasibility conditions" instead of "Karush-Kahn-Tucker optimality conditions"

Notes

↑ Some readers may not be familiar with the KKT formulation used by GLPK. Textbooks on linear programming often present the optimality conditions in terms of strong duality and complementary slackness. These together represent a special case of the KKT conditions for differentiable optimization.
↑ The LP terminology for equation types is unfortunately inconsistent. This expression is also referred to as the canonical form and the term standard form then applies to something else.
↑ The | symbol represents vector concatenation.
↑ Sottinen, Tommi (2009). Operations research with GNU Linear Programming Kit. ORMS1020 course notes. Department of Mathematics and Statistics, University of Vaasa, Finland. http://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdf.

[1] Some readers may not be familiar with the KKT formulation used by GLPK. Textbooks on linear programming often present the optimality conditions in terms of strong duality and complementary slackness. These together represent a special case of the KKT conditions for differentiable optimization.

[2] The LP terminology for equation types is unfortunately inconsistent. This expression is also referred to as the canonical form and the term standard form then applies to something else.

[3] The | symbol represents vector concatenation.

[4] Sottinen, Tommi (2009). Operations research with GNU Linear Programming Kit. ORMS1020 course notes. Department of Mathematics and Statistics, University of Vaasa, Finland. http://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdf.

[1]

[2]

[3]

[4]

Orientation

Karush-Kahn-Tucker (KKT) optimality conditions

KKT optimality conditions

See also

Notes