Re: [eclipse-clp-users] Bugs in http://87.230.22.228/examples/crew.ecl.txt?

C A wrote:
> I just wanted to point out that I think there is a problem with the
> crew.pl example linked from  the main Eclipse website and I wonder if
> someone (far more proficient than me) could double-check as I've spent a
> lot of time tyring to work out  whether the problem is me or the program!
> 
> The problem centers around the "two-days-rest" clauses. This works for
> the data given but when the data approaches the limits of possibilty to
> satisfy the contraints (maximum crew members etc) the two-days-rest
> constraint seems to fly out of the cabin window! I know unions are weak
> these days but... ;-)
>
> I ran it with this data overnight (it took 5 hours):
>
> flights(
>   [flight( 1,crew:6,stewards:3,stewardesses:3,french:1,spanish:1,german:1),
>    flight( 2,crew:6,stewards:3,stewardesses:3,french:1,spanish:1,german:1),
>    flight( 3,crew:6,stewards:3,stewardesses:3,french:1,spanish:1,german:1),
>    flight( 4,crew:7,stewards:3,stewardesses:3,french:1,spanish:1,german:1),
>    flight( 5,crew:7,stewards:3,stewardesses:3,french:1,spanish:1,german:1),
>    flight( 6,crew:7,stewards:3,stewardesses:3,french:1,spanish:1,german:1)
>    ]
> ).
> 
> And no solution respected the two_days_off clauses.


Hi Chris,

you are absolutely right, it is a bug in the program!  Obviously, with your
data set there should be no solution, as you have only 20 staff, and for the
last flight 14 of them are out because they have done the two flights before.

The problem is here:

two_days_off([X,Y,Z|Rest]) :-       %%% cut ! missing
  all_disjoint([X,Y,Z]),
  two_days_off([Y,Z|Rest]).
two_days_off(_Rest).

What happens is that after the search (with insetdomain) is completed
unsuccessfully, the program backtracks to the 2nd clause of two_days_off
and succeeds again, this time with one all_disjoint-constraint missing...
It does that until enough of them are removed so that a solution is found.

Once the cut is add, a solution is found immediately.

It is a little bit disappointing that the all_disjoint-constraint does not
detect the infeasibility of your original data set.  The library(cardinal),
an alternative set solver, would probably do that, as it contains stronger
reasoning over set cardinalities.  However, you can also strengthen the
reasoning by manually adding a redundant constraint, e.g.
...
  all_disjoint([X,Y,Z]),
  #(X)+ #(Y)+ #(Z) #=< Nattendants,
...
With this addition (plus the bug fix), your data set fails straight away.


-- Joachim