4 ms·

Recently I've been playing around with MILP solvers and this sounds similar. Can anyone with some experience in these kinds of optimization problems give a summ

Recently I've been playing around with MILP solvers and this sounds similar. Can anyone with some experience in these kinds of optimization problems give a summary of the similarities and differences between CP and MILP?

niemandhier 4y ago
CP is different in that it is less a sigle method than a framework for individual CS insights into enforcing constraints. This is usually down by a global constraint store and a watchlist of variable for the problem under consideration. A good example is the famous “ All different” constraint. In MIP you would implement that as a fancy summ, in CP one can use a corollary from Berge’s lemma to get a specialised constraint to just enforce that. Rule of Thump is that CP excels when the problem is thigh lay constraint and one has many global constraints ( those that apply to all variables). Another point is that contrary to MIP programs that often are modelled directly using sums and inequalities, CP Programms usually are written in a declarative language such as ZINC, which in my opinion makes it easier to get into the subject. If you are interested: This series of blog posts builds a CP solver in Julia https://opensourc.es/blog/constraint-solver-1/ https://opensourc.es/blog/constraint-solver-1/ ortoools by Google also contains a CP solver and the doc is quite interesting https://developers.google.com/optimization/cp https://developers.google.com/optimization/cp Finally there is the dissertation of Guido Tack, who developed a oss Cp solver as his PhD project ( I think that is the internal solver used by SAP software now) https://www.gecode.org/papers/Tack_PhD_2009.pdf https://www.gecode.org/papers/Tack_PhD_2009.pdf
- niemandhier 4y ago
  I think the wonderful people of the association for constraint programming deserv a mention here, for those interested check out the cap summer schools 2023 https://school.a4cp.org/summer2023/ https://school.a4cp.org/summer2023/
vpastore 4y ago
In milps you can have an objective function to minimize/maximize and continuous variables. The techniques used are based on the characteristics of the mathematical space of the possible solution and methods to reduce the size of space that you have to look into. The solution of milp solver are provably optimal. CP allows for constrains that are difficult to model and/or solve in milps (or even mip). There is some overlap between the two. For example, presolving in milp is basically a generalization of constraint programming.
- habitue 4y ago
  Thanks, that's helpful

niemandhier 4y ago

CP is different in that it is less a sigle method than a framework for individual CS insights into enforcing constraints. This is usually down by a global constraint store and a watchlist of variable for the problem under consideration. A good example is the famous “ All different” constraint. In MIP you would implement that as a fancy summ, in CP one can use a corollary from Berge’s lemma to get a specialised constraint to just enforce that. Rule of Thump is that CP excels when the problem is thigh lay constraint and one has many global constraints ( those that apply to all variables). Another point is that contrary to MIP programs that often are modelled directly using sums and inequalities, CP Programms usually are written in a declarative language such as ZINC, which in my opinion makes it easier to get into the subject. If you are interested: This series of blog posts builds a CP solver in Julia https://opensourc.es/blog/constraint-solver-1/ https://opensourc.es/blog/constraint-solver-1/ ortoools by Google also contains a CP solver and the doc is quite interesting https://developers.google.com/optimization/cp https://developers.google.com/optimization/cp Finally there is the dissertation of Guido Tack, who developed a oss Cp solver as his PhD project ( I think that is the internal solver used by SAP software now) https://www.gecode.org/papers/Tack_PhD_2009.pdf https://www.gecode.org/papers/Tack_PhD_2009.pdf

niemandhier 4y ago
I think the wonderful people of the association for constraint programming deserv a mention here, for those interested check out the cap summer schools 2023 https://school.a4cp.org/summer2023/ https://school.a4cp.org/summer2023/

vpastore 4y ago

In milps you can have an objective function to minimize/maximize and continuous variables. The techniques used are based on the characteristics of the mathematical space of the possible solution and methods to reduce the size of space that you have to look into. The solution of milp solver are provably optimal. CP allows for constrains that are difficult to model and/or solve in milps (or even mip). There is some overlap between the two. For example, presolving in milp is basically a generalization of constraint programming.

habitue 4y ago
Thanks, that's helpful