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

From: Joachim Schimpf <joachim.schimpf_at_...44...>
Date: Fri, 30 Apr 2010 11:48:58 +1000
```Marco Gavanelli wrote:
>
> Marco Gavanelli. An algorithm for multi-criteria optimization in CSPs.
> In Frank van Harmelen, editor, ECAI 2002. Proceedings of the 15th
> European Conference on Artificial Intelligence, pages 136-140, Lyon,
> France, July 21-26 2002. IOS Press.
>
> I post it on the mailing list, as it may be useful to other people as
> well. The problem is that it works with the FD library, and not with the
> new IC library.

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

Yesterday, I put together some quick code for finding _one_ pareto optimum
directly (without using the weighted-components trick which would drive
your search towards one particular optimum).

I have to say I'm no expert and this is only based on reading the Wikipedia
page on pareto optimality...  So maybe Marco can comment on whether I have
understood things correctly!

-- Joachim

%----------------------------------------------------------------------
% Simple branch-and-bound to find a pareto optimum
%----------------------------------------------------------------------

:- lib(ic).

% arguments similar to bb_min/3
minimize_pareto(Goal, Costs) :-
term_variables(Goal, Vars),
minimize_pareto(Goal, Costs, Vars, Vars, Costs).

% arguments similar to bb_min/6
minimize_pareto(Goal, CostVars, Template, Solution, Opts) :-
% initialize the solution store
( foreach(_,CostVars), foreach(1.0Inf,StartCosts) do true ),
shelf_create(sol(no_solution,StartCosts), Handle),
(
% find improving solutions, then fail
improve(Goal, Template, CostVars, Handle)
;
% retrieve the optimum
shelf_get(Handle, 0, sol(s(Solution),Opts))
).

% Find a solution and store result in Handle (or fail)
improve(Goal, Template, Costs, Handle) :-
repeat, % until cut
% get the tuple of best cost values so far
shelf_get(Handle, 2, BestVals),
(
% constrain Costs to be pareto-better than BestVals
%               impose_improvement_weak(Costs, BestVals, 1),
impose_improvement_strong(Costs, BestVals, 1),
% try and find a better solution
call(Goal)
->
% found one, store it in Handle
( ground(Costs) -> true ;
writeln(error, "search did not instantiate cost variables"),
abort
),
shelf_set(Handle, 0, sol(s(Template),Costs)),
printf(log_output, "Found solution with cost %w%n", [Costs])
;
% no solution, don't try further
!
),
fail.

% Weak pareto condition: require each cost to improve by Delta
impose_improvement_weak(CostVars, BestVals, Delta) :-
( foreach(CostVar,CostVars), foreach(BestVal,BestVals), param(Delta) do
CostVar \$=< BestVal - Delta
).

% Strong pareto condition: require at least one cost to improve by Delta
impose_improvement_strong(CostVars, BestVals, Delta) :-
( foreach(CostVar,CostVars), foreach(BestVal,BestVals), foreach(Di,Dis) do
Di \$= BestVal - CostVar,
Di \$>= 0
),
max(Dis) \$>= Delta,
% redundant constraint for better propagation
sum(CostVars) \$=< sum(BestVals) - Delta.

%----------------------------------------------------------------------
% This test problem has 2 optimal solutions [2,4] and [4,2].
% With random labeling, one of them should be found.
%----------------------------------------------------------------------

test(Xs) :-
Xs = [X,Y],
Xs :: 0..7,
X+Y #>=5,
abs(X-Y) #=2,
minimize_pareto(search(Xs, 0, input_order, indomain_random, complete, []), [X,Y]).
```
Received on Fri Apr 30 2010 - 01:47:17 CEST

This archive was generated by hypermail 2.3.0 : Wed Aug 21 2019 - 09:13:32 CEST