Re: [eclipse-clp-users] Pareto Optimality + Branch and Bound?

Philipp Marcus wrote:
> Hi,
> 
> thanks for all your helpful replies.
> 
> At 30.04.2010 03:48, Joachim Schimpf wrote:
>> I really have to apologize to Marco, because he gave me his code years
>> ago, and I never got round to update it for IC and to put it into the
>> ECLiPSe distribution...
>>    
> 
> are you still planing to port Marco's code to IC and if so, can you give 
> an estimate until when it would be finished? His code would be exactly 
> what I'd need but at the moment I don't feel experienced enough to port 
> it from FD to IC on my own.

Dear Joachim and Philipp,

there is no need for Joachim to apologize: I know he is very busy and
works hard to make ECLiPSe the excellent platform it is now.

I think the code by Joachim is correct; I remember a talk by Filippo
Focacci at CPAIOR 02 on a similar method.

Concerning the Pareto front, I must give two warnings to Philipp:

- First, computing the Pareto front is VERY expensive: it will take a
long time, and it will likely produce an exponentially long list of
solutions.

- Second, as for all NP-hard problems, there is no solution that is 
always the best. As for one-function minimization, one can use the 
'continue' or the 'restart' strategy, and each works well in some cases.
The method I proposed in ECAI02 was using the 'continue' strategy.

However, the 'restart' strategy is probably easier to implement.
Try the following example:

run:-
     [A,B]::0..10,
     A+B #> 10,
     F1 #= A,
     F2 #= B,
     bb_min(
     (
          repeat,
          (   bb_min(
                     labeling([A,B])
                    ,F2,bb_options{strategy:restart})
              ->     write('found solution with cost '),
                     writeln([F1,F2])
              ;      !
          )
     )
     ,F1,bb_options{strategy:restart}).

Of course, if you want a list of solutions you have to store them in 
some unbacktrackable data structure.

Best,
Marco

-- 
Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
http://www.ing.unife.it/docenti/MarcoGavanelli/