Automatically finding lower bound on constraints with clpz and/or simplex?

[jjtolton]

Related to #2519:

The following code finds a final time and assign a schedule based on constraints:

schedule(FinTime, Schedule) :- 
        tasks(TasksDurs),
        precedence_constr(TasksDurs, Schedule, FinTime),
        assign_processors(Schedule, FinTime),
        maplist(start, Schedule, Starts),
        labeling([], Starts).

?- FinTime #=< 22, schedule(FinTime, Schedule).
%@    FinTime = 22, Schedule = [t1/1/2/4,t2/1/0/2,t3/2/0/2,t4/1/2/20,t5/2/2/20,t6/3/11/11,t7/3/0/11]
%@ ;  FinTime = 22, Schedule = [t1/1/3/4,t2/1/0/2,t3/2/0/2,t4/1/2/20,t5/2/2/20,t6/3/11/11,t7/3/0/11]
%@ ;  FinTime = 22, Schedule = [t1/1/4/4,t2/1/0/2,t3/2/0/2,t4/1/2/20,t5/2/2/20,t6/3/11/11,t7/3/0/11]
%@ ;  FinTime = 22, Schedule = [t1/1/5/4,t2/1/0/2,t3/2/0/2,t4/1/2/20,t5/2/2/20,t6/3/11/11,t7/3/0/11]
%@ ;  ... .

?- FinTime #=< 21, schedule(FinTime, Schedule).
%@    false.

I think it would be useful to automatically find the lower bound without having to manually try each version.

I feel like there's probably a better way to find the lower bound given a domain than by trial and error, something like:

?- FinTime in 20..30, schedule(FinTime, Schedule), labeling([min], [FinTime]).
%@    FinTime = 30, Schedule = [t1/1/0/4,t2/1/4/2,t3/1/6/2,t4/1/8/20,t5/2/8/20,t6/3/8/11,t7/3/19/11]
%@ ;  FinTime = 30, Schedule = [t1/1/0/4,t2/1/4/2,t3/1/6/2,t4/1/8/20,t5/2/9/20,t6/3/8/11,t7/3/19/11]
%@ ;  FinTime = 30, Schedule = [t1/1/0/4,t2/1/4/2,t3/1/6/2,t4/1/8/20,t5/2/10/20,t6/3/8/11,t7/3/19/11]
%@ ;  FinTime = 30, Schedule = [t1/1/0/4,t2/1/4/2,t3/1/6/2,t4/1/9/20,t5/2/8/20,t6/3/8/11,t7/3/19/11]
%@ ;  ... .

And it would probably be faster if I dropped the labeling constraints in schedule/2, i.e.

schedule(FinTime, Schedule) :- 
        tasks(TasksDurs),
        precedence_constr(TasksDurs, Schedule, FinTime),
        assign_processors(Schedule, FinTime).

I saw the minimize/3 function in the simplex library, would that be the right way to go?

[UWN]

What is the answer without labeling?

[jjtolton]

What is the answer without labeling?

schedule(FinTime, Schedule) :- 
        tasks(TasksDurs),
        precedence_constr(TasksDurs, Schedule, FinTime),
        assign_processors(Schedule, FinTime).


?- schedule(FinTime, Schedule).
%@    Schedule = [t1/1/_G/4,t2/1/_F/2,t3/1/_E/2,t4/1/_D/20,t5/1/_C/20,t6/1/_B/11,t7/1/_A/11], clpz:(FinTime in 70..sup), clpz:(_A#=<FinTime+ -11), clpz:(_B#=<FinTime+ -11), clpz:(_C#=<FinTime+ -20), clpz:(_D#=<FinTime+ -20), clpz:(_E#=<FinTime+ -2), clpz:(_F#=<FinTime+ -2), clpz:(_G#=<FinTime+ -4), clpz:(_A in 59..sup), clpz:(_G#=<_A+ -4), clpz:(_F#=<_A+ -2), clpz:(_D#=<_A+ -20), clpz:(_C#=<_A+ -20), clpz:(_B#=<_A+ -11), clpz:(_E#=<_A+ -2), clpz:(_G in 0..sup), clpz:(_G#=<_B+ -4), clpz:(_G#=<_E+ -4), clpz:(_G#=<_F+ -4), clpz:(_G#=<_C+ -4), clpz:(_G#=<_D+ -4), clpz:(_B in 48..sup), clpz:(_D#=<_B+ -20), clpz:(_C#=<_B+ -20), clpz:(_F#=<_B+ -2), clpz:(_E#=<_B+ -2), clpz:(_D in 8..sup), clpz:(_E#=<_D+ -2), clpz:(_D#=<_C+ -20), clpz:(_F#=<_D+ -2), clpz:(_E in 6..sup), clpz:(_F#=<_E+ -2), clpz:(_E#=<_C+ -2), clpz:(_F in 4..sup), clpz:(_F#=<_C+ -2), clpz:(_C in 28..sup)
%@ ;  Schedule = [t1/1/_G/4,t2/1/_F/2,t3/1/_E/2,t4/1/_D/20,t5/1/_C/20,t6/1/_B/11,t7/1/_A/11], clpz:(FinTime in 105..sup), clpz:(_A#=<FinTime+ -11), clpz:(_B#=<FinTime+ -11), clpz:(_C#=<FinTime+ -20), clpz:(_D#=<FinTime+ -20), clpz:(_E#=<FinTime+ -2), clpz:(_F#=<FinTime+ -2), clpz:(_G#=<FinTime+ -4), clpz:(_A in 105..sup), clpz:(_A#=<_G+ -11), clpz:(_F#=<_A+ -2), clpz:(_D#=<_A+ -20), clpz:(_C#=<_A+ -20), clpz:(_B#=<_A+ -11), clpz:(_E#=<_A+ -2), clpz:(_G in 70..sup), clpz:(_G#=<_B+ -4), clpz:(_G#=<_E+ -4), clpz:(_G#=<_F+ -4), clpz:(_G#=<_C+ -4), clpz:(_G#=<_D+ -4), clpz:(_B in 94..sup), clpz:(_D#=<_B+ -20), clpz:(_C#=<_B+ -20), clpz:(_F#=<_B+ -2), clpz:(_E#=<_B+ -2), clpz:(_D in 78..sup), clpz:(_E#=<_D+ -2), clpz:(_D#=<_C+ -20), clpz:(_F#=<_D+ -2), clpz:(_E in 76..sup), clpz:(_F#=<_E+ -2), clpz:(_E#=<_C+ -2), clpz:(_F in 74..sup), clpz:(_F#=<_C+ -2), clpz:(_C in 78..sup)
%@ ;  Schedule = [t1/1/_G/4,t2/1/_F/2,t3/1/_E/2,t4/1/_D/20,t5/1/_C/20,t6/1/_B/11,t7/1/_A/11], clpz:(FinTime in 70..sup), clpz:(_A#=<FinTime+ -11), clpz:(_B#=<FinTime+ -11), clpz:(_C#=<FinTime+ -20), clpz:(_D#=<FinTime+ -20), clpz:(_E#=<FinTime+ -2), clpz:(_F#=<FinTime+ -2), clpz:(_G#=<FinTime+ -4), clpz:(_A in 67..sup), clpz:(_G#=<_A+ -4), clpz:(_F#=<_A+ -2), clpz:(_D#=<_A+ -20), clpz:(_C#=<_A+ -20), clpz:(_B#=<_A+ -11), clpz:(_E#=<_A+ -2), clpz:(_G in 59..sup), clpz:(_B#=<_G+ -11), clpz:(_G#=<_E+ -4), clpz:(_G#=<_F+ -4), clpz:(_G#=<_C+ -4), clpz:(_G#=<_D+ -4), clpz:(_B in 67..sup), clpz:(_D#=<_B+ -20), clpz:(_C#=<_B+ -20), clpz:(_F#=<_B+ -2), clpz:(_E#=<_B+ -2), clpz:(_D in 67..sup), clpz:(_E#=<_D+ -2), clpz:(_D#=<_C+ -20), clpz:(_F#=<_D+ -2), clpz:(_E in 65..sup), clpz:(_F#=<_E+ -2), clpz:(_E#=<_C+ -2), clpz:(_F in 63..sup), clpz:(_F#=<_C+ -2), clpz:(_C in 67..sup)
%@ ;  Schedule = [t1/1/_G/4,t2/1/_F/2,t3/1/_E/2,t4/1/_D/20,t5/1/_C/20,t6/1/_B/11,t7/1/_A/11], clpz:(FinTime in 82..sup), clpz:(_A#=<FinTime+ -11), clpz:(_B#=<FinTime+ -11), clpz:(_C#=<FinTime+ -20), clpz:(_D#=<FinTime+ -20), clpz:(_E#=<FinTime+ -2), clpz:(_F#=<FinTime+ -2), clpz:(_G#=<FinTime+ -4), clpz:(_A in 67..sup), clpz:(_A#=<_G+ -11), clpz:(_F#=<_A+ -2), clpz:(_D#=<_A+ -20), clpz:(_C#=<_A+ -20), clpz:(_B#=<_A+ -11), clpz:(_E#=<_A+ -2), clpz:(_G in 78..sup), clpz:(_B#=<_G+ -11), clpz:(_G#=<_E+ -4), clpz:(_G#=<_F+ -4), clpz:(_G#=<_C+ -4), clpz:(_G#=<_D+ -4), clpz:(_B in 67..sup), clpz:(_D#=<_B+ -20), clpz:(_C#=<_B+ -20), clpz:(_F#=<_B+ -2), clpz:(_E#=<_B+ -2), clpz:(_D in 82..sup), clpz:(_E#=<_D+ -2), clpz:(_D#=<_C+ -20), clpz:(_F#=<_D+ -2), clpz:(_E in 82..sup), clpz:(_F#=<_E+ -2), clpz:(_E#=<_C+ -2), clpz:(_F in 82..sup), clpz:(_F#=<_C+ -2), clpz:(_C in 82..sup)
%@ ;  ... .

🤔

[UWN]

(It is often helpful to add extend the core relation with an argument for the variables to be labeled. Thus schedule_(FinTime, Schedule, Zs). In this manner you get a bit more freedom with various search schemes to use the relation.)

In your case it is not that easy to determine extrema. As long as there would be a single leaf answer. Just label with FinTime first. But in your case it is not evident in which of the many leaf answers the extremum is hidden so you have to enumerate them somehow.
The most naive way would be to enumerate FinTime first before schedule_/3 and then label. Alternatively or complementarily label upto_in to avoid useless enumeration of irrelevant values. So you enumerate all possible values of FinTime and then take its extremum (which is the non-monotonic part of it).

?- X in 1..10, Y in 4..6, X #< Y, labeling([],[X,Y]).
   X = 1, Y = 4
;  X = 1, Y = 5
;  X = 1, Y = 6
;  X = 2, Y = 4
;  X = 2, Y = 5
;  X = 2, Y = 6
;  X = 3, Y = 4
;  X = 3, Y = 5
;  X = 3, Y = 6
;  X = 4, Y = 5
;  X = 4, Y = 6
;  X = 5, Y = 6.
?- X in 1..10, Y in 4..6, X #< Y, labeling([upto_in],[X,Y]).
   X = 1, clpz:(Y in 4..6)
;  X = 2, clpz:(Y in 4..6)
;  X = 3, clpz:(Y in 4..6)
;  X = 4, clpz:(Y in 5..6)
;  X = 5, Y = 6.

[jjtolton]

Ah you're right, I actually totally forgot this is an NP-hard problem so there's no easy way to automatically find that. Taking what you said, ignoring the important parts, and then abusing the intent 😰 😰 😰 I came up with this hack that I'm scared to even post:

?- once((FinTime in 20..35, indomain(FinTime), once(schedule(FinTime, Schedule)))).
%@    FinTime = 22, Schedule = [t1/1/_A/4,t2/1/0/2,t3/2/0/2,t4/1/2/20,t5/2/2/20,t6/3/11/11,t7/3/0/11], clpz:(_A in 2..18).

It looks like there's a significant amount of study to formulate these the correct way to take advantage of CP features properly, so I'll keep studying!

[UWN]

It has nothing to do with NP-hardness or another complexity class. To conclude that it is a bit more difficult to implement it was sufficient to see the leaf answers I asked you for.

More complex search schemes are thinkable, in particular those that restart once a new extremum has been found.

And, then maybe it is possible to reformulate the problem such all solutions are represented in a single leaf answer.