3 ms·

Thank you for the explanation. Any idea why one would choose to use CP over an LP, IP, or MIP solver? Maybe some CP problems can't be translated? I'm not sure w

Thank you for the explanation. Any idea why one would choose to use CP over an LP, IP, or MIP solver? Maybe some CP problems can't be translated? I'm not sure what the mathematical relationship is.

wenc 8y ago
Most MIP solvers contain performance heuristics tailored to MIP metaphors. If you're using translation, some CPs could translate into MIP formulations that MIP-solvers happen to not handle that well (these are theoretical worst-case exponential problems, and you can't know a priori if your solver is going to hit the worst case; MIP solvers are fast in general but there's a measure of luck involved in the solution process -- anyone who does discrete optimization for a living knows this). You're also at the mercy of the translation algorithm, which may not possess a library of the most efficient MIP formulations. Furthermore, MIP modeling is an art which takes years to hone (less so today than when I started -- algorithms are getting more and more sophisticated -- but nevertheless, it takes human reasoning and intuition to produce a good formulation). It's always useful have a range of solvers at your disposal and not limit yourself. CP solvers are specialized to CP problems and for simple problems they may work better due to less translation overhead.
skosch 8y ago
MIP solvers work themselves through the search tree using all sorts of clever tricks, constantly running LPs on relaxations (approximations) of the problem to prune the tree. They can be very efficient, but the constraints need to be linear for the LPs to work. CP solvers are less sophisticated in their search (although some are getting more clever [1]), but they instead delegate to graph-theoretical algorithms [2] that can efficiently deal with more high-level constraints, for instance "I only want solutions where all these variables have different values", which in the MIP world would translate to tons of auxiliary linear constraints and variables that would slow down your solver. So it really depends on how you write your model, and it's not even always obvious whether MIP or CP is better – which is why Minizinc is so useful. There are even attempts to automatically choose the algorithm to use based on the problem structure [3]. [1] https://github.com/chuffed/chuffed https://github.com/chuffed/chuffed [2] http://www.emn.fr/x-info/sdemasse/gccat/sec5.html http://www.emn.fr/x-info/sdemasse/gccat/sec5.html [3] https://github.com/CP-Unibo/sunny-cp https://github.com/CP-Unibo/sunny-cp

Thank you for the explanation. Any idea why one would choose to use CP over an LP, IP, or MIP solver? Maybe some CP problems can't be translated? I'm not sure what the mathematical relationship is.

wenc 8y ago

Most MIP solvers contain performance heuristics tailored to MIP metaphors. If you're using translation, some CPs could translate into MIP formulations that MIP-solvers happen to not handle that well (these are theoretical worst-case exponential problems, and you can't know a priori if your solver is going to hit the worst case; MIP solvers are fast in general but there's a measure of luck involved in the solution process -- anyone who does discrete optimization for a living knows this). You're also at the mercy of the translation algorithm, which may not possess a library of the most efficient MIP formulations. Furthermore, MIP modeling is an art which takes years to hone (less so today than when I started -- algorithms are getting more and more sophisticated -- but nevertheless, it takes human reasoning and intuition to produce a good formulation). It's always useful have a range of solvers at your disposal and not limit yourself. CP solvers are specialized to CP problems and for simple problems they may work better due to less translation overhead.

skosch 8y ago

MIP solvers work themselves through the search tree using all sorts of clever tricks, constantly running LPs on relaxations (approximations) of the problem to prune the tree. They can be very efficient, but the constraints need to be linear for the LPs to work. CP solvers are less sophisticated in their search (although some are getting more clever [1]), but they instead delegate to graph-theoretical algorithms [2] that can efficiently deal with more high-level constraints, for instance "I only want solutions where all these variables have different values", which in the MIP world would translate to tons of auxiliary linear constraints and variables that would slow down your solver. So it really depends on how you write your model, and it's not even always obvious whether MIP or CP is better – which is why Minizinc is so useful. There are even attempts to automatically choose the algorithm to use based on the problem structure [3]. [1] https://github.com/chuffed/chuffed https://github.com/chuffed/chuffed [2] http://www.emn.fr/x-info/sdemasse/gccat/sec5.html http://www.emn.fr/x-info/sdemasse/gccat/sec5.html [3] https://github.com/CP-Unibo/sunny-cp https://github.com/CP-Unibo/sunny-cp