<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Apr 8, 2015 at 11:35 AM, Manser, Mark <span dir="ltr"><<a href="mailto:Mark.Manser@flyjazz.ca" target="_blank">Mark.Manser@flyjazz.ca</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div lang="EN-CA" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">Hello Dip/Dippy Community,<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">I am new to implementing decomposition algorithms and Dip/Dippy and am trying to figure out how the platform works. I have a couple
of general questions:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">1) On pg. 15 of <a href="http://coral.ie.lehigh.edu/~ted/files/papers/RAMP12.pdf" target="_blank">http://coral.ie.lehigh.edu/~ted/files/papers/RAMP12.pdf</a> it states “The return value of relaxed solver is a list of
DecompVar objects having negative reduced cost.” This appears to be the case for the cutting_stock.py and bin_pack_decomp_func.py for example, but not the case for facility_location.py nor gap.py. When is it necessary to return a list of dippy.DecompVar
instances, and when does it suffice to return a regular sparse dictionary of variables? </span></p></div></div></blockquote><div><br></div><div>Sorry about the confusion. There have been some minor adjustment to the API of relaxed_solver over time and the paper is no longer correct on this point. But it looks like we never updated some of the examples. I'm a little baffled by how out of date some of the examples are, since I thought I had run them all fairly recently. Sorry about that! The facility_location.py and gap.py examples are the ones that are correct. You now only have to returns a sparse dictionary of variables. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><div><p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">Also, why isn’t the reduced cost being returned in gap.py when the dippy.Solve option is: 'doPriceCut': '1'.<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">In cutting_stock.py, the function ‘relaxed_solver’ ends by returning a list containing a dippy.DecompVar instance:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> dv = dippy.DecompVar(var_values, rc - convexDual, 1)<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> return [dv]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">In bin_pack_decomp_func.py, the function ‘solve_subproblem’ ends by returning a list containing a dippy.DecompVar instance:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> dv = dippy.DecompVar(var_values, rc - convexDual, waste)<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> return [dv]</span></p></div></div></blockquote><div><br></div><div>Yes, these two seem to be incorrect. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><div>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">In facility_location.py, the function ‘solve_subproblem’ ends by returning a list containing a regular dictionary:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> var_values = dict([(avars[i], 1) for i in solution])<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> var_values[use_vars[loc]] = 1<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> …<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> return [var_values]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">In gap.py, the function ‘solve_subproblem’ ends by returning a list containing a regular dictionary:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> var_values = dict([(var[i], 1) for i in solution])<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> …<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> return [var_values]</span></p></div></div></blockquote><div><br></div><div>Those are correct for the current release version. Note that in trunk, we have enabled some additional functionality which will require another change to the API sometime in the future.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><div><p class="MsoNormal"><span style="font-family:Arial,sans-serif;font-size:10pt"> </span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">2) I am confused about the effect of the following dippy.Solve options:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> 'doCut',</span></p></div></div></blockquote><div><br></div><div>This controls whether to do branch-and-bound or branch-and-cut (see below)<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><div><p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> 'generateCuts',</span></p></div></div></blockquote><div><br></div><div>This option is either old or a mistake. It doesn't seem to have any effect in the current release.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><div><p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> 'generateInitVars',</span></p></div></div></blockquote><div><br></div><div>This option is either old or a mistake. It doesn't seem to have any effect in the current release.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> 'doPriceCut',</span></p></div></blockquote><div><br></div><div><div>This controls whether to do branch-and-price or branch-and-price-and-cut (see below)<br></div></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> 'CutCGL'</span></p></div></blockquote><div><br></div><div>This option controls whether to generate generic MILP cuts. It is off by default with branch-and-price (but sometimes helps a lot---it's off because this is not the usual version of branch-and-price people are used to. Perhaps it should be on by default).</div><div> <span style="font-family:Arial,sans-serif;font-size:10pt"> </span></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple">
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">For some context, in facility_location.py the following code exists:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> dippyOpts = {}<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> algo = 'PriceCut'<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> if len(sys.argv) > 1:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> algo = sys.argv[1]<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> if algo == 'PriceCut':<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> dippyOpts['doPriceCut'] = '1'<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> dippyOpts['CutCGL'] = '1'<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> elif algo == 'Price':<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> dippyOpts['doPriceCut'] = '1'<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> dippyOpts['CutCGL'] = '0'<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> else:<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"> dippyOpts['doCut'] = '1'<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">Are the last 3 conditionals how one would specify ‘Branch-and-price-and-cut’, ‘branch-and-price’, and ‘branch-and-cut’ respectively?</span></p></div></blockquote><div><br></div><div>Yes.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><div><p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">Would setting just dippyOpts['doCut'] = '0' result in ‘Branch-and-Bound’?</span></p></div></div></blockquote><div><br></div><div>doCut = 1 means branch-and-bound or branch-and-cut, depending on whether you also choose to generate CGL cuts (they are generated by default). </div><div>doPriceCut = 1 means branch-and-price or branch-and-price-and-cut, depending on whether you also choose to generate CGL cuts.</div><div><br></div><div>In Dippy, you must set exactly one of these to 1 to specify which base algorithm you want. So setting doCut = 0 doesn't give you branch and bound, it just means you are going to do branch-and-price (and need to set doPriceCut = 1). In DIP itself, it is possible to run both algorithms in parallel so you could in theory have both options set to 1. You can also just call the underlying IP solver directly on the compact formulation, which means both these parameters could also be zero. You can even run the underlying IP solver, DIP cutting plane method and multiple instances of Price and Cut with different decompositions if you want with DIP. We have not enabled this functionality with Dippy yet.</div><div> <span style="font-family:Arial,sans-serif;font-size:10pt"> </span></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div lang="EN-CA" link="blue" vlink="purple"><div>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">3) I have a model built for a real-world application, but it’s not behaving the way I expected it would. There are potentially a number
of things wrong and I would like to discuss it with someone knowledgeable. If one of the devs has time for a quick review, could you reply to this message?<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif"><u></u> <u></u></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10pt;font-family:Arial,sans-serif">Also, I am unable to access the online doxygen documentation at <a href="http://www.coin-or.org/Doxygen/Dip/" target="_blank">http://www.coin-or.org/Doxygen/Dip/</a> as listed on the github page. I
am receiving “403 Forbidden You don't have permission to access /Doxygen/Dip/ on this server.” I am not sure if this is on my end or if it’s affecting everyone.</span></p></div></div></blockquote><div><br></div><div>I will get this fixed.</div><div><br></div><div>Cheers,</div><div><br></div><div>Ted </div></div><div><br></div>-- <br><div><div dir="ltr">Dr. Ted Ralphs<br>Professor, Lehigh University<br><a href="tel:%28610%29%20628-1280" value="+16106281280" target="_blank">(610) 628-1280</a><br>ted 'at' lehigh 'dot' edu<br><a href="http://coral.ie.lehigh.edu/~ted" target="_blank">coral.ie.lehigh.edu/~ted</a><br></div></div>
</div></div>