# 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,
>
>
> 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/
```
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