In an optimization problem, a slack variable is a variable that added to an inequality constraint to transform it into an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a non-negativity constraint on the slack variable.[1]: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.[2]
If a slack variable associated with a constraint is zero at a particular candidate solution, the constraint is 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 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 infeasible (not allowed), as it does not satisfy the constraint.
Example
By introducing the slack variable \( {\displaystyle \mathbf {y} \geq \mathbf {0} } \) , the inequality \( {\mathbf {A}}{\mathbf {x}}\leq {\mathbf {b}} \) can be converted to the equation \( {\displaystyle \mathbf {A} \mathbf {x} +\mathbf {y} =\mathbf {b} }. \)
Embedding in orthant
Further information: Orthant and Generalized barycentric coordinates
Slack variables give an embedding of a polytope \( P \hookrightarrow (\mathbf{R}_{\geq 0})^f \) into the standard f-orthant, where f 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 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 n vertices (dual to facets), regardless of dimension, as the image of the standard (n-1)-simplex, which has n vertices – the map is onto: \( \Delta ^{{n-1}}\twoheadrightarrow P \) , 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
Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 15, 2011.
Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8.:42
External links
Slack Variable Tutorial - Solve slack variable problems online
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
