Scryer-prolog: Please help debug library(simplex)

[triska]

Here is a version of library(simplex) that runs with Scryer Prolog, intended for future inclusion in the system:

https://www.metalevel.at/prolog/scryer/simplex.pl

assignment/2 and transportation/4 already work, and solve assignment and transportation problems with good asymptotic complexity.

The examples given at the start of the file also work, except for the "coins" example:

:- use_module(simplex).
:- use_module(library(dcgs)).

coins(S) :-
    gen_state(S0),
    coins(S0, S).

coins -->
    constraint([c(1), 5*c(5), 20*c(20)] = 111),
    constraint([c(1)] =< 3),
    constraint([c(5)] =< 20),
    constraint([c(20)] =< 10),
    constraint([c(1)] >= 0),
    constraint([c(5)] >= 0),
    constraint([c(20)] >= 0),
    constraint(integral(c(1))),
    constraint(integral(c(5))),
    constraint(integral(c(20))),
    minimize([c(1), c(5), c(20)]).

Yielding:

?- coins(S), variable_value(S, c(1), C1),
         variable_value(S, c(5), C5),
         variable_value(S, c(20), C20).
nontermination

I know that branch_and_bound/8 does not terminate in this case. However, I do not know why, and I currently cannot look into it because I am working on other issues.

If you are interested in combinatorial optimisation and this library, please help me debug the issue, for example by using the predicates mentioned in #461 to find out what is going on, or by constructing a smaller example that also exhibits unexpected nontermination.

This may be an interesting issue for new contributors.

[notoria]

This program works but the order doesn't seems to matter, minimize([c(5), c(1)]) and minimize([c(1), c(5)]) produce the same solution. What did you use to implement branch_and_bound/8? (book, reference, ...)

[triska]

Thank you a lot for looking into this!

In minimize/3, the objective function is represented as a list ofCoefficient*Variable terms that represents the sum of its elements, so [c(5),c(1)] means c(5) + c(1), which amounts to the same result as c(1) + c(5). This is the reason why we get the same result in both cases.

I implemented branch_and_bound/8 from a booklet on algorithms and data structures from a university course. The surprising result in this case is the nontermination for the example I posted. The other examples work correctly.

[notoria]

Doing this permutation:

    constraint(integral(c(1))),
    constraint(integral(c(20))),
    constraint(integral(c(5))),

The nontermination disappears. Commenting can also remove the nontermination.

[triska]

Very nice findings, thank you a lot!

To debug the issue further, an ideal case would be a very small example (as small as possible) that also exhibits nontermination. In this way, we could more easily trace the steps that branch and bound performs, and how it goes wrong.

[triska]

It could be an interesting project to write a Prolog program that tries to construct such an example by systematic search for it, or systematically reduces a given example to a minimal one.

[notoria]

In the first case, by changing the value of k, constraint([c(1), k*c(5), 20*c(20)] = 111), it terminates for 1, 2, 4, 8, 11 and it seems to loop forever for 3, 6, 7, 9, 10.

Will try that constructive way.

[notoria]

Not sure but this seems to not terminate (unless permutation of integral):

:- use_module(simplex).
:- use_module(library(dcgs)).

:- op(950, fy, *). *_.

coins(S) :-
    gen_state(S0),
    coins(S0, S).

coins -->
    constraint([3*c(5), 20*c(20)] = 110),
    constraint([c(5)] =< 20),
    constraint([c(20)] =< 10),
    constraint([c(5)] >= 0),
    constraint([c(20)] >= 0),
    constraint(integral(c(5))),
    constraint(integral(c(20))),
    minimize([c(5), c(20)]).

test(S) :-
    coins(S),
    variable_value(S, c(5), C5),
    variable_value(S, c(20), C20),
    writeq(C5), nl,
    writeq(C20), nl,
    true.

Not found by the constructive method.

[triska]

Excellent find! Thank you a lot, this already simplifies the problem considerably!