Active Constraints

Standing at a point of a feasible region, some restrictions are pressing and the rest have room to spare. The ones holding with equality form the active set, and they are what pins a point down: how many hold, and whether their normals are independent, decides whether the point is a corner, an edge point, or interior.

Definition

Let the feasible region be described by constraints $a_{i}^{T} x \leq b_{i}$ for $i \in I$ , $a_{i}^{T} x = b_{i}$ for $i \in E$ , and $x_{j} \geq 0$ for $j = 1, \dots, n$ .

At a feasible point $\bar{x}$ , a constraint is active (equivalently tight, or binding) when it holds with equality there:

A (\bar{x}) = {i \in I \cup E : a_{i}^{T} \bar{x} = b_{i}} \cup {j : {\bar{x}}_{j} = 0} .

A constraint holding strictly, $a_{i}^{T} \bar{x} < b_{i}$ , or ${\bar{x}}_{j} > 0$ , is inactive at $\bar{x}$ .

Three observations follow directly.

Equality constraints are active everywhere. Every $i \in E$ belongs to $A (\bar{x})$ for every feasible $\bar{x}$ , since feasibility is equality for those rows. They never distinguish one feasible point from another.

Nonnegativity restrictions are constraints. A component sitting at zero is an active constraint exactly as much as a resource limit reached exactly. In standard form, where $A x = b$ carries every structural row, the nonnegativity restrictions are the only ones that vary from point to point.

Activity is a property of a point, not of a constraint. The same inequality is active at some feasible points and inactive at others. "This constraint is binding" is shorthand for "binding at the point under discussion", and the point must be recoverable from context or the statement means nothing.

Formal statement

$A (\bar{x}) = {i : a_{i}^{T} \bar{x} = b_{i}} \cup {j : {\bar{x}}_{j} = 0}$ . A point $\bar{x} \in R^{n}$ is a vertex of the feasible region when the active constraint normals at $\bar{x}$ span $R^{n}$ , that is when $rank {a_{i} : i \in A (\bar{x})} = n$ counting nonnegativity rows as unit vectors $e_{j}$ .

Assumptions and scope

Activity is defined only at feasible points. Asking which constraints are active at an infeasible point is not meaningful, since some constraint is violated rather than merely tight.
Equality constraints are active at every feasible point and therefore carry no information distinguishing points. Counting them into a comparison between two points is a common source of confusion.
Nonnegativity restrictions count as constraints and are active exactly where a component is zero. In standard form they are the only constraints whose activity varies.
What makes a point a vertex is the rank of the active normals, not their number. Three active constraints in two variables may still leave a direction free if two of the normals are parallel.
An inactive constraint cannot be deleted from the problem. It is inactive at one point, and removing it changes the feasible region and potentially the optimum.

Worked material

Example

The active set at four points of one region

Take the region

x_{1} + x_{2} \leq 4, x_{1} \leq 3, x_{1} \geq 0, x_{2} \geq 0,

with $n = 2$ , and label the constraints $C_{1}, C_{2}$ and the restrictions $N_{1}, N_{2}$ .

The point $(1, 1)$ . $C_{1}$ : $2 < 4$ , slack. $C_{2}$ : $1 < 3$ , slack. Both components positive. Active set empty, rank $0$ , two free directions. Interior.

The point $(3, 0.5)$ . $C_{1}$ : $3.5 < 4$ , slack. $C_{2}$ : $3 = 3$ , active. $N_{2}$ : $x_{2} = 0.5 > 0$ , slack. Active set ${C_{2}}$ , normal $(1, 0)$ , rank $1$ , one free direction. On a face.

The point $(3, 1)$ . $C_{1}$ : $4 = 4$ , active. $C_{2}$ : $3 = 3$ , active. Normals $(1, 1)$ and $(1, 0)$ are independent, rank $2 = n$ . No free direction. A vertex.

The point $(0, 4)$ . $C_{1}$ : $4 = 4$ , active. $C_{2}$ : $0 < 3$ , slack. $N_{1}$ : $x_{1} = 0$ , active. Normals $(1, 1)$ and $e_{1} = (1, 0)$ , independent, rank $2$ . A vertex, and note that one of the two constraints pinning it is a nonnegativity restriction, not a numbered constraint.

The same four constraints throughout. What varies is which are active, and that is what distinguishes the four positions.

Non-example

What is not an active constraint

Not active: a constraint that is merely close. At $(2.99, 1)$ in the earlier region, $C_{2}$ gives $2.99 < 3$ . Nearly tight is inactive. There is no tolerance in the definition, and introducing one turns a rank computation into a judgement call.

Not active: a violated constraint. At $(4, 1)$ , $C_{2}$ gives $4 > 3$ . That constraint is not active; the point is infeasible and the active set is not defined there at all. Violation and equality are different relations, and only one of them is activity.

Not a reason to count it: an equality constraint distinguishing points. In standard form both structural rows are active at every feasible point. Citing them to explain why this point is a vertex rather than that one explains nothing, since they are equally active at both.

Not enough for a vertex: three active constraints in two variables. If two of the three normals are parallel, say $x_{1} \leq 3$ and $2 x_{1} \leq 6$ , whose normals are $(1, 0)$ and $(2, 0)$ , then three active constraints have rank $2$ at best, and possibly less. It is the rank that decides, and counting is not a substitute for it.

Not removable: an inactive constraint. Dropping $C_{1}$ from the region because it is slack at $(1, 1)$ changes the region: $(3, 3)$ then becomes feasible, and the vertex at $(3, 1)$ disappears. The constraint was inactive at one point, not inert.

Contrast

Inactive here does not mean unnecessary

The word 'inactive' suggests a constraint that is not doing anything, and the suggestion is wrong in a way that has consequences.

The tempting move. Solving a program, you observe that the constraint $x_{1} + x_{2} \leq 4$ has slack at the point you are examining, and conclude it can be dropped to simplify the problem.

Why it fails. Activity is a property of a point. Take the region $x_{1} + x_{2} \leq 4$ , $x_{1} \leq 3$ , $x_{1}, x_{2} \geq 0$ , and examine $(1, 1)$ , where the first constraint indeed has slack. Now drop it. The region was a quadrilateral with vertices $(0, 0)$ , $(3, 0)$ , $(3, 1)$ and $(0, 4)$ ; without that constraint it becomes an unbounded strip running upward between $x_{1} = 0$ and $x_{1} = 3$ . The vertex $(3, 1)$ is gone and so is the bound on $x_{2}$ . Maximise $x_{2}$ over each and the answers are $4$ and no finite optimum. A different problem with a different verdict.

The general statement. A constraint's job is to exclude points, and a constraint inactive at $\bar{x}$ is excluding points elsewhere. What can be dropped without changing the region is a redundant constraint, one whose removal leaves the feasible set unchanged, and redundancy is a property of the constraint against the whole system, decided globally, not by inspecting one point.

The confusion this actually causes. In the simplex method a learner who has conflated the two expects the algorithm to discard slack constraints as it goes. It does not. Every constraint remains in the system for every iteration; what changes is which are active at the current basic feasible solution, and a constraint slack at this corner may be exactly the one that limits the step at the next.

Common errors

Common misconception

A constraint that is not active at the current point is not doing any work, so it can be dropped from the problem.

Active Constraints

Assumptions and scope

Worked material

The active set at four points of one region

What is not an active constraint

Inactive here does not mean unnecessary

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history