HOME

TheInfoList



OR:

In mathematics, a constraint is a condition of an
optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
problem that the solution must satisfy. There are several types of constraints—primarily
equality Equality may refer to: Society * Political equality, in which all members of a society are of equal standing ** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elit ...
constraints,
inequality Inequality may refer to: Economics * Attention inequality, unequal distribution of attention across users, groups of people, issues in etc. in attention economy * Economic inequality, difference in economic well-being between population groups * ...
constraints, and integer constraints. The set of
candidate solution In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...
s that satisfy all constraints is called the
feasible set In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, poten ...
.


Example

The following is a simple optimization problem: :\min f(\mathbf x) = x_1^2+x_2^4 subject to :x_1 \ge 1 and :x_2 = 1, where \mathbf x denotes the vector (''x''1, ''x''2). In this example, the first line defines the function to be minimized (called the
objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
, 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 are
hard constraint In mathematical optimization, constrained optimization (in some contexts called constraint optimization) is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The obj ...
s, 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 f(\mathbf x) has the lowest value. But this solution does not satisfy the constraints. The solution of the constrained optimization problem stated above is \mathbf x = (1,1), which is the point with the smallest value of f(\mathbf x) that satisfies the two constraints.


Terminology

* If an inequality constraint holds with ''equality'' at the optimal point, the constraint is said to be , as the point ''cannot'' 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 a ''strict inequality'' at the optimal point (that is, does not hold with equality), the constraint is said to be , as the point ''could'' 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 be infeasible.


Hard and soft constraints

If the problem mandates that the constraints be satisfied, as in the above discussion, the constraints are sometimes referred to as ''hard constraints''. However, in some problems, called flexible constraint satisfaction problems, it is preferred but not required that certain constraints be satisfied; such non-mandatory constraints are known as '' soft constraints''. Soft constraints arise in, for example, preference-based planning. In a MAX-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

Global constraints are constraints representing a specific relation on a number of variables, taken altogether. Some of them, such as th
alldifferent
constraint, can be rewritten as a conjunction of atomic constraints in a simpler language: the alldifferent constraint holds on ''n'' variables 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 x_1 \neq x_2, x_1 \neq x_3..., x_2 \neq x_3, x_2 \neq x_4 ... x_ \neq 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, the regular constraint expresses that a sequence of variables is accepted by a
deterministic finite automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state autom ...
. Global constraints are used to simplify the modeling of
constraint satisfaction problems Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constr ...
, to extend the expressivity of constraint languages, and also to improve the constraint 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 a
online catalog.


See also

*
Constraint algebra In theoretical physics, a constraint algebra is a linear space of all constraints and all of their polynomial functions or functionals whose action on the physical vectors of the Hilbert space should be equal to zero. For example, in electromagne ...
*
Karush–Kuhn–Tucker conditions In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be op ...
*
Lagrange multipliers In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied e ...
*
Level set In mathematics, a level set of a real-valued function of real variables is a set where the function takes on a given constant value , that is: : L_c(f) = \left\~, When the number of independent variables is two, a level set is calle ...
* Linear programming *
Nonlinear programming In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or s ...
*
Restriction Restriction, restrict or restrictor may refer to: Science and technology * restrict, a keyword in the C programming language used in pointer declarations * Restriction enzyme, a type of enzyme that cleaves genetic material Mathematics and logi ...
*
Satisfiability modulo theories In computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involvi ...


References


Further reading

* {{cite book , first=Gordon S. G. , last=Beveridge , first2=Robert S. , last2=Schechter , chapter=Essential Features in Optimization , title=Optimization: Theory and Practice , location=New York , publisher=McGraw-Hill , year=1970 , pages=5–8 , isbn=0-07-005128-3 , chapter-url=https://books.google.com/books?id=TfhVXlWtOPQC&pg=PA5


External links


Nonlinear programming FAQMathematical Programming Glossary
Mathematical optimization Constraint programming ca:Restricció es:Restricción (matemáticas)