Constraint Programming vs Linear Programming: Speed and quality of solution

user_11678191 0
Viewed 836

I have been studying about optimization algorithms and I came across some questions that I couldn't found answer.

a) Is CP faster than LP? And how is it compared to MILP?
b) CP and MILP would provide the same objective function value?
c) When should I use CP instead MILP? (if I have a mixed-integer linear problem)

Thank you.

mixed-integer-programming linear-programming constraint-programming optimization
1 Answers

Having worked with both CP and LP/MILP, maybe I can offer some insights on your queries. The only thing CP and LP have in common is the word "Programming".

  • The type of variables is different (CP=discrete integer values/LP=continous values/MILP=some are discrete and other variables are continous).
  • The type of constraintes handled is different (CP involve non-linear, LP are of course linear in the variables used).

a) Is CP faster than LP ? in most cases I would consider that CP is slower, because there is no explicit algorithm in CP. It relies on search. However, CP models tend to need lesser variables. With only linear constraints, more variables are needed to model (e.g. using large M equations).

b) CP and MILP give the same objective function value - if the constraints are all linear, and all the variables are integer, then it would not be interesting to use CP to solve the problem because it would be less performant.

c) We should use CP when the problem constraints are well expressed in CP equations, and/or poorly expressed in linear (big M) equations where convergence towards optimum is bad or slow.

Check this question. Some research work to integrate both approaches result in open source software like CLP(r).

user_13104170
Related