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

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