<br><br><div class="gmail_quote">On Wed, Oct 26, 2011 at 7:18 PM, Christopher Wilcox <span dir="ltr"><<a href="mailto:wilcox@cs.colostate.edu">wilcox@cs.colostate.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
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:<br>
<br><span style="font-family:courier new,monospace">DATA BOX WEIGHT VALUE VOLUME</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" clear="all">
<span style="font-family:courier new,monospace"> Gray 1 1 4</span><br style="font-family:courier new,monospace" clear="all"><span style="font-family:courier new,monospace"> Yellow 4 10 5</span><br style="font-family:courier new,monospace" clear="all">
<span style="font-family:courier new,monospace"> Orange 3 2 1</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> Blue 1 2 1 </span><br style="font-family:courier new,monospace" clear="all">
<span style="font-family:courier new,monospace">
</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">CONSTRAINT: Sum of volumes < 15</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">MAXIMIZE: Sum of values</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">MAXIMIZE: Sum of weights</span><br style="font-family:courier new,monospace"><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">SOLUTIONS:</span><br style="font-family:courier new,monospace">
<br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">3 Yellow + 3 Orange: Value = 36, Weight = 21, Volume = 15</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">15 Orange: Value = 30, Weight = 45, Volume = 15</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">1 Yellow + 11 Orange: Value = 32, Weight = 37, Volume = 15</span><br style="font-family:courier new,monospace"><br style="font-family:courier new,monospace">Here are my questions:<br>
<br>1) The above solutions only show up in the output, how do I retrieve them? With sym_get_col_solution()?<br></blockquote><div><br></div><div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">2) How many solutions should I expect?<br></blockquote><div><br></div><div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">3) How does the weighting function sym_set_obj2_coeff affect the result? Is the first objective more important?<br>
</blockquote><div><br></div><div>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:</div>
<div><br></div><div><a href="http://coral.ie.lehigh.edu/~ted/files/papers/BICRIT2.pdf">http://coral.ie.lehigh.edu/~ted/files/papers/BICRIT2.pdf</a></div><div><br></div><div>Our server is down at the moment, though, from a power outage.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
4) Can I write this same program in C++? Is there an example similar to milp2.c in C++?<br></blockquote><div><br></div><div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">5) Why is my program crashing with a malloc error? Do I need to ask for more resources on the command line?</blockquote>
<div><br></div><div>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.</div>
<div><br></div><div>Cheers,</div><div><br></div><div>Ted</div><div> -- </div></div>Dr. Ted Ralphs<br>Associate Professor, Lehigh University<br>(610) 628-1280<br>ted 'at' lehigh 'dot' edu<br><a href="http://coral.ie.lehigh.edu/~ted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
<br>