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

Support for branching constraints #124

Open spoorendonk opened 4 years ago

spoorendonk commented 4 years ago

In the default implementation DIP branches on variable bounds.

In general one may like to support GUB/SOS1 branching? For derived branching decisions one may want to add problem specific branch constraints.

Not sure how to start this. Adding a DecompConstraintSet or a DecompCut/DecompCutOsi to AlpsDecompTreeNode and then roll them on/off in

https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/AlpsDecompTreeNode.cpp#L104

tkralphs commented 4 years ago

Yeah, the way that it's done has to do with how Dip interacts with Alps. I'm not sure quite how easy this is going to be, actually, There may be some hidden gotchas in how the subproblems are created. The general mechanism is that the branching disjunction is selected in DecompAlpsTreeNode::process() by cal;ling DecompAlgo::chooseBranchSet(), then the node is marked with status AlpsNodeStatusPregnant and put back into the queue. When it's chosen again, AlpsDecompTreeNode::branch() is called to create the children with the call https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/AlpsDecompTreeNode.cpp#L504 So the first thing would probably be to modify AlpsDecompNodeDesc so that the constructor is a bit more general. At the moment, it's pretty simplistic: https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/AlpsDecompNodeDesc.h#L104-L118 After that, I guess you would need to look at where the subproblem is actually created and installed from the description and make sure that whatever information is in the description is correctly applied. That is the bulk of the work I guess. Hopefully, that's enough to get you started. Let me know if anything is unclear.