<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Nov 6, 2015 at 6:38 PM, Ted Ralphs <span dir="ltr"><<a href="mailto:ted@lehigh.edu" target="_blank">ted@lehigh.edu</a>></span> wrote:<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 dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span><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 text="#000000" bgcolor="#FFFFFF"><ol><li>The reason why
I would like to know is that my subproblems are quite large when
formulated as MILP. Therefore, at the moment I provide DIP with
dummy MILPs for the subproblems which serve the only purpose of
establishing the assignment of variables to their subproblem.
They do not make any sense, though. That is why I would like to
make sure that DIP relies on the custom <tt>solveRelaxed</tt>
method only and does not use more information from the MILP
formulation than the occurence of variables.</li></ol></div></blockquote></span><div>Hmm, that is an interesting approach. I have to admit that the possibility of doing this didn't really occur to me. I'm a little surprised it works, since in the design of Dip, we sort of assume that Dip has access to a description of the subproblem as an MILP internally. I actually had on my TODO list to think about the possibility of using Dip in a mode where that assumptions is not true. It is certainly possible when using the branch and cut algorithm (see the TSP example), but I thought it would break in the branch and price case. What you're doing makes sense, though. We could actually make it a bit less clunky by allowing the user just to specify the number of subproblems and the number of variables in each subproblem, without having to specify a formulation for each block. Internally, we could then make dummy blocks, as you have done. </div></div></div></div></blockquote><div><br></div><div>I looked at this a bit more and wanted to clarify that what I said was a bit misleading. Dip itself doesn't require an explicit formulation for the subproblem in branch and price, as long as the user provides an exact subroutine for solving the subproblem. For example, in the GAP example, no formulation for the subproblem is given:</div><div><br></div><div><a href="https://projects.coin-or.org/Dip/browser/trunk/Dip/examples/GAP/GAP_DecompApp.cpp#L224" target="_blank">https://projects.coin-or.org/Dip/browser/trunk/Dip/examples/GAP/GAP_DecompApp.cpp#L224</a><br></div><div><br></div><div>In that example, we're essentially doing the same thing internally that you're doing except that no actual dummy subproblem is created. As long as the generic MILP solver never needs to be invoked, no formulation is required. Of course, this example fails to solve correctly in branch and cut mode, since part of the formulation is missing. We would need a cut generator to generate the missing constraints in order for it to work correctly. Perhaps this should be added to the example.</div><div><br></div><div>DipPy originally did assume a complete formulation was given and this was needed before we changed the interface to allow the user to declare that the subproblem has been solved to optimality, even if no solution was found. With that change, we can now remove this assumption, but I'll have to think about how to do that. We need a way of adding variables into the blocks without actually having to create the formulation. For now, the way you're doing it should be the best approach. </div><div><br></div><div>Cheers,</div><div><br></div><div>Ted</div><div>-- <br></div></div><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>