Slack variable
Encyclopedia
In an optimization problem
, a slack variable is a variable that is added to an inequality constraint to transform it to an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a nonnegativity constraint.
In linear programming
, this is required to turn an inequality into an equality where a linear combination of variables is less than or equal to a given constant in the former. 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.
, the inequality
can be converted to the equation
. Solve slack variable problem.
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
-simplex, which has n vertices – the map is onto: 
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.
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
, a slack variable is a variable that is added to an inequality constraint to transform it to an equality. Introducing a slack variable replaces an inequality constraint with an equality constraint and a nonnegativity constraint.
In linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
, this is required to turn an inequality into an equality where a linear combination of variables is less than or equal to a given constant in the former. As with the other variables in the augmented constraints, the slack variable cannot take on negative values, as the Simplex algorithm
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
requires them to be positive or zero.
- If the slack variable associated with a constraint is zero in a given state, the constraint is binding, as the constraint restricts the possible changes of the point.
- If a slack variable is positive in a given state, the constraint is non-binding, as the constraint does not restrict the possible changes of the point.
- If a slack variable is negative in a given state, the point is infeasible, and not allowed, as it does not satisfy the constraint.
Example
By introducing the slack variable, the inequality can be converted to the equation. Solve slack variable problem.Embedding in orthant
Slack variables give an embedding of a polytope into the standard f-orthantOrthant
In geometry, an orthant or hyperoctant is the analogue in n-dimensional Euclidean space of a quadrant in the plane or an octant in three dimensions....
, 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
-simplex, which has n vertices – the map is onto: 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.