Feasible region

Feasible Region (also feasible set) — in operations research, optimization, and mathematical modeling, is the set of all possible solutions (sets of variable values) that satisfy all the constraints of a problem.

The feasible region constitutes the subspace within which the optimal solution is sought. Any solution outside this region is considered infeasible.

Definition and Formulation

The feasible region is formed by the intersection of the sets defined by each individual constraint of the problem. Constraints can be represented as:

• Inequalities: These establish upper or lower bounds for the values of variables or their combinations (e.g., "consumption of resource A must not exceed 100 units," "the quantity of products manufactured must be at least 50 units").
• Equalities: These require a condition to be met exactly (e.g., "the total volume of shipments must be equal to 1000 tons," "the balance of incoming and outgoing flows is zero").
• Variable sign conditions: Often, variables are required to be non-negative, integer, or belong to a specific discrete set.

A point (or a vector of variable values) belongs to the feasible region if and only if it simultaneously satisfies all these constraints.

Geometric Interpretation

The feasible region often has a clear geometric interpretation, especially in problems with a small number of variables:

• In two-dimensional space (2 variables): Each linear inequality constraint defines a half-plane. The feasible region is the intersection of these half-planes, forming a convex polygon (which may be unbounded or empty).
• In three-dimensional space (3 variables): Each linear inequality constraint defines a half-space. The feasible region is the intersection of these half-spaces, forming a convex polyhedron.
• In multi-dimensional space: A feasible region defined by linear constraints is a convex polytope.

In the case of non-linear constraints, the feasible region can have a more complex shape and may not be convex.

Role in Optimization

The feasible region plays a fundamental role in optimization:

1. Defining the Search Space: The optimal solution to the problem (if one exists) is always located within the feasible region or on its boundary. Optimization algorithms search for the extremum of the objective function specifically within this region.
2. Verifying the Existence of Solutions: If the feasible region is an empty set (i.e., the constraints are contradictory), then the problem has no feasible solutions and, consequently, no optimal solution.
3. Influence on the Optimal Solution: The shape and size of the feasible region directly affect the possibility of reaching an extremum of the objective function and the value of that extremum.

Properties of the Feasible Region (in Linear Programming)

In linear programming (LP) problems, where all constraints and the objective function are linear, the feasible region has important properties:

• Convexity: If two points belong to the feasible region, the entire line segment connecting them also belongs to the region. This property ensures that the optimal solution (if it exists and is unique) will be located at one of the vertices of the feasible region's polytope.
• Closedness: The feasible region includes its boundaries (due to non-strict inequalities ≤, ≥, and equalities).

A feasible region can be:

• Bounded: It has finite dimensions.
• Unbounded: It extends infinitely in one or more directions.
• Empty: It contains no points.

Further Reading

• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

See Also

• Operations research
• Optimization
• Mathematical model
• Constraint
• Feasible solution
• Optimal solution
• Objective function
• Linear programming
• Convex set