Constraints
Constraints
A constraint is a condition that a solution must satisfy.
In operational research, constraints represent limitations, requirements, or rules.
Basic Definition
A constraint restricts the possible values of the decision variables.
If:
\[x=(x_1,x_2,\ldots,x_n)\]then a constraint is a mathematical condition on $x$.
Examples:
\[x_1+x_2\le 100\] \[2x_1+3x_2=50\] \[x_1\ge 0\]Why Constraints Matter
Optimization without constraints may be meaningless.
Example:
\[\max x_1+x_2\]has no finite solution if $x_1$ and $x_2$ can grow forever.
Constraints define what is allowed.
Types of Constraints
Common constraint types:
- equality constraints
- inequality constraints
- sign constraints
- integer constraints
- binary constraints
Equality Constraints
An equality constraint has the form:
\[g(x)=b\]In linear programming:
\[a_1x_1+a_2x_2+\cdots+a_nx_n=b\]Example:
\[x_1+x_2=100\]This means the total must be exactly $100$.
Inequality Constraints
An inequality constraint has the form:
\[g(x)\le b\]or:
\[g(x)\ge b\]In linear programming:
\[a_1x_1+a_2x_2+\cdots+a_nx_n\le b\]or:
\[a_1x_1+a_2x_2+\cdots+a_nx_n\ge b\]Resource Constraints
Resource limits usually use $\le$.
Example:
\[2x_1+3x_2\le 120\]This could mean:
- product 1 uses 2 hours
- product 2 uses 3 hours
- at most 120 hours are available
Requirement Constraints
Minimum requirements usually use $\ge$.
Example:
\[3x_1+2x_2\ge 60\]This could mean production must satisfy at least 60 units of demand.
Sign Constraints
Many variables represent quantities and must be nonnegative:
\[x_j\ge 0\]For all variables:
\[x\ge 0\]means:
\[x_1\ge 0,\quad x_2\ge 0,\quad \ldots,\quad x_n\ge 0\]Integer Constraints
If a variable must be an integer:
\[x_j\in\mathbb{Z}\]This is common when variables count objects:
- workers
- machines
- vehicles
- people
- selected items
Binary Constraints
A binary constraint forces a variable to be either $0$ or $1$:
\[x_j\in\{0,1\}\]This models yes/no decisions.
Examples:
- open a facility or not
- choose an item or not
- assign a worker or not
Linear Constraints
A constraint is linear if variables only appear to the first power and are not multiplied together.
Linear:
\[2x_1+3x_2\le 10\]Not linear:
\[x_1x_2\le 10\] \[x_1^2+x_2\le 10\] \[\sqrt{x_1}+x_2\le 10\]Constraint Matrix Form
Many linear constraints can be written compactly as:
\[Ax\le b\]or:
\[Ax=b\]where:
- $A$ is the constraint matrix
- $x$ is the decision vector
- $b$ is the right-hand side vector
Example
The constraints:
\[2x_1+3x_2\le 120\] \[5x_1+x_2\le 80\]can be written as:
\[\begin{bmatrix} 2 & 3 \\ 5 & 1 \end{bmatrix} \begin{bmatrix} x_1\\ x_2 \end{bmatrix} \le \begin{bmatrix} 120\\ 80 \end{bmatrix}\]Standard Form Constraints
A standard-form LP uses equality constraints and nonnegative variables:
\[Ax=b\] \[x\ge 0\]So inequalities must be converted into equalities.
Slack Variables
A $\le$ constraint can be converted into equality by adding a slack variable.
Example:
\[2x_1+3x_2\le 120\]becomes:
\[2x_1+3x_2+s=120\]with:
\[s\ge 0\]The slack variable measures unused resource:
\[s=120-2x_1-3x_2\]Surplus Variables
A $\ge$ constraint can be converted into equality by subtracting a surplus variable.
Example:
\[2x_1+3x_2\ge 120\]becomes:
\[2x_1+3x_2-s=120\]with:
\[s\ge 0\]The surplus variable measures how much the left-hand side exceeds the requirement.
Active Constraints
A constraint is active at a point if it holds as equality.
Example:
\[x_1+2x_2\le 10\]At:
\[x=(2,4)\]we have:
\[2+2(4)=10\]so the constraint is active.
At:
\[x=(1,1)\]we have:
\[1+2(1)=3<10\]so the constraint is not active.
Binding and Nonbinding Constraints
In optimization language:
- active constraint = binding constraint
- inactive constraint = nonbinding constraint
A binding resource constraint means the resource is fully used.
A nonbinding resource constraint means some slack remains.
Constraint Interpretation
When formulating a model, every constraint should have a real-world meaning.
Examples:
| Real-world rule | Mathematical form |
|---|---|
| use no more than 100 hours | $\le 100$ |
| produce at least 50 units | $\ge 50$ |
| spend exactly the budget | $= B$ |
| quantity cannot be negative | $x_j\ge 0$ |
| number of workers must be integer | $x_j\in\mathbb{Z}$ |
Common Mistake: Wrong Inequality Direction
If the problem says:
at most
use:
\[\le\]If the problem says:
at least
use:
\[\ge\]If the problem says:
exactly
use:
$$
$$
Common Mistake: Missing Nonnegativity
Always include nonnegativity when variables represent quantities:
\[x_j\ge 0\]Without it, the model may allow impossible negative production, negative food, or negative investment.
Checklist
You understand constraints if you can:
- identify equality constraints
- identify inequality constraints
- choose the correct inequality direction
- explain sign constraints
- write constraints from word problems
- convert $\le$ constraints using slack variables
- convert $\ge$ constraints using surplus variables
- identify active constraints
- write constraints in matrix form
See Also
- Optimization Foundations
- Decision Variables
- Objective Functions
- Feasible Sets
- Standard Form
- Slack Variables
- Surplus Variables
Exam checkpoint
In exam problems, translate the story into variables, objective, constraints, feasible set, and optimal value. Always state whether the problem is a maximization or minimization and what the units are.