Use of cumulatives

Question

I'm working on a problem where I use the cumulatives/[2,3] predicate. But I get very bad performance when I try to combine this with minimize in labeling

I have the following demo. 10 task, all with duration 1, 4 machines, all with capacity=1. My goal is to minimize the total time, i.e. minimize(maximum(Es)):

:- use_module(library(clpfd)).
:- use_module(library(lists)).

go( Ss, Es, Ms, Tm, Lab ) :-

    Ss = [S1, S2, S3, S4,S5,S6,S7,S8,S9,S10], %Starttimes
    Es = [E1, E2, E3, E4,E5,E6,E7,E8,E9,E10], %Endtimeds
    Ms = [M1, M2, M3, M4,M5,M6,M7,M8,M9,M10], %MachineIds


    domain(Ss, 1, 20),
    domain(Es, 1, 20),
    domain(Ms, 1, 10),

    %All task has duration = 1
    Tasks = [
        task(  S1, 1,  E1,  1, M1 ), 
        task(  S2, 1,  E2,  1, M2 ), 
        task(  S3, 1,  E3,  1, M3 ), 
        task(  S4, 1,  E4,  1, M4 ), 
        task(  S5, 1,  E5,  1, M5 ), 
        task(  S6, 1,  E6,  1, M6 ), 
        task(  S7, 1,  E7,  1, M7 ), 
        task(  S8, 1,  E8,  1, M8 ), 
        task(  S9, 1,  E9,  1, M9 ), 
        task( S10, 1,  E10, 1, M10 ) 
    ],

    %All machines has resource capacity = 1
    Machines = [
        machine(  1, 1 ),
        machine(  2, 1 ),
        machine(  3, 1 ),
        machine(  4, 1 ) 
    ],

    cumulatives(Tasks, Machines, [bound(upper)] ),

    maximum( MaxEndTime, Es ),

    %Make the list of options to pass to the labeling predicate
    append( [ [minimize(MaxEndTime)], [time_out( Tm, _)], Lab ], LabOpt ),
    %The variables to lable:
    append([Ms, Ss ], Vars),

    labeling( LabOpt, Vars). 

If I now run this and solve for 1 second I get:

| ?- go( S, E, M, 1000, []).
E = [2,3,4,5,6,7,8,9,10,11],
M = [1,1,1,1,1,1,1,1,1,1],
S = [1,2,3,4,5,6,7,8,9,10] ? 

I.e. all tasks has been scheduled to run on machine 1

I need to run the solver for 30 second before I see any sign of minimization:

| ?- go( S, E, M, 30000, []).
E = [2,3,4,5,6,7,8,9,10,2],
M = [1,1,1,1,1,1,1,1,1,2],
S = [1,2,3,4,5,6,7,8,9,1] ? 

If I run for 60 second I start to get acceptable results:

| ?- go( S, E, M, 60000, []).
E = [2,3,4,2,3,4,2,3,4,2],
M = [1,1,1,2,2,2,3,3,3,4],
S = [1,2,3,1,2,3,1,2,3,1] ? 

I feel that this is taking way too long time. Any comments on why it takes so long time?

Mcandrew

Answer 1

By using the task_intervals(true) option on the cumulativespredicate the speed is really improved:

cumulatives(Tasks, Machines, [bound(upper),task_intervals(true)] )

gives solvingtime of 2ms to the code in the original question without changing anyting else.

Mcandrew

Answer 2

I found two standard tricks that speed up your code.

First, variable order. You are labeling all the M variables before the S variables. That takes some 51 seconds. It's much better to fix both S and M for one task at a time. I.e. variable order [S1,M1,S2,M2,S3,M3,S4,M4,S5,M5,S6,M6,S7,M7,S8,M8,S9,M9,S10,M10]. That brings the time down to some 2 seconds.

Second, your tasks are interchangeable, and so are your machines. Perhaps that will not always be the case, if your code was meant to be a toy example and not the real thing. But if you have such symmetries, you can prevent the search going down a lot of culs de sac by breaking the symmetries e.g. by:

lex_chain([[S1,M1],[S2,M2],[S3,M3],[S4,M4],[S5,M5],[S6,M6],[S7,M7],[S8,M8],[S9,M9],[S10,M10]]),

That brings the time down to 10 milliseconds.

Both these tricks are standard in the craft of constraint programming.

Wiliness

You are correct that this is only a toy example, so use of lex_chain in the real problem is not possible in a one to one mapping from your example. I guess that a combination of better variable ordering and use of task_intervals(true) is a good solution. – Mcandrew