Local branching
type: Item
instance of: scholarly article
title: Local branching
zbMATH Open document ID: 1060.90056
author: Matteo Fischetti
author: Andrea Lodi
published in: Mathematical Programming. Series A. Series B
publication date: 2004-03-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 2055172
zbMATH Keywords: mixed integer program
zbMATH Keywords: adaptive branch-and-bound
reviewed by: Hartmut Noltemeier
MaRDI profile type: Publication
full work available at URL: s10107-003-0395-5
OpenAlex ID: W4232585008
DOI: 10.1007/S10107-003-0395-5
Recommended article: CP-Based Local Branching
Recommended article: Q4724746
Recommended article: Q5284195
Recommended article: Branching processes with local dependencies
Recommended article: Local branching in a constraint programming framework
Recommended article: Local induction
Recommended article: Local Backbones
Recommended article: Local derivations
description: scientific article; zbMATH DE number 2055172