[Dip] DipPy Questions

[Ted Ralphs]

On Sun, Jul 12, 2015 at 8:09 PM, Romain Montagné <r.montagne at hotmail.fr>
wrote:

> Hello Dippy Community,
>
> I am a PhD candidate and am currently working with Dippy. I am very
> impressed by both its performances and by how user friendly it is. It is a
> pleasure!
>
> However, some points remain mysterious:
>
> 1. Concerning the *branch_method *option*:*
>
>  - Is it possible to create more than two branches at a given node?
>

At the moment, this is not possible, but it is something I would also very
much like to have. The underlying branch and bound framework is capable of
it, we just need to make some modifications to DIP itself. I'm not sure how
difficult this will be. I guess it will be of medium difficulty.

- When the doPriceCut option is on, what is the default branching strategy
> that is used?
>

It is the same branching strategy as in branch and cut. It branches on
variables in the original compact formulation. It selects the branching
variable fairly naively at the moment, using a most fractional selection
rule. Changing the branching strategy to something like pseudocost
branching or reliability branch should not be too difficult. It's also on
the TODO list.


> - If the doPriceCut option is on, is it possible to branch on the
> variables of the master problem? As these variables are automatically
> generated by Dippy and not defined by the user, how can one call them?
>

This is difficult to allow in general, since fixing a single variable in
the master to value zero means you have to disallow the generation of the
corresponding solution when solving the subproblem (I guess you are aware
of this). This could be done in certain special cases by adding constraints
to the subproblem, but this may destroy the structure and would be
difficult to do in a generic way (I guess you are aware of this, too). What
is it that you want to do exactly?


> - If the doPriceCut option is on, is it possible to branch by adding
> constraints to the subproblem instead of returning sets of variables?
>

Not at the moment. This would probably be difficult to add. If you give
details of what you want to do, we can see what's possible.


> - If the doPriceCut option is on, is it possible to add customized cuts
> for the master problem?
>

Not at the moment. This would also be pretty difficult to support. The
whole design of DIP is premised on having an original compact formulation
that corresponds to the current Dantzig-Wolfe reformiulation. Adding cuts
in the master would destroy this mapping. I have considered adding a mode
in DIP where there is no original compact formulation and the algorithm
just does standard column generation, in which case what you are asking for
(both with respect to branching and adding cuts) might be possible, but
this would probably require significant effort.


> - If the doPriceCut is on, are customized cuts added by the
> *generate_cuts* method taken into account in the subproblem?
>

No, they are added to the original compact formulation and to the
Dantzig-Wolfe reformulation, i.e., they are treated as complicating
constraints. Allowing globally valid cuts to be added to the subproblem is
a possibility. It doesn't seem like that would be terribly difficult.
Locally valid cuts for the subproblem would probably be more difficult.


> 2. Concerning the *relaxed_solver *option*: *
>
>  - In the documentation available online, examples show that the variable
> convexDual is an input parameter of the method. However, in the examples of
> the Dippy distribution, there is no such  parameter. I have found links
> on the web showing that the method was updated, and that it is no longer a
> parameter. So how do we access this variable? Is it hidden somewhere in
> redCosts?
>

Yes, the documentation is a little out of date. When solving the subproblem
to optimality, it is not really necessary for the user to know the value of
convexDual---as long as an optimal solution is returned, DIP calculates the
reduced cost and decides whether the variable should be added internally.
The user has only to return the optimal solution to the subproblem without
considering the value of convexDual. Therefore, to simplify the interface
(since most users do not know what "convexDual" means), I had deleted this
argument in version 0.9.

However, I realized that if the user wants to use a heuristic to solve the
subproblem, this is problematic. In this case, the user should probably
know what the target value of the objective is in order to know whether the
heuristic is generating useful columns or not. Therefore, in version 0.91,
I added the argument back but called it "target," which I thought would be
less confusing. Of course, if you know what "convexDual" is, it may be more
confusing :). Does this make sense? What version of Dippy are you using? If
you are using the most recent release, you should have access to this extra
argument again.


> - In the documentation available online, the example proposed is a dynamic
> programming algorithm for the subproblem, which is optimal. Does the method
> implemented in relaxed_solver have to be  optimal or can it be a
> heuristic (meaning does DipPy check whether it is optimal or not)?
>

This is something we have recently addressed. In the current release
version, the user may supply a heuristic solution but there is no way for
the user to indicate that this is the case. Before concluding there are no
columns with negative reduced costs, DIP therefore does a final check by
solving the subproblem as a generic MILP. In the trunk version, we have now
added some additional return parameters so the user can indicate the status
of the subproblem solve (whether the solution is optimal or not and in the
case that no solution is returned, whether this is because no solution of
negative reduced cost exists or it is just that the user's heuristic did
not find such a solution). This means you can use a quick heuristic until
that fails and then let DIP solve the subproblem to optimality as a generic
MIP once the heuristic fails to find a solution with negative reduced cost.
On the other hand, you can solve the subproblem to optimality yourself and
avoid DIP's internal check.


> Thank you very much for your help.
>

No problem! Please let me know how I can help.

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/20150721/72e42b39/attachment.html>