CLP(FD): Option list for labeling/2

[Markus Triska-2]

The recent discussion about properties of option lists raise my hope
that similarly useful suggestions/opinions and consensus can be obtained
about the option list for the labeling/2 predicate in library(clpfd):

   http://gollem.science.uva.nl/SWI-Prolog/Manual/clpfd.html

Briefly, labeling/2's first argument is a list of options that let you
exhibit some control over the search process. It currently allows
conflicting options (like [ff,ffc,up,down]), in which case the options
occurring *right*most in the list take precedence over all conflicting
options (options fall into several distinct non-conflicting categories).

This behaviour is the one which is also documented in the SICStus
manual, and it can come in handy for example in the following case:
Suppose you wrote constraint code and found a "good" set of labeling
options, say [ff,down], in your_predicate/2. Then you can write:

   your_predicate(UserOptions, Vs) :-
      constraint(Vs),
      ...,
      labeling([ff,down|UserOptions], Vs).

A user can then use your predicate like this:

   your_predicate([leftmost,up], Variables)

and thus override all your predetermined options later.

But this behaviour of labeling/2 also has several drawbacks: First,
unintentionally conflicting options are not reported, and one can do:

   labeling([min(X),ff,down,max(X)], Vs)

Clearly, min(X) and max(X) are conflicting. The latter takes precedence,
since it occurs rightmost, which may not be very intuitive in this case.

Even worse, since no error is reported, users can easily draw the
mistaken conclusion that they can "maximize X", THEN "maximize Y" by
stating different max(...) options, i.e.:

   labeling([max(X),max(Y)], Vs)

But again, the latter takes precedence, and the former is ignored.

Actually, in the specific case of optimization options (min/max), it
might make sense to respect all given options in the order in which they
are stated. In the case above, one would first maximize X, THEN maximize
Y etc. Clearly, [max(X), min(X)] would still be conflicting. But what
options are conflicting? If the same variable occurs in both a min/1 and
a max/1 option? Maybe there is a nicer syntax to specify optimisation?

And what would you like to see when options are conflicting? A domain
error, or do you prefer the current "silent" precedence rules? Should
only the optimization options be exempt from this precedence, and be
respected in their natural order? If the precedence rules should be
dropped, is there still a nice way to override predetermined options?

Please share your suggestions and opinions about how labeling/2 should
behave in these cases. Do you have use cases where you want a specific
behaviour in labeling/2? Was anything surprising to you in its use? Some
users will want to specify their own labeling strategies as another
category of options. Currently, labeling/2 is always complete and always
terminates, no matter what options you choose. Giving users complete
freedom over variable and value selection strategies can destroy these
properties, and there should really be a different labeling predicate
for this purpose. Also for this, suggestions are very welcome.

Thank you and all the best,
Markus

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Fernando Sáenz Pérez]

Hello.
First of all, many thanks to Markus for his work about the clp(fd) library.
Regarding his message:

> The recent discussion about properties of option lists raise my hope
> that similarly useful suggestions/opinions and consensus can be obtained
> about the option list for the labeling/2 predicate in library(clpfd):
>
>   http://gollem.science.uva.nl/SWI-Prolog/Manual/clpfd.html
>
> Briefly, labeling/2's first argument is a list of options that let you
> exhibit some control over the search process. It currently allows
> conflicting options (like [ff,ffc,up,down]), in which case the options
> occurring *right*most in the list take precedence over all conflicting
> options (options fall into several distinct non-conflicting categories).
>
> This behaviour is the one which is also documented in the SICStus
> manual, and it can come in handy for example in the following case:
> Suppose you wrote constraint code and found a "good" set of labeling
> options, say [ff,down], in your_predicate/2. Then you can write:
>
>   your_predicate(UserOptions, Vs) :-
>      constraint(Vs),
>      ...,
>      labeling([ff,down|UserOptions], Vs).
>
> A user can then use your predicate like this:
>
>   your_predicate([leftmost,up], Variables)
>
> and thus override all your predetermined options later.
>
> But this behaviour of labeling/2 also has several drawbacks: First,
> unintentionally conflicting options are not reported, and one can do:
>
>   labeling([min(X),ff,down,max(X)], Vs)
>
> Clearly, min(X) and max(X) are conflicting. The latter takes precedence,
> since it occurs rightmost, which may not be very intuitive in this case.
>
> Even worse, since no error is reported, users can easily draw the
> mistaken conclusion that they can "maximize X", THEN "maximize Y" by
> stating different max(...) options, i.e.:
>
>   labeling([max(X),max(Y)], Vs)
>
> But again, the latter takes precedence, and the former is ignored.
>
> Actually, in the specific case of optimization options (min/max), it
> might make sense to respect all given options in the order in which they
> are stated. In the case above, one would first maximize X, THEN maximize
> Y etc. Clearly, [max(X), min(X)] would still be conflicting. But what
> options are conflicting? If the same variable occurs in both a min/1 and
> a max/1 option? Maybe there is a nicer syntax to specify optimisation?
>
> And what would you like to see when options are conflicting? A domain
> error, or do you prefer the current "silent" precedence rules? Should
> only the optimization options be exempt from this precedence, and be
> respected in their natural order? If the precedence rules should be
> dropped, is there still a nice way to override predetermined options?
>
> Please share your suggestions and opinions about how labeling/2 should
> behave in these cases. Do you have use cases where you want a specific
> behaviour in labeling/2? Was anything surprising to you in its use? Some
> users will want to specify their own labeling strategies as another
> category of options. Currently, labeling/2 is always complete and always
> terminates, no matter what options you choose. Giving users complete
> freedom over variable and value selection strategies can destroy these
> properties, and there should really be a different labeling predicate
> for this purpose. Also for this, suggestions are very welcome.
>
> Thank you and all the best,
> Markus

I think that stating the options in labeling is too free and, first,
should be constrained to legal uses and the resolution of satisfaction
and optimization problems should be separated.
Wrt. to satisfaction problems, one can distinguish among:
- Variable selection strategy (Default values: leftmost, ff, ffc)
- Branching strategy (Default values: step, enum, bisect)
- Value order (Default values: up, down)
- Solution order (Default values: min(Expr), max(Expr))
Wrt. to optimization problems:
- Optimization strategy (Default values: bb, ...)
What I would like to have is:
labeling(+Vars). % For default options
labeling(?VariableSelectionStrategy,?BranchingStrategy,+Vars) % For
specifying variable selection strategies. If a strategy is not specified
(variable argument), it shoud be unified with the default. So, the use
labeling(_,_,Vars) should be equivalent to labeling(Vars). Since value
order only applies to given branching strategies, then I'd like to write
something as step(down) as the branching strategy; since the value order
default is 'up', then, specifying enum would amount to enum(up). Illegal
combinations should raise an exception, as in labeling(ff,bisect(up),Vars).
If the order or solutions is also allowed to be configured, then:
labeling(?VariableSelectionStrategy,?BranchingStrategy,?SolutionOrders,+Vars)
% If several orders are allowed as in [min(Expr1),max(Expr2)], I'd
understand them as a way to sort the solutions wrt., first, ascending
values of Expr1, and for the same values of Expr1, show descending
values of  Expr2. Then, if we have [min(X), max(X)], this only states:
show solutions in ascending order of X, then, for each value of X, show
solutions in descending order of X, which yields the same ordering since
we refer to the same single value of X. Illegal uses following the
current implementation be hard to detect.
minimize(+Vars). % For default options
minimize(?OptimizationStrategy,+Vars). % For specifying only
optimization strategies. If a strategy is not specified (variable
argument), it shoud be unified with the default. So, the use
minimize(_,Vars) should be equivalent to minimize(Vars).
By the way, though there is only one minimum for an optimization
problem, it may correspond to different decision variable assignments.
For instance, if one tries to minimize a function as F=X mod 3, there is
as much solutions for X as 1/3 values in its domain. The system should
report about all this solutions for it to be complete.
A strategy for satisfaction/optimization problems can be predefined and
could be user-definable, but I do not think that the best way is to
overload labeling for this. Instead, simply provide reflection
predicates, and let the user build its own strategy. If I would like to
program my particular enumeration procedure, then I would write:
my_labeling(+Vars)
as a usual Prolog predicate. This, in addition, preserves the good
properties of the provided labeling procedure.
Best regards.
Fernando

--
==============================================================
Fernando Sáenz Pérez
Profesor Titular de Universidad / Associate Professor
Home Page: http://www.fdi.ucm.es/profesor/fernan
Tel: + 34 913947642. Fax: + 34 913947547
Despacho / Office: 435 (4ª planta / 4th floor)
Dept. Ingeniería del Software e Inteligencia Artificial /
Department of Software Engineering and Artificial Intelligence
Universidad Complutense de Madrid
Facultad de Informática
C/Profesor José García Santesmases, s/n
E - 28040 Madrid. Spain
==============================================================


------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Markus Triska-2]

Hi Fernando,

thank you for your insightful suggestions; my comments are embedded:

Fernando Sáenz Pérez <fernan@...> writes:

> labeling(+Vars). % For default options

This is good. Currently, there's label/1 with the same meaning;
labeling/2 should probably be kept for SICStus compatibility, but we can
thus use label/2, label/3 etc. for the other versions.

> specifying variable selection strategies. If a strategy is not
> specified (variable argument), it shoud be unified with the default.

Yes, and with other possible options on backtracking (otherwise it would
of course break monotonicity). Where there is no feasible way to
generate all possible options (like for optimisation expressions), it
must raise an instantiation error. However, I would even suggest
instantiation errors when the other options are not ground: Otherwise
labeling can take much longer and lead users to suspect performance
problems when in fact they only forgot to specify an option. This is one
reason why ins/2 creates an instantiation error instead of generating
all list lengths on backtracking if the first argument is not a list.

> labeling(?VariableSelectionStrategy,?BranchingStrategy,?SolutionOrders,+Vars)

This would indeed be good for the currently available set of options.
However, what about others or new ones, should we keep increasing
arities for them? For example, there are already (undocumented) options
in labeling/2 which are currently being discussed and will probably
become officially available soon. One example is upto_in/1:

   %?- [X,Y,Z] ins 0..100, 5*X #< Y, labeling([upto_in(S)], [X,Y,Z]).
   %@ X = 0, S = 10100, Y in 1..100, Z in 0..100 ;
   %@ X = 1, S = 9595, Y in 6..100, Z in 0..100 ;
   %@ X = 2, S = 9090, Y in 11..100, Z in 0..100 ; etc.

upto_in(S) labels variables until the remaining ones only have an in/2
constraint attached (which is trivially satisfiable), and S is unified
with the number of solutions that would arise if all variables were
labeled up to ground values. This allows to count solutions quickly.

Other sets of options are also conceivable for the future (backjumping,
learning, posting CLP(Q) constraints, verification etc.), and I've
therefore so far been reluctant to introduce higher arities for
different categories. But maybe it wouldn't be much of a problem?

> If several orders are allowed as in [min(Expr1),max(Expr2)], I'd
> understand them as a way to sort the solutions wrt., first, ascending
> values of Expr1, and for the same values of Expr1, show descending
> values of  Expr2. Then, if we have [min(X), max(X)], this only states:

I agree, and this is probably also what most users expect. I've already
seen a program where this was implicitly (and, so far, wrongly) assumed.
I've committed it in the "vienna" branch, which we use for experimental
changes in the CLP(FD) solver and related areas. You can try it with:

   $ git checkout -b vienna  --track origin/vienna

If it works as intended, I'll apply it to the master branch too.

> minimize(+Vars)

You mean a separate predicate for optimisation? That's an interesting
suggestion. We could have e.g.:

   optimisation(+MinMaxOpts, +LabelingOpts, +Vs)

This would separate the optimisation options (which can be several) from
the labeling options (where only one of each category is applicable).

> For instance, if one tries to minimize a function as F=X mod 3, there
> is as much solutions for X as 1/3 values in its domain. The system
> should report about all this solutions for it to be complete.

Absolutely; and indeed library(clpfd) is complete for all options, i.e.:

   ?- F #= X mod 3, X in 0..100, labeling([max(F)], [X]).
   %@ F = 2, X = 2 ;
   %@ F = 2, X = 5 ;
   %@ F = 2, X = 8 ;
   %@ F = 2, X = 11 ; etc.

One can use once/1 to get the incomplete behaviour of other systems.

> as a usual Prolog predicate. This, in addition, preserves the good
> properties of the provided labeling procedure.

Yes; one thing not considered so far is how options can be overridden if
we do away with the option list, i.e., labeling([ff,up|UserOptions], Vs).
Maybe this isn't a big problem? There probably aren't many programs that
use it that way, but it would be nice if it can still be supported.

Thank you and all the best,
Markus

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...

[Fernando Sáenz Pérez]

Markus Triska wrote:

Other sets of options are also conceivable for the future (backjumping,
learning, posting CLP(Q) constraints, verification etc.), and I've
therefore so far been reluctant to introduce higher arities for
different categories. But maybe it wouldn't be much of a problem?
  

I agree, increasing the arity would not be a good idea for increasing set of options. The point that I think is adviceable is to have separate sets of options for the user, e.g., options for variable selection, value selection and so on, so that orthogonal procedures in labeling can be selected without allowing to mix them and therefore cuting possible user misunderstandings and errors. Maybe, a list of procedures/options can be used, as, e.g.:
[var_sel(+VarSPs), val_sel(+ValSPs), branching(+BPs)...]
This also allows to add further options and procedures/strategies.

Yes; one thing not considered so far is how options can be overridden if
we do away with the option list, i.e., labeling([ff,up|UserOptions], Vs).
Maybe this isn't a big problem? There probably aren't many programs that
use it that way, but it would be nice if it can still be supported.

  

As a user, with respect to those default options, I'd expect not to mix incompatible options when I state them and, if mixed, I would expect an exception. I dislike to allow to state incompatible or overridable options and let the system decide in terms of a given criteria (e.g., selecting the rightmost option). For instance: [ff,ffc] would raise an exception. But, obviously, this is only my personal point of view.
Best regards
Fernando

[Markus Triska-2]

Fernando Sáenz Pérez <fernan@...> writes:

> As a user, with respect to those default options, I'd expect not to
> mix incompatible options when I state them and, if mixed, I would
> expect an exception. I dislike to allow to state incompatible or
> overridable options and let the system decide in terms of a given
> criteria (e.g., selecting the rightmost option). For instance:
> [ff,ffc] would raise an exception.

Yes, this sounds good. It is only left to decide which error this is. A
domain error seems sensible, but what should be the culprit? The whole
list, just the two contradicting options, or something else? A
representation error would be justified too since we can regard [ff,ffc]
as a system defined limit: We currently cannot handle such contradicting
options, but something sensible could be done with them. Opinions?
Examples of other predicates that handle contradicting options sensibly?

All the best,
Markus

------------
For further info, please visit http://www.swi-prolog.org/

To unsubscribe, send a plaintext mail with "unsubscribe prolog <e-mail>"
in its body to majordomo@...