[Symphony] Question about multi-objective optimization

[Christopher Wilcox]

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:

PROBLEM DESCRIPTION

I start with the generic Knapsack problem at
http://en.wikipedia.org/wiki/Knapsack_problem. 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.

AMPL DATA:

param:  BOXES:    Weight   Value   Volume   Minimum   Maximum :=
       "GREEN"          8       4       3        .         .
       "GRAY"           1       2       5        .         .
       "YELLOW"         4      10       4        .         .
       "BLUE"           3       2       1        .         .
       "ORANGE"         1       2       1        .         .;

AMPL MODEL:

# external data
set BOXES ordered;

# define bounds
param Weight  {BOXES} >= 0;
param Value   {BOXES} >= 0;
param Volume  {BOXES} >= 0;
param Minimum {BOXES} >= 0,               default 0;
param Maximum {i in BOXES} >= Minimum[i], default Infinity;

# variables
var Select {i in BOXES} integer >= Minimum[i], <= Maximum[i];

# objective functions
maximize TotalValue:  sum {i in BOXES} Value[i]  * Select[i];
minimize TotalWeight: sum {i in BOXES} Weight[i] * Select[i];

# constraints
subject to TotalVolume: 0 <= sum {i in BOXES} Volume[i] * Select[i] <= 15;

AMPL COMMANDS:

model Biobjective.mod;
data  Biobjective.dat;
solve;
display Select;
display TotalValue;
display TotalWeight;
display TotalVolume.body;

MPS FORMAT:

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.

RESULTS:

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.

Here is the output of the Symphony solver:

...
Solution Found: Node 0, Level 0
Solution Cost: -36.000
++++++++++++++++++++++++++++++
+++++++++++++++++++++
Column names and values of nonzeros in the solution
+++++++++++++++++++++++++++++++++++++++++++++++++++
  C0003      3.000
  C0004      3.000
...

And the Minos solver, just for comparison:

MINOS 5.51: ignoring integrality of 5 variables
MINOS 5.51: optimal solution found.
2 iterations, objective 36
Objective = TotalValue
Select [*] :=
 GREEN  0
  GRAY  0
YELLOW  3
  BLUE  3
ORANGE  0;

TotalValue = 36
TotalWeight = 21
TotalVolume.body = 15

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.

-- 
Chris Wilcox
cgwilcox at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20111021/a6704b25/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Biobjective.mps
Type: application/octet-stream
Size: 734 bytes
Desc: not available
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20111021/a6704b25/attachment.obj>