0
$\begingroup$

What are the differences between these two topics? I took courses a long time ago on these subjects, and the theory seemed to be the same. Yet I sometimes see people making a distinction between them.

$\endgroup$
3
$\begingroup$

Disclaimer: All generalizations in what follows are true except when they are not.

Constraint programming somewhat straddles operations research (analysis of systems with an eye toward using mathematical/statistical tools for decision making) and computer science (determining solutions to combinations of logical expressions, testing whether such solutions exist, ...).

Within OR, constraint programming and discrete optimization (integer or mixed integer linear programming) are often viewed as competing tools for the same types of optimization problems. Constraint programming offers more natural ways of expressing certain types of models (such as where a decision acts as an index of another decision), and there are specialized global constraints for certain things (such as "all different" for permutations, constraints to prevent time intervals from overlapping, ...). Some of those constraints seem to make constraint programming appealing in scheduling problems in particular.

On the other hand, constraint programming generally lacks the bounding inherent in discrete optimization algorithms, which has two impacts. First, if you stop a constraint solver before all possibilities are exhausted, you may not have any idea how close your solution is to optimal. Second, bounding allows integer programming solvers to prune ("fathom") nodes in the search tree when their bounds are worse than the current best known solution. The absence of that is likely to mean that a constraint solver would have to search a larger portion of the solution space than an integer programming solver would.

$\endgroup$
  • 1
    $\begingroup$ I would add that OR is a broader field that includes not only optimization (of which constraint programming is one flavor) but also stochastic processes and other tools for modeling random systems, plus applications, like supply chain, health care, energy... $\endgroup$ – LarrySnyder610 May 6 at 19:21
1
$\begingroup$

Operations research as a discipline is concerned with optimal decision making. This can be achieved by several techniques including mathematical programming or constraint programming.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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