imported>Float59: Reworded second sentence since it repeated what was in the first sentence

2024-05-28T13:47:16Z

Reworded second sentence since it repeated what was in the first sentence

New page

{{Short description|Mathematical concept}}
In an [[optimization problem]], a '''slack variable''' is a variable that is added to an [[inequality constraint]] to transform it into an equality constraint. A non-negativity constraint on the slack variable is also added.<ref>{{cite book|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|access-date=October 15, 2011}}</ref>{{rp|131}}

Slack variables are used in particular in [[linear programming]]. As with the other variables in the augmented constraints, the slack variable cannot take on negative values, as the [[simplex algorithm]] requires them to be positive or zero.<ref>{{Cite Gartner Matousek 2006}}{{rp|42}}</ref>

* If a slack variable associated with a constraint is ''zero'' at a particular [[candidate solution]], the [[constraint (mathematics)|constraint]] is '''[[binding constraint|binding]]''' there, as the constraint restricts the possible changes from that point.
* If a slack variable is ''positive'' at a particular candidate solution, the constraint is '''[[non-binding constraint|non-binding]]''' there, as the constraint does not restrict the possible changes from that point.
* If a slack variable is ''negative'' at some point, the point is [[feasible region|infeasible]] (not allowed), as it does not satisfy the constraint.

Slack variables are also used in the [[Big M method]].

==Example==
By introducing the slack variable <math>\mathbf{s} \ge \mathbf{0}</math>, the inequality
<math>\mathbf{A}\mathbf{x} \le \mathbf{b}</math> can be converted to the equation
<math>\mathbf{A}\mathbf{x} + \mathbf{s} = \mathbf{b}</math>.

== Embedding in orthant ==
{{further|Orthant|Generalized barycentric coordinates}}

Slack variables give an embedding of a [[polytope]] <math>P \hookrightarrow (\mathbf{R}_{\geq 0})^f</math> into the standard ''f''-[[orthant]], where <math>f</math> is the number of constraints (facets of the polytope). This map is one-to-one (slack variables are uniquely determined) but not onto (not all combinations can be realized), and is expressed in terms of the ''constraints'' (linear functionals, covectors).

Slack variables are ''[[Dual linear program|dual]]'' to [[generalized barycentric coordinates]], and, dually to generalized barycentric coordinates (which are not unique but can all be realized), are uniquely determined, but cannot all be realized.

Dually, generalized barycentric coordinates express a polytope with <math>n</math> vertices (dual to facets), regardless of dimension, as the ''image'' of the standard <math>(n-1)</math>-simplex, which has <math>n</math> vertices – the map is onto: <math>\Delta^{n-1} \twoheadrightarrow P,</math> and expresses points in terms of the ''vertices'' (points, vectors). The map is one-to-one if and only if the polytope is a simplex, in which case the map is an isomorphism; this corresponds to a point not having ''unique'' generalized barycentric coordinates.

==References==
{{reflist}}

==External links==
* [http://apmonitor.com/wiki/index.php/Main/SlackVariables Slack Variable Tutorial] - Solve slack variable problems online

[[Category:Linear programming]]

Slack variable - Revision history

imported>Float59: Reworded second sentence since it repeated what was in the first sentence