Originally posted by: Oskar Wigstrom

Hi,
 

I'm working on a project where a scheduling problem is combined with a special cost function. That is, the cost is a function of the precedences of the scheduling problem.

For example, if we have three tasks [A,B,C], which are all to be executed, then what I will call precedence indicators will in this case be are denoted [ab, ac, bc]. Each "precedence indicator" is a boolean variables expressing which task occurs first. In any case, the cost is expressed on the form: c = f(ab,ac,bc). For a partial solution, I can also get a lower bound on the cost, c >= f(ab,bc) for example.

I have a couple of questions related to my project, I plan on implementing the cost as a user defined constraint, but I'm not sure which way to go about this.

1. I could express an implication between booleans and precedences such as: (i) boolean <=> EndBeforeStart(a,b); (ii) not(boolean) <=> EndBeforeStart(b,a).
I could then have my user defined constraint subscribe to any changes in the boolean variables. However, I can't seem to get the implication expressions right in Ilog, any suggestions (using the C++ API)? How should I go about this?

2. Should I rather be using an IloSequenceVariable? Can I subscribe to an IloSequenceVariable instead? What will it look like at a partial solution?

3. Concerning branching, since the cost is only related to the precedences of operations, is it possible define the booleans in (1) as branching variables? If option (2) is preferable, can the search be directed as I'm suggesting?

Sorry if there's anything unclear, I appreciate any help I can get!

Best regards,
Oskar Wigström

Originally posted by: Oskar Wigstrom

Update:

I found that I could do:

IloBoolVar ab = IloBoolVar(env);
IloIntervalVar A = IloIntervalVar(A);
IloIntervalVar B = IloIntervalVar(B);

model.add((ab == 0 && IloEndOf(A)<=IloStartOf(B) )||(ab == 1 && IloEndOf(B)<=IloStartOf(A) ));

I can seem to manage to do it with EndBeforeStart(), is there a difference? How would I go about making Ilog CP branch on the boolean variables?

If i have a user defined constraint which expresses the cost as a function of boolean variables, will the CP optimizer understand that it is the boolean combinations it must search?

Originally posted by: PhilippeLaborie

Yes, what you propose here is also possible. However, constraints IloEndOf(A)<=IloStartOf(B) maybe slightly less efficient than endBeforeStart(A,B) in the engine.

Concerning the decisions on the boolean ab, if you define them as boolean variables, you can add a search phase that first fix those boolean variables in the search. See the concept of search phase in CP Optimizer.

Philippe

Originally posted by: PhilippeLaborie

Hello,
Is the problem you described a generalization of your actual problem or is it your actual problem?
If your actual problem is more specific, could you give more details, for instance:
- can your tasks (a,b,c) overlap? if there is no possible overlap between tasks, when you mean a precedence ab, does it really means that a is before b in the sequence or that a the task immediately before b ?
- do you need to consider all n^2 pairs of intervals in the function or is it expressed only over a subset of pairs?
- which type of functions f are you considering? It seems to be an increasing one that is if X in Y then f(X)<=f(Y)
- assuming you have boolean expressions/variables for ab, can function f be expressed algebraically in the model or is it really necessary that you implement this cost expression as a user-defined constraint?

Special characteristics of your problem can of course be exploited to implement a stronger model.

Also, if you really need to implement the aggregation function f as a user-defined constraint, then you may consider also handling yourself the link between boolean expressions ab and its effect on the start/end values of a/b in the engine.

I'm now assuming you really need to explicitly represent the boolean variables ab in the model and that the tasks do not overlap. It is indeed not possible to use endBeforeStart(a,b) in a composite constraint. You have two options for modelling that:

1) Assuming M is a big enough integer, you could post:
endBeforeStart(a,b,-M(1-ab)) && endBeforeStart(b,a,-Mab)
That way, if ab=1 you get endBeforeStart(a,b) && endBeforeStart(b,a,-M)
if ab=1 you get endBeforeStart(a,b,-M) && endBeforeStart(b,a)
As M is big enough, constraints involving -M as minimal delay are always true.

2) For a pair (a,b), you can create optional intervals representing the fact (1) a is before b or (2) b is before a:
  dvar interval a ...;
  dvar interval b ...;
  dvar interval optional a1 ...;
  dvar interval optional a2 ...;
  dvar interval optional b1 ...;
  dvar interval optional b2 ...;
  dexpr int ab = presenceOf(a1);
 
constraints:
  alternative(a, [a1,a2]);
  alternative(b, [b1,b2]);
  endBeforeStart(a1,b1);
  endBeforeStart(b2,a2);
  presenceOf(a1)==presenceOf(b1);
  presenceOf(a2)==presenceOf(b2);

This can be a bit heavy but will result in stronger propagation in the engine than the first approach.

Hope it helps,

Philippe
 

Originally posted by: Oskar Wigstrom

Thank you Philippe for your quick and detailed reply, I very much appreciate it!

First off, using the user defined constraint for handling the link between the booleans values and its effect on the start/end times of the model sounds like a good idea.

I realize I wasn't very clear in my problem description. I'm actually posing a NoOverlap constraint on the tasks and then the booleans are merly there to guide the search. The booleans are not strictly necessary, I simply want the solver to branch on the order of intervals subject to NoOverlap.

A couple of thoughts:

- Now that I think about it, is it possible for propagators to post/add additional constraints to the current branch being explored? That is, can a user defined propagation method which detects a change in the boolean variables post (or convert itself to) an EndBeforeStart constraint?

- Or alternatively (I think this might even be preferable), is it possible to create a 'search engine'/brancher which branches on the order of certain interval pairs? That is, the brancher itself adds EndBeforeStart constraints.

The problem described is indeed a generalization. I realize that I could have described the problem much better,  I'll try to give more detail:

My project aims to solve scheduling problems with nonlinear costs (and possibly including dynamics), for example the energy use in a machine could be modeled as a function of the execution time of each operation.

Previously, I've modeled this problem using MINLP methods; scheduling constraints are mixed integer linear and the objective nonlinear. But there are several drawbacks with MINLP, amongst other things the scheduling relaxations are so weak that infeasabilities are detected much too deep in the branches.

What I want to do is to instead use Ilog CP to model the scheduling problem. Have the Ilog create a branch and bound tree on the discrete decisions. And for the partial/fully assigned discrete decisions, create an NLP to find a lower/upper bound on the cost.

In the case of a job shop style problem: (i) I would fix the order of tasks within a job, (ii) post NoOverlap on the tasks for each machine, (iii) have Ilog branch on the discrete decisions; (iv) solve NLPs for the partial and fully assigned booleans.

To answer your questions (some of which may already be clear from the text above):

- While there may exist tasks that overlap, the pairs of tasks associated with booleans should do not.

- Only a subset of all intervals/tasks are considered, those allready subject to a NoOverlap constraint.

- You are correct in assuming the cost is an increasing one, as discrete decisions/booleans are fixed, the problem is further restricted and the cost becomes higher.

- While everything in the function may be expressed algebraically, I don't think propagation will be nearly strong enough, also floating point variable precision is required for the formulation.

I'll check out your suggestions and also read up on search phases!

Thanks again for your help,
Oskar

Originally posted by: PhilippeLaborie

Your problem is very interesting. If you can model your (nonlinear) objective function directly in CP Optimizer, it would be interesting to see how the automatic search of CP Optimizer behaves. Because part of the automatic search does something that resembles a lot the type of search you describe that is (1) producing a "solution" that consists of a set of precedence constraints on each resource and (2) find the exact start/end positioning of tasks with respect to the objective function by using Math Programming techniques. You can find more on the automatic search of CP Optimizer in [1,2]. The CP Optimizer language is very rich for expressing your objective function as a function of the start time of the tasks, as you can combine min/max/+/*/log/exp etc. as well as any piecewise linear function. So that's clearly what I would try first.

Otherwise, indeed, you can define your own search and you can post precedence constraints as decisions in the search tree. The API for adding new precedence constraints between interval variables of a sequence variable in a search goal is:

void IlcIntervalSequenceVar::setBefore(const IlcIntervalVar before, const IlcIntervalVar after) const
 

You can find more information on the topic in this par of the CP Optimizer reference manual:

CP Optimizer > CP Optimizer C++ API Reference Manual > Concepts > Search API for scheduling in CP Optimizer

[1] P. Laborie, D. Godard. Self-Adapting Large Neighborhood Search: Application to single-mode scheduling problems. Proceedings of 3rd Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2007).

[2] P. Laborie, J. Rogerie. Temporal Linear Relaxation in IBM ILOG CP Optimizer. Proceedings of 6th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2013).
 

Philippe

Originally posted by: Oskar Wigstrom

I did at one point try piecewise linear functions to approximate the cost, but for some reason, propagation was pretty bad. Maybe I did something wrong, if I get the time, I'll give it another shot.
However, the next step in the project (after just a nonlinear cost) would be to add the system dynamics, and then I'll need floating point precision for sure.

I'm going to check out search papers, I'm very happy to learn more about how CP Optimizer actually does its search. Then I'll see what I can do in terms of implementation. 

Thanks again Philippe!

Oskar

Originally posted by: Oskar Wigstrom

Seems as if the proceedings in which [2] is included havn't been published yet. Any chance you could send me a copy? (oskar.wigstrom "at" chalmers.se)