In an
optimization problem
In mathematics, computer science and economics, 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 ...
, a slack variable is a variable that is added to an
inequality constraint
In mathematics, a constraint is a condition of an optimization problem that the solution must satisfy. There are several types of constraints—primarily equality constraints, inequality constraints, and integer constraints. The set of can ...
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.
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
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...
requires them to be positive or zero.
* If a slack variable associated with a constraint is ''zero'' at a particular
candidate solution
In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...
, 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
A non-binding resolution is a written motion adopted by a deliberative body that can or cannot progress into a law. The substance of the resolution can be anything that can normally be proposed as a motion.
This type of resolution is often used ...
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.
Slack variables are also used in the
Big M method
In operations research, the Big M method is a method of solving linear programming problems using the simplex algorithm. The Big M method extends the simplex algorithm to problems that contain "greater-than" constraints. It does so by associating ...
.
Example
By introducing the slack variable
, the inequality
can be converted to the equation
.
Embedding in orthant
Slack variables give an embedding of a
polytope
In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
into the standard ''f''-
orthant
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.
In general an orthant in ''n''-dimensions can be considered the intersection of ''n'' mutua ...
, where
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
vertices (dual to facets), regardless of dimension, as the ''image'' of the standard
-simplex, which has
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.
References
{{reflist
External links
Slack Variable Tutorial- Solve slack variable problems online
Linear programming