[Symphony] Questions about multi-objective optimization

[Christopher Wilcox]

I just discovered this week that either our objective function or one of
our constraints must be non-linear. Luckily the number of combinations is
limited, so I have had some success with running an exhaustive set of
single-objective, non-linearly constrained, mixed-integer optimization
problems. I can then post-process these according to the second objective
function to get the Pareto-Optimal set of solutions that I am looking for.
I evaluated six solvers by developing an AMPL program and using the NEOS
server, including BonMin, Couenne, FilMINT, MINLP, lpopt, and MINOS, and
found that lpopt seems to produce correct output for the non-linear
problems I have tried. Thanks for your comments, and the Symphony software,
both have been a great help in figuring out this problem. The NEOS server
has also been very useful for exploring the different solvers.

-Chris-

On Sun, Oct 30, 2011 at 10:15 AM, Ted Ralphs <ted at lehigh.edu> wrote:

>
>
> 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 <http://coral.ie.lehigh.edu/%7Eted>
>
>


-- 
Chris Wilcox
cgwilcox at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20111030/16202073/attachment-0001.html>