Re: [eclipse-clp-users] Multiple objective knapsack problem

On Tue, 17 Feb 2015, Aaron Hunter wrote:
> items with two attributes X and Y. Each item takes up exactly 1 slot in the
> knapsack. The knapsack holds six items. I want to find one or more solutions
> that maximize X and Y.

What exactly does that mean?

For instance, suppose you have a very simple instance with three items.
Item A has X=1, Y=2; item B has X=2, Y=1; item C has X=1, Y=1.  Your
knapsack has capacity 1.

What solution or solutions would you consider to "maximize X and Y"?

One reasonable interpretation might be that you want solutions that are
not dominated by other solutions - that is, solutions satisfying the
criterion "no other solution increases X or Y without decreasing the
other."  Under that definition, taking A or B in my example would be
optimal even though each of them beats the other on one of the objectives;
taking C would not be optimal because it is dominated by either of the
other two solutions.  But each of them fails to maximize one of the
objectives, considered alone.  This is basically the definition of Pareto
optimality.

If that's what you want, I don't think there's any built-in way to extract
all such solutions, but you could get one by fixing some linear
combination of the two objective functions and maximizing that.  You could
get all of them by first maximizing X alone, then taking the value of Y
from that solution and maximizing X subject to a strict improvement in Y,
and repeating.

-- 
Matthew Skala
mskala_at_...206...                 People before principles.
http://ansuz.sooke.bc.ca/