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

From: Marco Gavanelli <marco.gavanelli_at_...17...>
Date: Tue, 04 May 2010 10:40:23 +0200
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

- 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:

     A+B #> 10,
     F1 #= A,
     F2 #= B,
          (   bb_min(
              ->     write('found solution with cost '),
              ;      !

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


Marco Gavanelli, Ph.D. in Computer Science
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
Received on Tue May 04 2010 - 08:40:38 CEST

This archive was generated by hypermail 2.3.0 : Sun Aug 25 2019 - 09:14:48 CEST