✦ScienexySCIENCE KNOWLEDGE LIBRARY
reference · SCI-MAT-013-011

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

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.

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