This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Feasible region" – news ·newspapers ·books ·scholar ·JSTOR(November 2018) (Learn how and when to remove this message)

Inmathematical optimization andcomputer science, afeasible region,feasible set, orsolution space is the set of all possible points (sets of values of the choice variables) of anoptimization problem that satisfy the problem'sconstraints, potentially includinginequalities,equalities, andinteger constraints.^[1] This is the initial set ofcandidate solutions to the problem, before the set of candidates has been narrowed down.

For example, consider the problem of minimizing the function${\displaystyle x^2+y^4}$ with respect to the variables${\displaystyle x}$ and${\displaystyle y,}$ subject to${\displaystyle 1\le x\le 10}$ and${\displaystyle 5\le y\le 12.}$ Here the feasible set is the set of pairs (x,y) in which the value ofx is at least 1 and at most 10 and the value ofy is at least 5 and at most 12. The feasible set of the problem is separate from theobjective function, which states the criterion to be optimized and which in the above example is${\displaystyle x^2+y^4.}$

In many problems, the feasible set reflects a constraint that one or more variables must be non-negative. In pureinteger programming problems, the feasible set is the set of integers (or some subset thereof). Inlinear programming problems, the feasible set is aconvexpolytope: a region inmultidimensional space whose boundaries are formed byhyperplanes and whose corners arevertices.

Constraint satisfaction is the process of finding a point in the feasible region.

Aconvex feasible set is one in which a line segment connecting any two feasible points goes through only other feasible points, and not through any points outside the feasible set. Convex feasible sets arise in many types of problems, including linear programming problems, and they are of particular interest because, if the problem has aconvex objective function that is to be minimized, it will generally be easier to solve in the presence of a convex feasible set and anylocal optimum will also be aglobal optimum.

If the constraints of an optimization problem are mutually contradictory, there are no points that satisfy all the constraints and thus the feasible region is theempty set. In this case the problem has no solution and is said to beinfeasible.

Feasible sets may bebounded or unbounded. For example, the feasible set defined by the constraint set {x ≥ 0,y ≥ 0} is unbounded because in some directions there is no limit on how far one can go and still be in the feasible region. In contrast, the feasible set formed by the constraint set {x ≥ 0,y ≥ 0,x + 2y ≤ 4} is bounded because the extent of movement in any direction is limited by the constraints.

In linear programming problems withn variables, anecessary but insufficient condition for the feasible set to be bounded is that the number of constraints be at leastn + 1 (as illustrated by the above example).

If the feasible set is unbounded, there may or may not be an optimum, depending on the specifics of the objective function. For example, if the feasible region is defined by the constraint set {x ≥ 0,y ≥ 0}, then the problem of maximizingx +y has no optimum since any candidate solution can be improved upon by increasingx ory; yet if the problem is tominimizex +y, then there is an optimum (specifically at (x,y) = (0, 0)).

Inoptimization and other branches ofmathematics, and insearch algorithms (a topic incomputer science), acandidate solution is amember of theset of possible solutions in the feasible region of a given problem.^[2] A candidate solution does not have to be a likely or reasonable solution to the problem—it is simply in the set that satisfies allconstraints; that is, it is in the set offeasible solutions. Algorithms for solving various types of optimization problems often narrow the set of candidate solutions down to a subset of the feasible solutions, whose points remain as candidate solutions while the other feasible solutions are henceforth excluded as candidates.

The space of all candidate solutions, before any feasible points have been excluded, is called the feasible region, feasible set, search space, or solution space.^[2] This is the set of all possible solutions that satisfy the problem's constraints.Constraint satisfaction is the process of finding a point in the feasible set.

In the case of thegenetic algorithm, the candidate solutions are the individuals in the population being evolved by the algorithm.^[3]

In calculus, an optimal solution is sought using thefirst derivative test: thefirst derivative of the function being optimized is equated to zero, and any values of the choice variable(s) that satisfy this equation are viewed as candidate solutions (while those that do not are ruled out as candidates). There are several ways in which a candidate solution might not be an actual solution. First, it might give a minimum when a maximum is being sought (or vice versa), and second, it might give neither a minimum nor a maximum but rather asaddle point or aninflection point, at which a temporary pause in the local rise or fall of the function occurs. Such candidate solutions may be able to be ruled out by use of thesecond derivative test, the satisfaction of which is sufficient for the candidate solution to be at least locally optimal. Third, a candidate solution may be alocal optimum but not aglobal optimum.

In takingantiderivatives ofmonomials of the form${\displaystyle x^n,}$ the candidate solution usingCavalieri's quadrature formula would be${\displaystyle \frac{1}{n+1}{x}^{n+1}+C.}$ This candidate solution is in fact correct except when${\displaystyle n=-1.}$

In thesimplex method for solvinglinear programming problems, avertex of the feasiblepolytope is selected as the initial candidate solution and is tested for optimality; if it is rejected as the optimum, an adjacent vertex is considered as the next candidate solution. This process is continued until a candidate solution is found to be the optimum.

• Optimal decisions
• Mathematical optimization

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from November 2018
• All articles needing additional references