Content deleted Content added
→Solution methods: more detail |
|||
Line 19:
==Solution methods==
===Equality constraints===
If the constrained problem has only equality constraints, the method of [[Lagrange multipliers]] can be used to convert it into an unconstrained problem whose number of variables is the original number of variables plus the original number of equality constraints. If the constraints are all equality constraints and are all linear, they can be solved for some of the variables in terms of the others, and the former can be substituted out of the objective function, leaving an unconstrained problem in a smaller number of variables.
===Inequality constraints===
With inequality constraints, the problem can be characterized in terms of the [[Karush–Kuhn–Tucker conditions]], which in simple problems may be solvable.
===Linear programming===
If the objective function and all of the hard constraints are linear, then the problem is a [[linear programming]] problem. This can be solved by the [[simplex method]], which usually works in [[polynomial time]] in the problem size but is not guaranteed to, or by [[interior point method]]s which are guaranteed to work in polynomial time.
===Quadratic programming===
If all the hard constraints are linear but the objective function is quadratic, the problem is a [[quadratic programming]] problem. It can still be solved in polynomial time by the [[ellipsoid method]] if the objective function is [[Convex function|convex]]; otherwise the problem is [[NP hard]].
===
====Branch and bound====
Constraint optimization can be solved by [[branch and bound]] algorithms. These are backtracking algorithms storing the cost of the best solution found during execution and use it for avoiding part of the search. More precisely, whenever the algorithm encounters a partial solution that cannot be extended to form a solution of better cost than the stored best cost, the algorithm backtracks, instead of trying to extend this solution.
Line 33 ⟶ 45:
On the other hand, this estimated cost cannot be lower than the effective cost that can be obtained by extending the solution, as otherwise the algorithm could backtrack while a solution better than the best found so far exists. As a result, the algorithm requires an upper bound on the cost that can be obtained from extending a partial solution, and this upper bound should be as small as possible.
=====First-choice bounding functions=====
One way for evaluating this upper bound for a partial solution is to consider each soft constraint separately. For each soft constraint, the maximal possible value for any assignment to the unassigned variables is assumed. The sum of these values is an upper bound because the soft constraints cannot assume a higher value. It is exact because the maximal values of soft constraints may derive from different evaluations: a soft constraint may be maximal for <math>x=a</math> while another constraint is maximal for <math>x=b</math>.
=====Russian doll search=====
This method runs a branch-and-bound algorithm on <math>n</math> problems, where <math>n</math> is the number of variables. Each such problem is the subproblem obtained by dropping a sequence of variables <math>x_1,\ldots,x_i</math> from the original problem, along with the constraints containing them. After the problem on variables <math>x_{i+1},\ldots,x_n</math> is solved, its optimal cost can be used as an upper bound while solving the other problems,
Line 43 ⟶ 55:
In particular, the cost estimate of a solution having <math>x_{i+1},\ldots,x_n</math> as unassigned variables is added to the cost that derives from the evaluated variables. Virtually, this corresponds on ignoring the evaluated variables and solving the problem on the unassigned ones, except that the latter problem has already been solved. More precisely, the cost of soft constraints containing both assigned and unassigned variables is estimated as above (or using an arbitrary other method); the cost of soft constraints containing only unassigned variables is instead estimated using the optimal solution of the corresponding problem, which is already known at this point.
====Bucket elimination====
The [[bucket elimination]] algorithm can be adapted for constraint optimization. A given variable can be indeed removed from the problem by replacing all soft constraints containing it with a new soft constraint. The cost of this new constraint is computed assuming a maximal value for every value of the removed variable. Formally, if <math>x</math> is the variable to be removed, <math>C_1,\ldots,C_n</math> are the soft constraints containing it, and <math>y_1,\ldots,y_m</math> are their variables except <math>x</math>, the new soft constraint is defined by:
| |||