Decision Optimization

Expand all | Collapse all

Overlap constraint for interval variables

Jump to Best Answer
  • 1.  Overlap constraint for interval variables

    Posted 9 days ago
    Hello everyone,

    I have a scheduling problem with the following characteristics:
    - MM tasks must be scheduled;
    - each task lasts a time interval, and it consumes one resource unit during its operation (regardless of the length of its time interval);
    - at each instant of time one task is completed;
    - the objective function is to minimize the maximum amount of resource used.
    - there are some subsets of tasks that need to be performed simultaneously in at least one unit of time.

    I modeled this problem as follows:


    I have a few subsets of tasks, where all the tasks contained in a subset must overlap in time for at least one unit of time. Thus, I would like something like an "Overlap Constraint". Alternatively, in the code above I used a precedence constraint for any pair (i, j) of tasks contained in each of these subsets generating a much larger number of constraints. Is there such a thing as a "Overlap Constraint" for interval variables?

    Best regards, 
    M.



    ------------------------------
    Martin
    ------------------------------


  • 2.  RE: Overlap constraint for interval variables

    Posted 8 days ago
    Hi,

    have you tried overlapLength ?

    https://www.ibm.com/support/knowledgecenter/SSSA5P_12.10.0/ilog.odms.cpo.help/CP_Optimizer/reffileformatcpo/functions/overlapLength.html

    regards

    ------------------------------
    ALEX FLEISCHER
    ------------------------------



  • 3.  RE: Overlap constraint for interval variables
    Best Answer

    Posted 8 days ago
    Hello,
    another possibility I see is to model the time where all the intervals should overlap as an additional interval variable of length 1. Lets name this interval o. Then for every task i in the set you can constraint o to be inside i by:

    startBeforeStart(i, o);
    endBeforeEnd(o, i);

    Best regards, Petr

    ------------------------------
    Petr Vilím
    IBM
    ------------------------------



  • 4.  RE: Overlap constraint for interval variables

    Posted 8 days ago
    I think it is not really possible to do better than the model you implemented with precedence constraints. I do not see how to get rid of posting one (or two) constraint each pair of interval that corresponds to an arc (i,j) in your graph, and precedence constraints are "light" constraints in the engine. Of course, performance will depend on the number of arcs in your graph. What is the typical size of the problem? Also, if the graph has a particular topology, maybe there could be a better model, but I'm really not sure.

    ------------------------------
    Philippe Laborie
    ------------------------------



  • 5.  RE: Overlap constraint for interval variables

    Posted 7 days ago
    Hello,

    Thank you all for the suggestions.
    I didn't try overlapLength because I don't know beforehand the length of the overlap of the interval variables. Furthermore, this approach seems to me similar to my use of precedence constraints, i.e., to constrain two interval variables at a time (instead of an array of interval variables).
    Petr Vilím's suggestion seemed promising. Thank you!
    I consider instances of 50 to 200 tasks. I get good solutions, but usually without a certificate of optimality. For dense graphs, my model would lead to many constraints due to the arcs (i, j), so I want a more compact modeling approach. I am unaware of particular properties in this graph.

    Best regards,
    Martin.

    ------------------------------
    Martin
    ------------------------------



  • 6.  RE: Overlap constraint for interval variables

    Posted 7 days ago
    Petr's suggestion allows compacting the formulation of the constraint in case your graph is a clique (as you move from O(n^2) constraints to O(n) ones). But if the graph has no particular property, and if you model each arc (i,j) by introducing a new interval 'o' of length 1, it will not simplify the problem.

    So maybe a good way to proceed would be to decompose the graph into a set of cliques, for each clique of size >2 in the decomposition, you can can use Petr's idea and introduce an interval 'o' for each clique, and for the isolated arcs (clique of size 2), just use two precedences. For dense graphs, this could really help compacting the formulation because there are chances that you will find large cliques in the decomposition.

    ------------------------------
    Philippe Laborie
    ------------------------------



  • 7.  RE: Overlap constraint for interval variables

    Posted 7 days ago
    Hello,

    In fact, this graph can be represented by a set of cliques. The subsets of tasks that I mentioned in the first message are these clicks. By particular property of this graph, I meant that I don't know if this graph is a perfect graph, chordal graph, interval graph, etc.

    Thanks!

    Best regards,

    ------------------------------
    Martin
    ------------------------------



  • 8.  RE: Overlap constraint for interval variables

    Posted 7 days ago
    So if you already know the clique decomposition, indeed it is a good new and you should use Petr's suggestion.

    I noticed something else looking at the model: 
    - Maybe it could help the search to use additional intervals of length 1 at the end of the tasks and instead of the AllDifferent constraint, use a NoOverlap constraints on these interval variables. The reason it could help is that the automatic search would directly 'see' this constraint on interval variables and could exploit it.
    - Also, given that the problem seems symmetrical on the time axis (I think you mention it in another thread), maybe you could post this noOverlap constraint on the start time of the tasks. The reason is that the search is essentially a chronological search so it is probably better to consider this noOverlap on the start time instead of the end time (when posted on the end time, the constraint will not propagate much given that the duration of tasks is unknown)

    ------------------------------
    Philippe Laborie
    ------------------------------