User Tools

Site Tools


solver:implementing_new_branching_rules

Branching on sums of binary variables

Q: I have implemented a MIP-model in GAMS, which I would like to solve to proven optimality. The problem has a lot of degenerate optimal problems, and solutions very close to the optimum, so it is not terminating with the optimal solution, but continuing to examine nodes with a very small gap > 0.00 % I have a good idea for a branching rule, which i believe can work around the degeneracy problems. Instead of doing binary branching on fractional binary variables, I intend to branch on the sum of some variables, i.e: \sum_s \delta_s \leq k or \sum_s \delta_s \geq k+1

My question is then, how can I make a branching rule as this in GAMS, instead of using binary branching ??

Assuming your \delta_s are discrete variables (binary or integer), you could introduce another integer variable sum_delta =e= sum(s, delta(s)); Now you can use priorities to tell Cplex to first branch on the sum_delta variable and then on the delta(s):

  delta.prior(s) = 100;
  sum_delta.prior = 1;
  mymodel.prioropt=1;
  solve mymodel min obj using mip;

If your multiple close optimal solutions come from symmetry try to avoid it. You might try set symmetry cut generation (option symmetry) to very aggressive level (3). Preprocessing at the node or aggressive probing might also help (option preslvnd and probe).

solver/implementing_new_branching_rules.txt · Last modified: 2013/08/09 08:23 by support