Constraints represent the limitations, requirements, and rules that a decision must satisfy. They may describe resource availability, production capacity, minimum service levels, budget limits, technical requirements, or logical conditions. Constraints are expressed using equations, inequalities, or other mathematical relationships. A feasible solution is any assignment of decision-variable values that satisfies all constraints, including variable-domain restrictions such as non-negativity or integrality. A solution may produce an attractive objective value but still be unacceptable if it violates a constraint. Optimization searches for the best solution among feasible solutions, not among all mathematically possible values.
Constraints and Feasible Solutions
Constraints are mathematical conditions that restrict possible decisions, while feasible solutions are decisions satisfying every constraint.
gᵢ(x) ≤ 0
hⱼ(x) = 0
x ≥ 0
Feasible set: S = {x | gᵢ(x) ≤ 0, hⱼ(x) = 0}
Explanation
Variables
x: decision vector
gᵢ(x): inequality constraint
hⱼ(x): equality constraint
S: feasible set
i and j: constraint indices
Example or application
A student has a study budget of 10 hours per week. If x and y represent hours spent on mathematics and programming, the total-time constraint is x + y ≤ 10, with x ≥ 0 and y ≥ 0.
Definition
A constraint is a mathematical condition restricting the allowable values of decision variables. A feasible solution is a decision vector that satisfies all constraints and variable-domain requirements.
Purpose
The purpose of constraints is to ensure that proposed decisions respect the actual limitations and requirements of the problem.
Importance
Constraints prevent unrealistic decisions, represent limited resources, and define the solution space within which an optimal decision must be found.
Learning Objectives
Define constraints and feasible solutions.
Distinguish equality and inequality constraints.
Translate resource limits into mathematical expressions.
Test whether a candidate solution is feasible.
Explain why feasibility must be checked before optimality.
Key Concepts
Constraint
Equality constraint
Inequality constraint
Feasible solution
Feasible set
Non-negativity restriction
Working Principle
Constraints filter out decisions that violate the problem's requirements. The remaining decisions form the feasible set, and an optimization method searches within this set for the best objective value.
Process
Identify every resource limit and required condition.
Translate each condition into an equation or inequality.
Specify variable-domain restrictions.
Test candidate decisions against every condition.
Reject any candidate that violates at least one constraint.
Compare objective values only among feasible candidates.
Applications
Budget allocation
Production capacity planning
Workforce scheduling
Transportation capacity
Energy and material limitations
Worked Example
Consider x + y ≤ 8, x ≥ 0, and y ≥ 0. The candidate (x, y) = (3, 4) is feasible because 3 + 4 = 7 ≤ 8 and both variables are non-negative. The candidate (5, 5) is infeasible because 5 + 5 = 10, which exceeds 8. The candidate (−1, 2) is also infeasible because x violates the non-negativity condition.
Common Misconceptions
A feasible solution is not necessarily optimal.
A candidate must satisfy every constraint, not just most of them.
Non-negativity restrictions are also part of the model.
Equality and inequality constraints describe different types of requirements.
Practice Questions
Define a feasible solution.
Distinguish equality and inequality constraints.
Test whether (2, 5) satisfies x + y ≤ 10, x ≥ 0, y ≥ 0.
Why can a solution with high profit still be infeasible?
Give two examples of resource constraints.
Key Takeaway
Constraints define which decisions are allowed, and only feasible solutions can be considered for optimality.
Prerequisites
Linear inequalities
Decision Variables and Parameters
Mathematical Modelling in Optimization
Reference
Hillier, F. S., and Lieberman, G. J. Introduction to Operations Research.
Bertsimas, D., and Tsitsiklis, J. N. Introduction to Linear Optimization.
Related Topics
Objective Functions
Feasible and Infeasible Regions
Optimal Solutions
Decision-Making Under Constraints
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Optimization & Operations Research