Decision Optimization

 View Only
Expand all | Collapse all

Is there a way to make the noOverlap() constraint in CP optimiser enforce a maximum distance between interval variables? (instead of / in addition to minimum as it currently does)

  • 1.  Is there a way to make the noOverlap() constraint in CP optimiser enforce a maximum distance between interval variables? (instead of / in addition to minimum as it currently does)

    Posted Tue August 02, 2022 03:58 PM
    Is there a way to make the noOverlap() constraint in CP optimiser enforce a maximum distance between interval variables? (instead of / in addition to minimum as it currently does)?

    I have tried to play with the startOf() and startOfNext() constraints to mimic this behaviour but I still need a way to incorporate something like the transition matrix but for maximum distances as these are also sequence dependent.

    ------------------------------
    Eghonghon Eigbe
    ------------------------------

    #DecisionOptimization


  • 2.  RE: Is there a way to make the noOverlap() constraint in CP optimiser enforce a maximum distance between interval variables? (instead of / in addition to minimum as it currently does)

    Posted Wed August 03, 2022 04:40 AM
    Dear Eghonghon,

    There is unfortunately no support in the noOverlap constaints for max distances.
    You can emulate this behavior by using if_then constraints to specify max delays between successive intervals, as shown in the code below: 

    import itertools
    import numpy as np
    from docplex.cp import model as cp
    from random import randint, seed
    
    jobs = [0, 1, 2, 3]
    seed(1)
    
    model = cp.CpoModel()
    
    # Intervals: the jobs to be executed
    its = [cp.interval_var(length=1, name=f'J{j}') for j in jobs]
    
    # Ensure intervals do not overlap and add setup time between each interval
    distance_matrix = [[sorted([randint(1,5), randint(1, 5)]) for _ in jobs] for _ in jobs]
    min_matrix = np.array([[e[0] for e in row] for row in distance_matrix])
    max_matrix = np.array([[e[1] for e in row] for row in distance_matrix])
    
    # show the distance matrices
    print('min_matrix'); print(min_matrix)
    print('max_matrix'); print(max_matrix)
    
    # create sequence
    seq = cp.sequence_var(vars=its, name='Seq', types=jobs)
    model.add(cp.no_overlap(sequence=seq, distance_matrix=min_matrix))
    
    # set max distances
    for i,j in itertools.product(jobs,jobs):
        model.add(model.if_then(
            model.type_of_next(seq, its[i]) == j,
            (model.start_of(its[j]) - model.end_of(its[i])) <= max_matrix[i][j]))
    
    makespan = model.max([model.end_of(its[i]) for i in jobs])
    model.add(makespan < 20)
    model.add(model.first(seq, its[0]))
    model.add(model.start_of(its[0]) == 0)
    model.add(model.maximize(makespan))
    
    solution = model.solve()
    
    solution.write()
    ​
    I hope this helps.

    ------------------------------
    Renaud Dumeur
    ------------------------------



  • 3.  RE: Is there a way to make the noOverlap() constraint in CP optimiser enforce a maximum distance between interval variables? (instead of / in addition to minimum as it currently does)

    Posted Thu August 04, 2022 07:12 AM

    Thank you. It does help!

    I was hoping for a neater single shot constraint like noOverlap but I'll look into a custom implementation.



    ------------------------------
    Eghonghon Eigbe
    ------------------------------