Re: [eclipse-clp-users] Correct use of minimize to find a globally minimal solution

On 27/02/2013 19:30, Misha Aizatulin wrote:
> hi all,
>
>    I'm having trouble understanding how to use minimize(). Attached is a
> simple example that tries to find an allocation of dance lessons to
> dance couples (satisfying requests), and then choose the one with the
> minimal cost. Unfortunately, minimize() does not find the globally
> minimal solution. What is the correct way to use that?

A constraint program has to follow a certain structure, in order to
make sense (http://www.eclipseclp.org/doc/tutorial/tutorial055.html)

solve(Variables) :-
         read_data(Data),
         setup_constraints(Data, Variables),
         labeling(Variables).

An essential point is that the constraint setup code must not contain
"choices" or "alternatives", except in the form of alternative values
for variables (i.e. their domain).  In your code, the cost/3 predicate
represents such choices, and must be replaced.  In the following, I
have used element/3 constraints to do that:


:- lib(ic).
:- lib(branch_and_bound).

%------- the data ---------

ncouples(2).

% request(Couple, PossibleLessons)
request(1, [0,1,2]).
request(2, [0,2,3]).

% Lesson 0 1 2 3
cost(1, [1,0,0,0]).	% Couple 1
cost(2, [0,0,1,1]).	% Couple 2

% ----- the constraint model ---------

schedule(Allocation) :-
     ncouples(NCouples),
     (
         for(I, 1, NCouples),
         foreach(Lesson, Allocation),
         foreach(Cost, Costs)
     do
         request(I, PossibleLessons), % get data
         Lesson :: PossibleLessons,   % create variable
         cost(I, LessonCostsForI),    % get data
         Lesson1 #=Lesson+1,          % create constraints
         element(Lesson1, LessonCostsForI, Cost)
     ),
     alldifferent(Allocation),        % more constraints
     TotalCost #= sum(Costs),

     % ---- the search ----
     minimize(labeling(Allocation), TotalCost).



-- Joachim