9
$\begingroup$

Is it true that the more we add constraint to a constraint programming solver the more efficient it will be? How does this compare to adding constraints in integer programming solvers.

$\endgroup$

1 Answer 1

13
$\begingroup$

This is not true in practice. Moreover, this is something almost impossible to guess without experimenting. Indeed, adding constraints (proven to be mathematical valid, or just guessed by your flair and feeling of the business) to a mathematical optimization model that is solved by constraint programming techniques or integer programming techniques should be good to cut some branches of the enumeration tree (that is, the enumeration of partial solutions), by improving the propagation of constraints and/or the continuous relaxation. On the other hand, constraint programming solvers and integer programming solvers now rely on many heuristic ingredients; adding constraints may be bad for these heuristics. In conclusion, sometimes this is good, sometimes not. Take the time to experiment on the instances you have to solve.

$\endgroup$
2
  • 4
    $\begingroup$ Good answer. Another issue (common to both kinds of solvers): the additional constraints add to the processing time required per node, either because they have to be checked or because there are matrix operations and they make the matrices larger. Constraints that materially reduce the number of nodes processed probably pay for themselves, but redundant constraints likely do not. $\endgroup$
    – prubin
    Oct 7, 2020 at 21:48
  • $\begingroup$ Many thanks @prubin for your kind word and for your valuable remark. $\endgroup$ Oct 8, 2020 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.