[Symphony] Questions about multi-objective optimization

[Ted Ralphs]

On Wed, Oct 26, 2011 at 7:18 PM, Christopher Wilcox <wilcox at cs.colostate.edu
> wrote:

> I just picked up Symphony 5.4.0 and started to use the C interface.  I
> copied the milp2.c program and changed it to do multi-objective
> optimization. The code and output is attached, including the AMPL
> description I started with. The problem I coded is a variant of the
> Knapsack problem, in which we try to optimize the value of boxes put into a
> knapsack. The original problem has boxes with weights and values, and we
> try to maximize value within a weight constraint. This works fine as a
> single-objective problem in Symphony. I modified the program to add volume
> to the boxes, now I try to maximize value and weight within a volume
> constraint. When I look at the output I see three answers before the
> program fails, as follows:
>
> DATA          BOX        WEIGHT      VALUE     VOLUME
>               Green        8           4         3
>               Gray         1           1         4
>               Yellow       4          10         5
>               Orange       3           2         1
>               Blue         1           2         1
>
> CONSTRAINT: Sum of volumes < 15
> MAXIMIZE:   Sum of values
> MAXIMIZE:   Sum of weights
>
> SOLUTIONS:
>
> 3 Yellow + 3 Orange: Value = 36, Weight = 21, Volume = 15
> 15 Orange: Value = 30, Weight = 45, Volume = 15
> 1 Yellow + 11 Orange: Value = 32, Weight = 37, Volume = 15
>
> Here are my questions:
>
> 1) The above solutions only show up in the output, how do I retrieve them?
> With sym_get_col_solution()?
>

There's not a really easy way to do this through the API at the moment. The
work I was doing at the time just required evaluating the tradeoffs between
the two objectives, so I never added the method that would be needed to get
the solutions. This would not be too difficult to do, but would still take
some time and I'm not sure I could promise anything in the near future.


> 2) How many solutions should I expect?
>

This varies widely depending on the structure of the instance, the
alignment of the two objectives, and other factors. I don't think you can
make any general statements about this.


> 3) How does the weighting function sym_set_obj2_coeff affect the result?
> Is the first objective more important?
>

The algorithm gives the full efficient frontier by default, so neither
objective is considered more important. All non-dominated solutions are
produced. There are parameter settings that give partial enumerations of
the frontier if you don't want to wait for all solutions to be produced.
All the algorithms are described in the associated paper, which you can
find here:

http://coral.ie.lehigh.edu/~ted/files/papers/BICRIT2.pdf

Our server is down at the moment, though, from a power outage.


> 4) Can I write this same program in C++? Is there an example similar to
> milp2.c in C++?
>

milp2.c is in C++ :). Originally, SYMPHONY was coded in pure C and most of
the source code is still pure C, so we use the .c extension, but because we
link to other COIN libraries that are written in C++, SYMPHONY must built
with a C++ compiler and can be called from C++ without changing anything.


> 5) Why is my program crashing with a malloc error? Do I need to ask for
> more resources on the command line?


That is difficult to say. Have you run the code through valgrind? I will
try to build it and take a look. By the way, I should have pointed out that
there is an application specifically written for solving bicriteria
knapsacj problems that you might have a look at. It's in the Applications
directory and it's called MCKP. It reads files in several standard formats
and should work fine (at least it did when I was doing this work.

Cheers,

Ted
 --
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/20111030/ce7a1aef/attachment.html>