This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(September 2016) (Learn how and when to remove this message)

Inmathematics, aconstraint is a condition of anoptimization problem that the solution must satisfy. There are several types of constraints—primarilyequality constraints,inequality constraints, andinteger constraints. The set ofcandidate solutions that satisfy all constraints is called thefeasible set.^[1]

The following is a simple optimization problem:

${\displaystyle minf(\mathbf{x})=x_1^2+x_2^4}$

subject to

${\displaystyle x_1\ge 1}$

and

${\displaystyle x_2=1,}$

where${\displaystyle \mathbf{x}}$ denotes the vector (x₁,x₂).

In this example, the first line defines the function to be minimized (called theobjective function, loss function, or cost function). The second and third lines define two constraints, the first of which is an inequality constraint and the second of which is an equality constraint. These two constraints arehard constraints, meaning that it is required that they be satisfied; they define the feasible set of candidate solutions.

Without the constraints, the solution would be (0,0), where${\displaystyle f(\mathbf{x})}$ has the lowest value. But this solution does not satisfy the constraints. The solution of theconstrained optimization problem stated above is${\displaystyle \mathbf{x}=(1,1)}$, which is the point with the smallest value of${\displaystyle f(\mathbf{x})}$ that satisfies the two constraints.

• If an inequality constraint holds withequality at the optimal point, the constraint is said to bebinding, as the pointcannot be varied in the direction of the constraint even though doing so would improve the value of the objective function.
• If an inequality constraint holds as astrict inequality at the optimal point (that is, does not hold with equality), the constraint is said to benon-binding, as the pointcould be varied in the direction of the constraint, although it would not be optimal to do so. Under certain conditions, as for example in convex optimization, if a constraint is non-binding, the optimization problem would have the same solution even in the absence of that constraint.
• If a constraint is not satisfied at a given point, the point is said to beinfeasible.

If the problem mandates that the constraints be satisfied, as in the above discussion, the constraints are sometimes referred to ashard constraints. However, in some problems, calledflexible constraint satisfaction problems, it is preferred but not required that certain constraints be satisfied; such non-mandatory constraints are known assoft constraints. Soft constraints arise in, for example,preference-based planning. In aMAX-CSP problem, a number of constraints are allowed to be violated, and the quality of a solution is measured by the number of satisfied constraints.

Global constraints^[2] are constraints representing a specific relation on a number of variables, taken altogether. Some of them, such as thealldifferent constraint, can be rewritten as a conjunction of atomic constraints in a simpler language: thealldifferent constraint holds onn variables${\displaystyle x_1...x_n}$, and is satisfied if the variables take values which are pairwise different. It is semantically equivalent to the conjunction of inequalities${\displaystyle x_1\ne x_2,x_1\ne x_3...,x_2\ne x_3,x_2\ne x_4...x_{n-1}\ne x_n}$. Other global constraints extend the expressivity of the constraint framework. In this case, they usually capture a typical structure of combinatorial problems. For instance, theregular constraint expresses that a sequence of variables is accepted by adeterministic finite automaton.

Global constraints are used^[3] to simplify the modeling ofconstraint satisfaction problems, to extend the expressivity of constraint languages, and also to improve theconstraint resolution: indeed, by considering the variables altogether, infeasible situations can be seen earlier in the solving process. Many of the global constraints are referenced into anonline catalog.

• Beveridge, Gordon S. G.; Schechter, Robert S. (1970)."Essential Features in Optimization".Optimization: Theory and Practice. New York: McGraw-Hill. pp. 5–8.ISBN 0-07-005128-3.

• Nonlinear programming FAQArchived 2019-10-30 at theWayback Machine
• Mathematical Programming GlossaryArchived 2010-03-28 at theWayback Machine

• Mathematical optimization
• Constraint programming

• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from September 2016
• All articles lacking in-text citations
• Webarchive template wayback links