[Dip] Issues related to Dippy source code

[Ted Ralphs]

On Fri, Nov 6, 2015 at 6:38 PM, Ted Ralphs <ted at lehigh.edu> wrote:
>
>
>>    1. 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 solveRelaxed method only and does not use more
>>    information from the MILP formulation than the occurence of variables.
>>
>> 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.
>

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:

https://projects.coin-or.org/Dip/browser/trunk/Dip/examples/GAP/GAP_DecompApp.cpp#L224

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.

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.

Cheers,

Ted
-- 
Dr. Ted Ralphs
Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/dip/attachments/20151107/ac96df3a/attachment.html>