search

coin-or / Dip

DIP is a decomposition-based solver framework for mixed integer linear programs.
https://github.com/coin-or/Dip/wiki
Eclipse Public License 1.0
17 stars 7 forks source link

setting convexity constraints bounds #119

Closed spoorendonk closed 4 years ago

spoorendonk commented 4 years ago

One manual way to handle identical subproblems is to manual set the bounds of the convexity constraints.

In https://github.com/coin-or/Dip/blob/38759ed3055e69c369f00d5e0decd6c0c777b73d/Dip/src/DecompAlgo.cpp#L1045-L1055 the bounds are set to [0,1] or [1,1].

I would like functionality to change this to a user defined value. Perhaps through the modelCore. It may break the automatic changing back-and-forth between BAC and BCP, but is useful if DIP is used for column generation only with a user defined solveRelaxed method.

In https://github.com/coin-or/Dip/blob/38759ed3055e69c369f00d5e0decd6c0c777b73d/Dip/src/DecompAlgo.cpp#L3757 the bounds must be changed to relfect the upper bound on the convexity constraint, i.e., something like zDW_LB = zDW_UBPrimal + mostNegRC * convUb;

@tkralphs how does this sound, are you aware of other pitfalls in the code?

tkralphs commented 4 years ago

Interesting thought. It's fine with me to have this option, even if it breaks automatic conversion, but I have to think if making this change would break anything. My guess without much thought is that it would probably break something somewhere, but this could probably be sorted out just by trying it and seeing what happens. We could do this in a feature branch.

On the other hand, we could also just think about how much work it would be to handle identical subproblems "the right way." It's not even perfectly clear to me that handling them the way we do is that bad. It would be nice to do a controlled experiment to see if collapsing them really is a big win.

spoorendonk commented 4 years ago

My use case for doing this hacky approach is to be able to bypass an explicit formulation of the k blocks that are identical. When solving VRPs I would be able to decompose 2-index formulations into a single subproblem with convexity bounds equal to the number of routes allowed. It makes it easier to handle formulations such as the set partitioning master of VRP or the Gilmore-Gomory model for cutting stock.

In a generic setting one a can follow the approach of Vanderbeck https://hal.inria.fr/inria-00311274v1/document that aggregates identical sub-problems and the disaggregates them when needed during branching. To implement this one would need to introduces a aggregate/disaggregate functionality and additional branching rules for handling disaggregation of subproblems.

On would still need to define all variables in all block, the disaggregated variables. By just enforcing the convexity bound I can avoid that. Doing that is only valid if integrality imposed on aggregated values also implies integrality on the disaggregated ones which is not the case in general.

To sum up.

  1. Allowing the setting of convexity constraints bounds allows the user to bypass the disaggregation process. To be used with caution and not valid for general MIPs
  2. Aggregate subproblems works in general, but demands more implementation and does not allow the (lazy/well informed) user to bypass disaggregation.

As I see it both approaches have a use case. I will look into 1. then 2.

spoorendonk commented 4 years ago

I think this should be something for the user to extend at this point.

In general DIP should be able to aggregate subproblem and handle the implications it would have on branch decisions.

Closing this for now.