[Dip] dippy.DecompVar and dippy.Solve Options

[Ted Ralphs]

On Wed, Apr 8, 2015 at 11:35 AM, Manser, Mark <Mark.Manser at flyjazz.ca>
wrote:

>  Hello Dip/Dippy Community,
>
>
>
> 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:
>
>
>
> 1)  On pg. 15 of http://coral.ie.lehigh.edu/~ted/files/papers/RAMP12.pdf
> 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?
>

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.


> Also, why isn’t the reduced cost being returned in gap.py when the
> dippy.Solve option is:    'doPriceCut': '1'.
>
>
>
> In cutting_stock.py, the function ‘relaxed_solver’ ends by returning a
> list containing a dippy.DecompVar instance:
>
>     dv = dippy.DecompVar(var_values, rc - convexDual, 1)
>
>     return [dv]
>
>
>
> In bin_pack_decomp_func.py, the function ‘solve_subproblem’ ends by
> returning a list containing a dippy.DecompVar instance:
>
>     dv = dippy.DecompVar(var_values, rc - convexDual, waste)
>
>     return [dv]
>

Yes, these two seem to be incorrect.


> In facility_location.py, the function ‘solve_subproblem’ ends by returning
> a list containing a regular dictionary:
>
>     var_values = dict([(avars[i], 1) for i in solution])
>
>     var_values[use_vars[loc]] = 1
>
>     …
>
>     return [var_values]
>
>
>
> In gap.py, the function ‘solve_subproblem’ ends by returning a list
> containing a regular dictionary:
>
>     var_values = dict([(var[i], 1) for i in solution])
>
>     …
>
>     return [var_values]
>

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.


>
>
> 2)  I am confused about the effect of the following dippy.Solve options:
>
>
>
>     'doCut',
>

This controls whether to do branch-and-bound or branch-and-cut (see below)


>     'generateCuts',
>

This option is either old or a mistake. It doesn't seem to have any effect
in the current release.


>      'generateInitVars',
>

This option is either old or a mistake. It doesn't seem to have any effect
in the current release.


>      'doPriceCut',
>

This controls whether to do branch-and-price or branch-and-price-and-cut
(see below)


>      'CutCGL'
>

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).


> For some context, in facility_location.py the following code exists:
>
>
>
>     dippyOpts = {}
>
>     algo = 'PriceCut'
>
>     if len(sys.argv) > 1:
>
>         algo = sys.argv[1]
>
>     if algo == 'PriceCut':
>
>         dippyOpts['doPriceCut'] = '1'
>
>         dippyOpts['CutCGL'] = '1'
>
>     elif algo == 'Price':
>
>         dippyOpts['doPriceCut'] = '1'
>
>         dippyOpts['CutCGL'] = '0'
>
>     else:
>
>         dippyOpts['doCut'] = '1'
>
>
>
> Are the last 3 conditionals how one would specify
> ‘Branch-and-price-and-cut’, ‘branch-and-price’, and ‘branch-and-cut’
> respectively?
>

Yes.


>  Would setting just dippyOpts['doCut'] = '0' result in ‘Branch-and-Bound’?
>

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).
doPriceCut = 1 means branch-and-price or branch-and-price-and-cut,
depending on whether you also choose to generate CGL cuts.

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.


> 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?
>
>
>
> Also, I am unable to access the online doxygen documentation at
> http://www.coin-or.org/Doxygen/Dip/ 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.
>

I will get this fixed.

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/20150413/2ffcafea/attachment.html>