Active Constraints

An active constraint is a constraint that holds with equality at a specific point.

Inequality Constraints

For

the constraint is active at $x$ if

It is inactive if $a_i^Tx<b_i$. For $a_i^Tx\ge b_i$, it is active in the same way: equality must hold.

Equality Constraints

An equality constraint

is active at every feasible point. If it fails, the point is simply infeasible.

Nonnegativity Constraints

In standard form, $x_j\ge 0$ is active exactly when

At a basic solution, all nonbasic variables are zero, so their nonnegativity constraints are active.

Slack and Surplus

For $a_i^Tx+s_i=b_i$, the original $\le$ constraint is active when $s_i=0$.

For $a_i^Tx-s_i=b_i$, the original $\ge$ constraint is active when $s_i=0$.

Vertices

Vertices occur where enough independent constraints are active to pin down a point.

In $\mathbb{R}^2$, this usually means two active boundary lines. In $\mathbb{R}^n$, it usually means $n$ linearly independent active constraints.

Checklist

Given a point, substitute it into every constraint and mark which ones are tight. Those are the active constraints.

See Also

• Slack Variables
• Surplus Variables
• Vertices
• Basic Feasible Solutions

Exam checkpoint

For BFS questions, convert to standard form before checking the point. A candidate in original variables must be lifted with slack and surplus variables before testing basis columns.