3
$\begingroup$

My understanding is Constraint programming (CP) is a sub-set of MILP but in MILP we not only try to find a feasible solution (like CP) but also we should optimize an objective function. I do have a large-scale Job Shop Scheduling problem (40k binary variables) and I need to find a fast and efficient way of finding a feasible solution (preferably without any commercial solver). I am familiar with GAMS and Pyomo (and they both use solvers).

Any advice on the available resources for solving CP or MILP models?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ "My understanding is Constraint programming (CP) is a sub-set of MILP but in MILP we not only try to find a feasible solution (like CP) but also we should optimize an objective function." No, CP and MILP are two paradigms to model optimization problems. It's possible to feed a CP solver with a MILP model, but it's very likely not going to work better. The model needs to be rewritten using CP specific constraints (all-different, cumulative, circuit...). $\endgroup$
    – fontanf
    Jul 14, 2022 at 14:53
  • $\begingroup$ @Optimization team, job shop scheduling problem naturally is NP-hard and it needs lots of efforts to develop a mathematical formulation to solve large instances. If you are facing with a large scale model, you might want to combine MILP and CP to work together hopefully to find a good feasible solution. Also, be aware that there are some heuristics to tackle such a problem to achieve very good feasible solution even for the large scale models. $\endgroup$
    – A.Omidi
    Jul 15, 2022 at 11:34

2 Answers 2

Reset to default
10
$\begingroup$

CP is not a subset of MILP. They are separate modeling/solving paradigms whose domains of application overlap. Both can solve for optimal solutions (in CP's case, by incorporating a constraint that says each solution must improve on the previous one) or stop with a feasible solution.

It's a bit deceptive to refer to "CP" as a single approach, the way MILP is. All MILP languages and solvers understand linear equality and inequality constraints and real, integer and binary variables. Some extend to SOS1 and SOS2 constraints, if-then constraints and quadratic cone constraints, but that's about it. CP languages and solvers vary more in terms of what constructs they understand. They all support integer and binary/logical variables, but some provide things like interval variables (typically representing a time interval) and others, I think, do not. They probably all have the "all different" constraint, but some support constraint types that others do not.

Some CP languages and solvers are specifically geared to scheduling problems. They allow the problem to be expressed more directly than a MILP model would. For instance, some have a constraint with a name something like "EndBeforeBegin" which is used to enforce a precedent constraint (one job must end before the next begins).

Whether you can solve a scheduling problem faster with CP or MILP is an empirical question, the answer to which depends on the specific elements of your problem, the specific CP and MILP solvers you use (and the model elements supported by whatever language or API you use), and of course your modeling skills.

Improve this answer
$\endgroup$
3
$\begingroup$

Google has a very nice library called OR Tools. One of those tools is a CP-SAT solver. Even though their solver works only on integer valued variables it is not that hard to convert MILP models to integer problems.

They also have some nice documentation about CP-SAT, constraint optimization and relevant topics.

Improve this answer
$\endgroup$

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.