7
$\begingroup$

Optional interval is a great idea of optional interval/task that can be active or inactive based on boolean variable. I found it very useful in complex scheduling problems.

It was introduced in IBM Cp Optimizer more than ten years ago. Unfortunatelly except constraint solver (not developed anymore) and cp-sat solver in or-tools optional interval is not supported by any other solver.

Is there a reason why optional interval is not supported by other solvers (effort?) or exists alternative to optional intervals in other constraint solvers ?

Optional interval is defined by four variables: start, duration, end and active variable (boolean variable). In case active=true, start + duration = end should be satisfied and all constraints that work with the interval (like cumulative constraints) should respect it.

I use optional intervals primarily to express alternatives. In case I need to choose between two or more workers for an operation, the sum of active variables equal to one guarantees that only one worker is used. Without optional intervals, I need to choose a worker for an operation too early and all other alternatives are lost during search phase until backtrack.

Cumulative constraint to guarantee that a worker is not used more than once at same time doesn't work very well when assignments of a worker are unknown. Most time there's nothing to propagate since solver waits for mostly random assignments. My experience with a solver without optional intervals.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ It's for sure harder to implement. But i wonder what other solvers you are talking about? ILOG CP feels like the only commercial representative (and is it really not developed anymore?) and has it. or-tools too as modern LCG/Hybrid and then there is gecode, the open-source classic CP representative also supporting it. Is there something in CP which isn't somewhat dominated by these three candidates? (a personal similar example to yours is the following: or-tools has self-loops @ circuit-constraint which has lots of potential without CP Opt or gecode matching it: in this regard i feel the pain) $\endgroup$
    – sascha
    Jan 11, 2022 at 22:25
  • $\begingroup$ No more developed is constraint solver from or-tools, ILOG CP is a black box and cp-sat solver from or-tools is not constraint solver - for more complex problems I miss custom propagators, much more memory can be used with channeling constraints compared constraint solver. I didn’t know about gecode, it should be a way to go to implement branching strategy that benefits from optional intervals. $\endgroup$
    – gregy4
    Jan 12, 2022 at 7:33
  • $\begingroup$ Could you give a good example of an optional interval? Maybe with a use case? It sounds like something we support in OptaPlanner (through shadow vars or CS) but I need to understand it better - and create an RFE if we don't. $\endgroup$
    – Geoffrey De Smet
    Jan 12, 2022 at 8:17
  • 1
    $\begingroup$ I extended original question, authors of ILOG CP like Philippe Laborie published a lot about optional intervals. cp2019.a4cp.org/PDFs/P-Laborie.pdf $\endgroup$
    – gregy4
    Jan 12, 2022 at 9:10
  • $\begingroup$ Thank you Greg! $\endgroup$
    – Geoffrey De Smet
    Jan 12, 2022 at 10:22

2 Answers 2

Reset to default
4
$\begingroup$

As you say, the specific modelling primitives you mention that CP Optimizer introduced are not very common in other solvers. A big reason for this is that the backing infrastructure that makes it work well seems to be quite a lot of implementation-work even just as a starting step. I'm thinking about the logical precedence networks and timlines (see https://icaps17.icaps-conference.org/tutorials/T3-Introduction-to-CP-Optimizer-for-Scheduling.pdf starting at slide 220). Apart from implementing the networks, all the propagators need to use them also which is a lot of work.

In addition, it is not known how well those would work in another solver without all the other innovations in CP Optimizer, such as their automatic, parallel, randomized, deterministic search.

As a Gecode developer, I would love to have the time to implement something similar since it seems so useful. Unfortunately, that is very unlikely to happen. What we do have are classical CP constraints such as cumulative that can operate on optional variable (for examples, see constraints https://www.gecode.org/doc-latest/reference/group__TaskModelIntScheduling.html).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think a way to go is to try it preferably with real optimization problems. Originally I tried to solve my scheduling problem with classical constraint solver (choco solver). To improve performance I was forced to develop custom propagators and still result was not perfect. Approach with CP Optimizer and optional intervals seems to me like reusable alternative to my custom propagators. In case I can affect searching strategy, gecode could be even better than CP Optimizer for my problem. Hopefully I'll have time to implemented it in gecode. I can inform you in case you are interested. $\endgroup$
    – gregy4
    Feb 23, 2022 at 10:12
  • $\begingroup$ Hope you find a good solution to your problem, and I would love to see how well it works if you attempt to solve it in Gecode. As always, the best solution and solver to use will vary with the problem. For scheduling, CP Optimizer and Google OR-tools are typically also something that is a good idea to try if possible. $\endgroup$
    – Zayenz
    Feb 24, 2022 at 14:24
  • 1
    $\begingroup$ Implementation in cp-sat solver from or-tools already done :-) Unfortunately I don’t have access to CP Optimizer. I think comparison between cp-sat and gecode implementation could be very interesting. $\endgroup$
    – gregy4
    Feb 24, 2022 at 22:01
5
$\begingroup$

I'm afraid that the answer is simply that not enough people use/request that feature from solver developers. The same is true in our company's case as well - in the 4 years since I started Octeract, no client has ever requested this feature.

The secondary answer is that the feature is fairly meaningless unless the popular modelling frameworks support it as well, otherwise we can't get that information into the solver, and unfortunately many of them don't (probably for the same reason as above). In IBM's case it probably made more sense at the time since they also provided a modelling platform.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Well it is hard to realize it, since only performance is affected in some cases :-) In my case random worker assignments for some data caused a lot of backtracking and bad results (minimalization of makespan) in constraint solver. By the way I tried octeract solver to solve worker assignment only with given positions of operations (defined as mip problem) and the problem was too hard for your solver. Probably due to number of variables, although cp-sat solver from or-tools and gurobi solver found good results in seconds. $\endgroup$
    – gregy4
    Jan 12, 2022 at 16:06
  • $\begingroup$ @gregy4 That's good to know! If your problem is MIP then we just preprocess it and send it to CBC, so GUROBI etc will always be better. If you have a nonlinear formulation then feel free to send your model to our support, we'd love to have a look :) $\endgroup$
    – Nikos Kazazakis
    Jan 12, 2022 at 16:49

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.