<div dir="ltr">Sure that can happen. It just means that the PC relaxation is too weak and that is a bad way to solve the problem. Is that with the KP oracle or the AP oracle? I would expect the bound using the KP oracle to be strong.<div><br></div><div>If you get 1693 with doDirect or doCut but 1698 with CBC, then either (a) there is a bug, or (b) you are not creating the same model.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jun 12, 2019 at 4:14 PM Florian Fontan <<a href="mailto:dev@florian-fontan.fr">dev@florian-fontan.fr</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF">
<p>Indeed! I didn't think to look there.</p>
<p>I managed to compile the GAP example. I tested on instance
a05100. This instance is solved optimally by a naive
implementation in CBC in 0.005s. The optimal value is 1698 which
is actually also the upper bound from the linear relaxation. When
I try the GAP implementation given as example in Dip on this
instance (./decomp_gap --param gap.parm)</p>
<ul>
<li>with doPriceCut = 1, doCut = 0, doDirect = 0: the lower bound
found is 1556, no feasible solution is found and the algorithm
doesn't terminate after at least several minutes</li>
<li>with doPriceCut = 0, doCut = 1, doDirect = 0 or doDirect = 1:
the algorithm terminates very quickly, returning a best lower
bound and a best upper bound of 1693. I think it may be the
solution of the problem with the capacity constraints removed.</li>
</ul>
<p>Is this the expected behavior?</p>
<p>Florian<br>
</p>
<div class="gmail-m_-6113883389000557119moz-cite-prefix">Le 11/06/2019 à 22:34, Matthew Galati a
écrit :<br>
</div>
<blockquote type="cite">
<div dir="ltr">The Makefile gives some hints... one case using the
built-in MILP solver, one case uses a KP solver.
<div><br>
</div>
<div>
<table class="gmail-m_-6113883389000557119gmail-highlight gmail-m_-6113883389000557119gmail-tab-size gmail-m_-6113883389000557119gmail-js-file-line-container">
<tbody style="box-sizing:border-box">
<tr style="box-sizing:border-box">
<td id="gmail-m_-6113883389000557119gmail-LC25" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap">
<table class="gmail-m_-6113883389000557119gmail-highlight gmail-m_-6113883389000557119gmail-tab-size gmail-m_-6113883389000557119gmail-js-file-line-container" style="box-sizing:border-box;border-collapse:collapse;border-spacing:0px;font-family:-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";font-size:14px;white-space:normal"><tbody style="box-sizing:border-box"><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L25" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC25" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span>PC: oracle for KP solve is Pisinger, BranchEnforceInMaster</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L26" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC26" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-smi" style="box-sizing:border-box">OBJS</span> += GAP_DecompApp.@OBJEXT@</td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L27" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC27" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-smi" style="box-sizing:border-box">CFLAGS</span> = -DVERSION1</td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L28" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC28" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap">
</td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L29" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC29" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span>TODO: BranchEnforceInSubProb using GAP_DecompApp2 or by option</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L30" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC30" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap">
</td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L31" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC31" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span> CPM/PC: built-in MILP solver, dense model build</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L32" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC32" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span> BranchEnforceInMaster or BranchEnforceInSubProb by option</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L33" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC33" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span>OBJS += GAP_DecompApp3.@OBJEXT@</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L34" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC34" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span>CFLAGS += -DVERSION3</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L35" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC35" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap">
</td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L36" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC36" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span> CPM/PC: built-in MILP solver, sparse model build</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L37" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC37" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span> BranchEnforceInMaster or BranchEnforceInSubProb by option</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L38" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC38" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span>OBJS += GAP_DecompApp4.@OBJEXT@</span></td></tr><tr style="box-sizing:border-box"><td id="gmail-m_-6113883389000557119gmail-L39" class="gmail-m_-6113883389000557119gmail-blob-num gmail-m_-6113883389000557119gmail-js-line-number" style="box-sizing:border-box;padding:0px 10px;color:rgba(27,31,35,0.3);font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;line-height:20px;min-width:50px;text-align:right;vertical-align:top;white-space:nowrap;width:50px">
</td><td id="gmail-m_-6113883389000557119gmail-LC39" class="gmail-m_-6113883389000557119gmail-blob-code gmail-m_-6113883389000557119gmail-blob-code-inner gmail-m_-6113883389000557119gmail-js-file-line" style="box-sizing:border-box;padding:0px 10px;line-height:20px;vertical-align:top;font-family:SFMono-Regular,Consolas,"Liberation Mono",Menlo,Courier,monospace;font-size:12px;overflow:visible;white-space:pre-wrap"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box;color:rgb(106,115,125)"><span class="gmail-m_-6113883389000557119gmail-pl-c" style="box-sizing:border-box">#</span>CFLAGS += -DVERSION4</span></td></tr></tbody></table>
</td>
</tr>
</tbody>
</table>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Tue, Jun 11, 2019 at 3:41
PM Florian Fontan <<a href="mailto:dev@florian-fontan.fr" target="_blank">dev@florian-fontan.fr</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Dear
Dip community,<br>
<br>
I am trying to get familiar with Dip and understand how it
works. Could <br>
someone tell me the differences between the multiple DecompApp
<br>
implementation examples for the Generalized Assignment
Problem?<br>
<a href="https://github.com/coin-or/Dip/tree/master/Dip/examples/GAP" rel="noreferrer" target="_blank">https://github.com/coin-or/Dip/tree/master/Dip/examples/GAP</a><br>
<br>
For example, in GAP_DecompApp.cpp, I noticed that the
setModelRelax call <br>
passes NULL as first argument:<br>
<br>
setModelRelax(NULL, modelName, i);<br>
<br>
whereas in GAP_DecompApp3.cpp, an other model is defined:<br>
<br>
status = createModelPartKP(modelRelax, i);<br>
modelName = "KP" + UtilIntToStr(i);<br>
setModelRelax(modelRelax, modelName, i);<br>
<br>
What does that mean? I haven't found any documentation about
it<br>
<br>
Florian<br>
_______________________________________________<br>
Dip mailing list<br>
<a href="mailto:Dip@list.coin-or.org" target="_blank">Dip@list.coin-or.org</a><br>
<a href="https://list.coin-or.org/mailman/listinfo/dip" rel="noreferrer" target="_blank">https://list.coin-or.org/mailman/listinfo/dip</a><br>
</blockquote>
</div>
</blockquote>
</div>
</blockquote></div>