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
Next revision
Previous revision
solver:implementing_new_branching_rules [2020/05/26 12:45]
Frederik Fiand
— (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]]). ​ 
IMPRESSUM / LEGAL NOTICEPRIVACY POLICY solver/implementing_new_branching_rules.1590489929.txt.gz ยท Last modified: 2020/05/26 12:45 by Frederik Fiand