User Tools

Site Tools



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

Link to this comparison view

Both sides previous revision Previous revision
solver:implementing_new_branching_rules [2021/01/28 17:38]
Atharv Bhosekar removed
— (current)
Line 1: Line 1:
-====== 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 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)) =l= k;''​ or ''​\sum(s,​ delta(s)) =g= k+1;''//​ 
-//My question is then, how can I introduce such a branching rule in GAMS,  instead of just using binary branching ?? // 
-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)'': ​ 
-delta.prior(s) = 100; 
-sum_delta.prior = 1; 
-solve mymodel min obj using mip; 
-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://​​latest/​docs/​S_CPLEX.html#​CPLEXsymmetry|symmetry]]). Preprocessing at the node or aggressive probing might also help (see e.g. Cplex options [[https://​​latest/​docs/​S_CPLEX.html#​CPLEXpreslvnd|preslvnd]] and [[https://​​latest/​docs/​S_CPLEX.html#​CPLEXprobe|probe]]). ​