solver:implementing_new_branching_rules

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

Both sides previous revision Previous revision | |||

solver:implementing_new_branching_rules [2013/08/09 10:23] support |
solver:implementing_new_branching_rules [2020/05/26 12:45] (current) Frederik Fiand |
||
---|---|---|---|

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; |

+ | </code> | ||

- | 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''). | + |

IMPRESSUM / LEGAL NOTICE
PRIVACY POLICY
solver/implementing_new_branching_rules.txt · Last modified: 2020/05/26 12:45 by Frederik Fiand