Local branching (Q1424277)

The paper offers another complete branching scheme to solve Mixed-Integer-Programs (MIP). The main idea is to favor early updates of the incumbent solution, producing improved solutions in early stages of the computation. This is intended by adding linear soft fixing constraints: linear inequalities, by which the relative number \(r\) of flipping (binary restricted) variables is constrained (with respect to a given solution \(\overline x\)), f.e. \[ \sum\overline x_j x_j\geq r \sum\overline x_j\qquad (0< r< 1). \] More general local branching constraints like \[ d(x,\overline x):= \sum_{j\in\overline S}(1- x_j)+ \sum_{j\in B-\overline S} x_j\leq k \] are used, where the two terms count the number of flipping variables (with respect to \(\overline x\)). \(k\) is choosen (and evtly. changed adaptively) within the branching process with disjunction \(d(x,\overline x)\leq k\) or \(d(x,\overline x)\geq k+ 1\), such that the ``left'' branch \(d(x,\overline x)\leq k\) should be examined rather fast. Enhancing this general scheme on left branching nodes by imposing time limits or diversification techniques like variable neighborhood search is additionally illustrated. Computational results on a wide range of instances of different (MIP-) applications are summarized. Analysing the convergence behaviour is left to future research as well as some possible extensions.