fd_maximize/fd_labeling with timeout

[Fred Bapst]

For a project dealing with large fd optimization problems (thousands of boolean
variables and constraints), we thought that it would be (very!) useful to have a
"timeout" version of fd_maximize and fd_labeling (by the way, such a feature is
available in other constraint programming tools, eg GeCode).

Taking as basis the implementation found in fd_values.pl and fd_optim.pl, we
wrote a first version of those predicates. Adapting the code was easy, but there
are many points that may need a discussion, such as:

- specification: how to precisely inform the caller about the 4 possible
outcomes (normal failure; failure due to timeout; optimal solution found;
solution found but timeout occurred); throwing an exception could be an option,
giving back a status (so never failing) is another. Our first version combines a
status with an ugly global variable trick...

- specification: how to interpret the timeout in case of 'redo'. In our first
version it is "somehow" (I know how, and see the drawbacks) taken into account
in my_labeling, but not in my_maximize.

- precision against the timeout in fd_maximize: the current implementation
happens to finally re-issue the call giving the "best" solution found, but with
a slightly different condition: the first time it was with a constraint (Z #>
PreviousBound), and the second time with (Z #= LastValidBound). The fact is that
measuring the duration of the first call does not directly help in estimating
the second call. Having this in mind, is it better to return too early (meaning
we do not always use the allowed resources), or too late (meaning we do not
always respect the timeout which could be 2x longer)?

Do you think such a feature should be included in the library ? On one hand I
find it very useful in practice; on the other hand, a routine with a too obscure
specification probably doesn't fit in a library.

Any comment is welcome.

Here is the code of this very first quick-and-dirty version.

%-----------------------------------------------------------
%--- my_maximize(+Goal, #Var, +TimeoutMs, -Status)
%    same as fd_maximize(Goal, Var), but with a time limit.
%    Here we suppose Goal is a call to fd_labeling/2.
%    Possible situations:
%    - fail (no solution found). It may be because of the timeout.
%      Then the global variable my_labeling_timeout is set to 'timeout'
%      instead of '0' (meaning 'no_timeout').
%    - optimal solution found. Then Status is set to 'completed'
%    - solution found, but timeout reached when trying to refine it.
%      Then Status is set to 'timeout'
%    Internally, the call to Goal that produced the best result is re-issued
%    (slightly differently), and that makes it hard to respect the timeout
%    strictly...
my_maximize(Goal, Var, Timeout, Status) :-
    fd_max_integer(Inf),
    g_assign('$my_max', 0),
    g_assign('$my_max_lastcall_duration', 0),
    real_time(T0),
    repeat,
    g_read('$my_max', B),
    B1 is B + 1,
    (   fd_domain(Var, B1, Inf),
        real_time(T1),
        g_read('$my_max_lastcall_duration', LastDuration),
        % here we assume that calling again Goal with Var#=B instead of Var#>=B
        % will cost the same; but generally it is faster...
        TimeLeft is Timeout-(T1-T0)-LastDuration,
        my_maximize_translate_goal(Goal, TimeLeft, NewGoal),
        write(best(B,timeLeft(TimeLeft))),  % todo: remove that tracing
        NewGoal,
        real_time(T2),
        ThisDuration is T2-T1, write(this(ThisDuration)), nl,
        g_assign('$my_max_lastcall_duration', ThisDuration)
    ->
        fd_max(Var, C),
        g_assign('$my_max', C),
        fail
    ;
        !,
        g_read(my_labeling_timeout, U),
        my_maximize_set_status(U, completed, Status),
        Var = B,
        real_time(T3),
        Goal,
        real_time(T4),
        TT is T4-T3,
        write(finalCall(TT)), nl  % todo: remove that tracing
    ).

my_maximize_translate_goal(fd_labeling(Ls,Options), Duration, NewGoal) :-
    !,
    NewGoal=my_labeling(Ls, Options, Duration).

my_maximize_translate_goal(Goal, _, Goal).

my_maximize_set_status(0, Status, Status).
my_maximize_set_status(timeout, _, timeout).


%-----------------------------------------------------------
%--- my_labeling(List, Option, TimeoutInMs):
%    same as fd_labeling(List, Option), but if the process duration
%    in milliseconds exceeds TimeoutMs, it fails.
%    Then the global variable my_labeling_timeout is set to 'timeout'
%    instead of '0' (meaning 'no_timeout').
my_labeling(List, Options, Timeout) :-
    '$set_labeling_defaults',
    '$get_labeling_options'(Options, Bckts),
    '$sys_var_read'(0, VarMethod),
    '$sys_var_read'(1, ValMethod),
    '$sys_var_read'(2, Reorder),
    '$fd_reset_labeling_backtracks',
    (   ( fd_var(List) ; integer(List) ) ->
        '$indomain'(List, ValMethod)
    ;
        '$check_list'(List),
        real_time(T0),
        g_assign(my_labeling_timeout, 0),
        my_labeling1(List, VarMethod, ValMethod, Reorder, timeout(Timeout,T0))
    ),
    '$fd_get_labeling_backtracks'(Bckts).


my_labeling1(List, 0, ValMethod, _, TimeOption) :-        %standard
    !, my_labeling_std(List, ValMethod, TimeOption).

my_labeling1(List, VarMethod, ValMethod, Reorder, TimeOption) :-
    '$fd_sel_array_from_list'(List, SelArray),
    my_labeling_mth(SelArray, VarMethod, ValMethod, Reorder, TimeOption).


my_labeling_std([], _, _).

my_labeling_std([X|List], ValMethod, timeout(Timeout,T0)) :-
    real_time(T1),
    ( (T1-T0) < Timeout
    ->
       '$indomain'(X, ValMethod),
        my_labeling_std(List, ValMethod, timeout(Timeout,T0))
    ;
       g_assign(my_labeling_timeout, timeout),   % timeout event reporting
       fail
    ).


my_labeling_mth(SelArray, VarMethod, ValMethod, Reorder, timeout(Timeout,T0)) :-
    '$fd_sel_array_pick_var'(SelArray, VarMethod, Reorder, X), !,
    real_time(T1),
    ( (T1-T0) < Timeout
    ->
       '$indomain'(X, ValMethod),
        my_labeling_mth(SelArray, VarMethod, ValMethod, Reorder,
                        timeout(Timeout,T0))
    ;
       g_assign(my_labeling_timeout, timeout),   % timeout event reporting
       fail
    ).

my_labeling_mth(_, _, _, _, _).