Branching in master only variables fails in second pass

[spoorendonk]

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

Dip/Dip/src/DecompBranch.cpp

Lines 67 to 71 in b0e1f03

	if (mit != m_masterOnlyColsMap.end()) {
	// it indicates the branched variable is a master-only variable
	// we need to set the branching method to branch in the master
	m_branchingImplementation = DecompBranchInMaster;
	}

We now have a up and a down branch.

Then when entering setMasterBounds we do this for the up branch

Dip/Dip/src/DecompAlgo.cpp

Lines 2446 to 2464 in b0e1f03

	} else if (m_branchingImplementation == DecompBranchInMaster) {
	int c, coreColIndex;
	DecompConstraintSet* modelCore = m_modelCore.getModel();
	const int nIntVars = modelCore->getNumInts();
	const int* integerVars = modelCore->getIntegerVars();
	// speical treat master-only variables, add variable bounds
	// directly on the master-only variables
	if (m_param.BranchEnforceInSubProb == true &&
	m_branchingImplementation == DecompBranchInMaster) {
	for (c = 0 ; c < nIntVars; c++) {
	coreColIndex = integerVars[c];
	if (std::find (m_masterOnlyCols.begin(), m_masterOnlyCols.end(), coreColIndex)
	!= m_masterOnlyCols.end()) {
	m_masterSI->setColBounds(m_masterOnlyColsMap[coreColIndex],
	lbs[coreColIndex], ubs[coreColIndex]);
	}
	}

however at the end of the function we do

Dip/Dip/src/DecompAlgo.cpp

Lines 2523 to 2525 in b0e1f03

	if (m_param.BranchEnforceInSubProb == true) {
	m_branchingImplementation = DecompBranchInSubproblem;
	}

Next time around for the down branch on the master variable we enter

Dip/Dip/src/DecompAlgo.cpp

Line 2385 in b0e1f03

if (m_branchingImplementation == DecompBranchInSubproblem ) {

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?

Dip/Dip/src/AlpsDecompTreeNode.cpp

Lines 221 to 238 in b0e1f03

	if (decompAlgo->getAlgo() == PRICE_AND_CUT) {
	int c;
	double* lbsInf = new double[n_cols];
	double* ubsInf = new double[n_cols];
	for (c = 0; c < n_cols; c++) {
	lbsInf[c] = -decompAlgo->getInfinity();
	ubsInf[c] = decompAlgo->getInfinity();
	//printf("root c:%d lb=%g ub=%g\n",
	// c, lbs[c], ubs[c]);
	}
	decompAlgo->setMasterBounds(lbsInf, ubsInf);
	UTIL_DELARR(lbsInf);
	UTIL_DELARR(ubsInf);
	//actually, don't need to do this - these should already be set
	decompAlgo->setSubProbBounds(lbs, ubs);
	}

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]

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]

Yes @tkralphs I will make a PR soon.