[Symphony] Question about multi-objective optimization

[Ted Ralphs]

Hi Chris,

Unfortunately, there is no convenient way to submit a multiobjective model
to SYMPHONY through NEOS. The COIN-OR MPS reader we use discards multiple
objectives, so the second objective must be set through the API directly,
i.e., you have to build a custome solver by linking to the SYMPHONY library.
I would suggest downloading SYMPHONY and installing it locally. Instructions
for doing so can be found on the SYMPHONY Wiki page. The easiest way will be
to get the source and build it yourself. Check the Examples directory in the
source distribution and have a look at the example bicriteria.c to see how
to work with bicriteria models. Feel free to ask if you have more questions.

Cheers,

Ted

On Fri, Oct 21, 2011 at 3:02 PM, Christopher Wilcox <cgwilcox at gmail.com>wrote:

> 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
>
>
> _______________________________________________
> Symphony mailing list
> Symphony at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/symphony
>
>


-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20111025/c68b90a0/attachment-0001.html>