2
$\begingroup$

I know that MILP solvers are bad with scheduling problems. However, if we are allowed to keep unscheduled some tasks (i.e a solution with 0 scheduled tasks is a feasible solution but we add the objective (makespan) the maximiation of scheduled tasks), does things become easier?

$\endgroup$
  • 1
    $\begingroup$ If there is no penalty for unscheduled tasks, it is optimal to schedule nothing. $\endgroup$ – RobPratt Sep 28 at 22:43
  • $\begingroup$ One issue with LP is that realworld scheduling problems often have constraints that form loops, regardless of you thinking you know about all constraints. And you don't get to understand the real problems until after your solution is first used by the customer. $\endgroup$ – Ian Ringrose Sep 29 at 9:54
5
$\begingroup$

That's a misconception - MILP solvers can be brilliant with scheduling tasks as long as the modeler knows their stuff, but that's true of all NP-Hard optimisation problems. The snag is that a certain level of custom modelling work is typically needed for real problems, but this is not a solver limitation per se.

If what you have in mind is to make the scheduling of some tasks optional in order to aid the solver, then many solvers support lazy constraints.

This is not trivial to model properly because you still need to ensure that the tasks are scheduled some of the time, but to answer your question directly no, it's not necessarily easier. The only way to check is to try out both formulations and see what works best for a particular problem.

In global optimisation (including MILP), constraints are our friends because they help us reduce the solution space. However, the problem is NP-Hard because (or the other way around depending on your preference) there is no one-size-fits-all way to change the problem to make it easier. For some problems constraining the system more tightly helps a lot, for others it makes things much worse.

From experience, what does work much better than MILP if you need to have fuzzy scheduling is to formulate an MINLP.

| improve this answer | |
$\endgroup$
  • $\begingroup$ In the real world scheduling problems, on the one hand, the MILP formulation should be really straightforward to solve in the reasonable amount of time and in the other hand, many planners will need to achieve a good solution as soon as possible. Also, lots of industrial folks do not strong background in OR to employ advanced techniques such as decomposition. Therefor using other useful methods like CP or heuristic would be helpful. $\endgroup$ – A.Omidi Sep 29 at 9:51
  • $\begingroup$ @A.Omidi what kind of decomposition can be used to solve complex scheduling problem (more complex thant rcpsp)? $\endgroup$ – Best_fit Sep 29 at 10:44
  • $\begingroup$ @Best-fit, if you are interested to know about the decomposition methods, you shall try googling and read related articles in both sides (industry or academy) but, in the simple words, column generation variants and benders decomposition may be more interested but they need special skills in OR and programming. $\endgroup$ – A.Omidi Sep 29 at 13:40
  • $\begingroup$ @A.Omidi As far as I know, those methods gives bounds and not feasible solutions (this is what I learn in my university!). So what am I missing ? $\endgroup$ – Best_fit Sep 29 at 14:23
  • $\begingroup$ @Best_fit Bounds can be produced as part of running the algorithms, but the end result is a feasible solution. $\endgroup$ – Nikos Kazazakis Sep 29 at 14:59
4
$\begingroup$

What follows is conjecture.

If you have a tightly constrained model, for which the solver struggles to find a feasible (or good feasible) schedule, then I suspect that allowing tasks to be skipped (at a penalty) may facilitate getting a feasible solution. Whether it will get you to an optimal solution sooner is anybody's guess.

If the MIP solver finds feasible schedules in reasonable time but struggles either finding an optimal schedule or proving optimality, I suspect that allowing tasks to be skipped will make things worse. It will expand the feasible region (so the search tree probably gets bigger), and I think it likely will loosen the LP relaxation bounds.

Overall, I doubt I would try it. If the issue is difficulty getting good schedules early (or any feasible schedule), I would try either scheduling heuristics or a constraint solver (specifically one that has global constraints tailored to scheduling problems). With heuristics, I would try to get a good schedule and then use it as a hot start for the MIP solver. With a constraint solver, I would first try to let the solver progress to optimality, and only use its solution to hot start the MIP solver if the constraint solver looked like it was going to struggle to reach optimality itself.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Any suggestion for solvers that have global constraints tailored to scheduling? I know about IBM CP Optimizer, any other suggestions? $\endgroup$ – Best_fit Sep 29 at 22:23
  • $\begingroup$ Disclaimer: I'm an integer programmer, and my knowledge of CP is rather modest. My first choice would be CP Optimizer. I have played a bit with MiniZinc, which is an open-source modeling language (the IBM analog would be OPL). MiniZinc includes some constraints, such as "no overlap", that would be useful for scheduling. The key would be using a solver that supports those constraints (and maybe adds one or two of its own). I don't know all the solvers that can be used with MiniZinc, but it does support at least a few, including some open-source ones. $\endgroup$ – prubin Sep 30 at 17:47
  • $\begingroup$ So, if I have a model with a lot of constraints (an extension to RCPSP but with more constraints. For the problem I am treating finding a feasible solution is NP-hard). Could getting a feasbile solution be very hard for a integer programming solver ? Could an IP solver be more powerful than a home-made heuristic or a CP solver to find a feasible solution? $\endgroup$ – Best_fit Oct 2 at 13:14
  • $\begingroup$ In a lot of papers that have problems with the same complexity (i.e finding a feasible solution is so hard) they use this complexity to justify using a heuristic approach rather than an IP solver (to find a feasible solution). Why just not using such a solver? What kind of heuristics used by an IP to find a first feasible solution. Are they "weak"? $\endgroup$ – Best_fit Oct 2 at 13:14
  • 1
    $\begingroup$ On any given instance, an IP solver might or might not struggle to find a good feasible solution, a heuristic might or might not be faster, and CP solver might or might not be better than an IP solver. The answer to all your questions is "maybe". The only way to tell is by experimentation. As far as complexity, it is fairly common for people with a predisposition toward using heuristics to shout "NP-hard" a few times and then skip trying to find an exact solution. "NP-hard" is an indicator of potential difficulty, but mostly it's an asymptotic result. Personally, I just tune it out. $\endgroup$ – prubin Oct 3 at 17:54

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.