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

From: Misha Aizatulin <tari3x_at_...6...>
Date: Tue, 05 Mar 2013 14:31:49 +0000
hi Joachim and Kish,

  thanks a lot, that was very helpful! I tried learning from examples
but didn't bother to read the tutorial far enough - my bad!

Best,
  Misha

On 02/28/2013 11:14 PM, Joachim Schimpf wrote:
> 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
> 
> ------------------------------------------------------------------------------
> Everyone hates slow websites. So do we.
> Make your web apps faster with AppDynamics
> Download AppDynamics Lite for free today:
> http://p.sf.net/sfu/appdyn_d2d_feb
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
> 
Received on Tue Mar 05 2013 - 14:32:00 CET

This archive was generated by hypermail 2.3.0 : Thu Feb 22 2024 - 18:13:20 CET