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

Branching in master only variables fails in second pass #121

Open spoorendonk opened 4 years ago

spoorendonk commented 4 years ago

I am solving a fixed charge multi commodity flow problem and need to branch on the design variables. The default branch setting is

  utilParam.Add("DECOMP", "BranchEnforceInSubProb", "1");
  utilParam.Add("DECOMP", "BranchEnforceInMaster", "0");

and I solve the subproblem with my own shortest path algorithm.

When picking a master variable the implementation changes https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompBranch.cpp#L67-L71

We now have a up and a down branch.

Then when entering setMasterBounds we do this for the up branch

https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompAlgo.cpp#L2446-L2464

however at the end of the function we do

https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompAlgo.cpp#L2523-L2525

Next time around for the down branch on the master variable we enter https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompAlgo.cpp#L2385

instead and never set the bounds correctly.

Proposal

Do not change strategy because of branching on master only variables. The strategy has something to do with enforcing integrality on subproblem variables.

Instead enforce setting the bounds always for the master only variables, i.e., move the bound setting of the master variables only out of the if-else statement in DecompAlgo::setMasterBounds and delete the change of implementation in DecompAlgo::chooseBranchSet

A check for ramping up is needed since master bounds are set to +/- inf here - not sure why? https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/AlpsDecompTreeNode.cpp#L221-L238

This can be handled with in the start of DecompAlgo::setMasterBounds by adding

bool rampUp = getNodeIndex() == 0 && m_phase == PHASE_UNKNOWN;

if(!rampUp){
   // set master only bounds
}

to check if we are ramping up and then not touch the bounds.

I am not sure there what the side effects of this approach may be?

tkralphs commented 4 years ago

This sounds like a reasonable proposal. It's strange that there was that bug there the whole time, as I thought we had pretty well tested the master-only stuff. I'm not sure if there are any implicatins to just always setting the bounds on master-only variables, bu I can't think of anything. Do you want to submit a PR?

spoorendonk commented 4 years ago

Yes @tkralphs I will make a PR soon.