# GAMS Support Wiki

### Site Tools

solver:implementing_new_branching_rules

# Differences

This shows you the differences between two versions of the page.

 solver:implementing_new_branching_rules [2013/08/09 10:23]support solver:implementing_new_branching_rules [2020/05/26 12:45] (current)Frederik Fiand Both sides previous revision Previous revision 2020/05/26 12:45 Frederik Fiand 2013/08/09 10:23 support 2007/08/08 09:33 external edit 2020/05/26 12:45 Frederik Fiand 2013/08/09 10:23 support 2007/08/08 09:33 external edit Line 1: Line 1: ====== Branching on sums of binary variables ====== ====== 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 % + Q: // I have implemented a MIP-model in GAMS, which I would like to solve to proven optimality. The problem ​is degenrate and has a lot optimal ​solutions, and many solutions very close to the optimum. 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''//​ + 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)) =l= k;''​ or ''​\sum(s, delta(s)) =g= k+1;''//​ - //My question is then, how can I make a branching rule as this in GAMS,  instead of using binary branching ?? // + //My question is then, how can I introduce such a branching rule in GAMS,  instead of just 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 + You could introduce another integer variable ''​sum_delta =e= sum(s, delta(s));''​ Now you can use branching ​priorities to instruct the MIP solver ​to first branch on the ''​sum_delta''​ variable and then on the ''​delta(s)'':​ - the ''​sum_delta''​ variable and then on the ''​delta(s)'':​ + <​code>​ - delta.prior(s) = 100; + delta.prior(s) = 100; - sum_delta.prior = 1; + sum_delta.prior = 1; - mymodel.prioropt=1;​ + mymodel.prioropt=1;​ - solve mymodel min obj using mip; + 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 ​''​ + If the multiple close to optimal solutions come from symmetry, you might also want to try a more aggressive level for symmetry ​braking cuts (see e.g. cplex option ​[[https://​www.gams.com/​latest/​docs/​S_CPLEX.html#​CPLEXsymmetry|symmetry]]). Preprocessing at the node or aggressive probing might also help (see e.g. Cplex options [[https://​www.gams.com/​latest/​docs/​S_CPLEX.html#​CPLEXpreslvnd|preslvnd]] and [[https://​www.gams.com/​latest/​docs/​S_CPLEX.html#​CPLEXprobe|probe]]). - symmetry''​) to very aggressive level (3). Preprocessing at the node or aggressive probing might also help (option ''​preslvnd'' ​and ''​probe''​). +