I am working on an optimization problem that requires multi-objective optimization. In order to understand multi-objective optimization I have built an example using the Knapsack problem. I have been working by writing the problem using AMPL, which I run on the Minos solver. After I have things basically working I use the 'ampl' tool to generate an MPS file that can be submitted to Symphony using the NEOS server. Sometimes I have to change the signs of values in the MPS file to maximize, since otherwise Symphony defaults to minimize. Here is a simple example of an unsuccessful attempt to do multi-objective optimization. Any comments on how to better specify the program would be helpful:<br>
<br>PROBLEM DESCRIPTION<br><br>I start with the generic Knapsack problem at <a href="http://en.wikipedia.org/wiki/Knapsack_problem">http://en.wikipedia.org/wiki/Knapsack_problem</a>. In this we have a set of boxes, each of which has a value and weight. The problem is to maximize the value of the boxes put in the Knapsack, while staying within a weight constraint. I code this in AMPL and translate to MPS, then run on Symphony and everything works as expected. To test multi-objective optimization I add a parameter volume to each box, remove the weight constraint, and add a volume constraint. I continue to try and maximize value but add another objective function to minimize weight. The second objective function seems to be ignored by both of the solvers I have tried. The problem specification and results are shown below.<br>
<br>AMPL DATA:<br><br><span style="font-family: courier new,monospace;">param: BOXES: Weight Value Volume Minimum Maximum :=</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> "GREEN" 8 4 3 . .</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> "GRAY" 1 2 5 . .</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> "YELLOW" 4 10 4 . .</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> "BLUE" 3 2 1 . . </span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> "ORANGE" 1 2 1 . .;</span><br style="font-family: courier new,monospace;">
<br>AMPL MODEL:<br><br><span style="font-family: courier new,monospace;"># external data</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">set BOXES ordered;</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"># define bounds</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">param Weight {BOXES} >= 0;</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">param Value {BOXES} >= 0;</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">param Volume {BOXES} >= 0;</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">param Minimum {BOXES} >= 0, default 0;</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">param Maximum {i in BOXES} >= Minimum[i], default Infinity;</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"># variables</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">var Select {i in BOXES} integer >= Minimum[i], <= Maximum[i];</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"># objective functions</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">maximize TotalValue: sum {i in BOXES} Value[i] * Select[i];</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">minimize TotalWeight: sum {i in BOXES} Weight[i] * Select[i];</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"># constraints</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">subject to TotalVolume: 0 <= sum {i in BOXES} Volume[i] * Select[i] <= 15;</span><br style="font-family: courier new,monospace;"><br>AMPL COMMANDS:<br><br><span style="font-family: courier new,monospace;">model Biobjective.mod;</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">data Biobjective.dat;</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">solve;</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">display Select;</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">display TotalValue;</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">display TotalWeight;</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">display TotalVolume.body;</span><br style="font-family: courier new,monospace;">
<br>MPS FORMAT:<br><br>File is attached, note that I have changed the values for each box to negative so that value is minimized instead of maximized. Negating the weights doesn't make a difference.<br><br>RESULTS:<br>
<br>For both of the solvers, I receive an answer of 3 yellow boxes and 3 blue boxes. This adds up to a total volume of 15, which exactly meets the constraint, and a total value of 36, which I believe is optimal. The solver computes a total weight of 21 whether I use maximize or minimize for the TotalWeight objective function. In the latter case I would expect an answer of 3 yellow boxes and 3 orange boxes, with the same volume and value, but a total weight of 15. My conclusion is that the second objective function is being ignored. Is there some way to enable processing of both objective functions? If so, how is the relative importance of both functions evaluated? In this case I have setup the problem so that there are two optimal answers to the first objective function, one of which minimizes and the other that maximizes the second objective function, but of course this may not always be the case.<br>
<br>Here is the output of the Symphony solver:<br><br>...<br>Solution Found: Node 0, Level 0<br>
Solution Cost: -36.000<br>
++++++++++++++++++++++++++++++<div id=":1qv">+++++++++++++++++++++<br>
Column names and values of nonzeros in the solution<br>
+++++++++++++++++++++++++++++++++++++++++++++++++++<br>
C0003 3.000<br>
C0004 3.000<br>...<br><br>And the Minos solver, just for comparison:<br><br><span style="font-family: courier new,monospace;">MINOS 5.51: ignoring integrality of 5 variables</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">MINOS 5.51: optimal solution found.</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">2 iterations, objective 36</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">Objective = TotalValue</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">Select [*] :=</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"> GREEN 0</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> GRAY 0</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">YELLOW 3</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"> BLUE 3</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">ORANGE 0</span><span style="font-family: courier new,monospace;">;</span><br style="font-family: courier new,monospace;"><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">TotalValue = 36</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">TotalWeight = 21</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">TotalVolume.body = 15</span><br></div><br>My real problem is similar to this example, except that I have more constraints and one of the objective functions requires a much more complicated equation.<br clear="all">
<br>-- <br>Chris Wilcox<br><a href="mailto:cgwilcox@gmail.com">cgwilcox@gmail.com</a><br><br>