From: <mskala_at_ansuz.sooke.bc.ca>

Date: Tue, 17 Feb 2015 10:23:11 -0600 (CST)

Date: Tue, 17 Feb 2015 10:23:11 -0600 (CST)

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_ansuz.sooke.bc.ca People before principles. http://ansuz.sooke.bc.ca/Received on Tue Feb 17 2015 - 16:16:49 CET

*
This archive was generated by hypermail 2.2.0
: Tue Feb 17 2015 - 21:17:07 CET
*