Generalized local branching heuristics and the capacitated ring tree problem

Alessandro Hill and Stefan VOß

Working Papers from University of Antwerp, Faculty of Business and Economics

Abstract: In this paper we present a heuristic framework that is based on mathematical programming to solve network design problems. Our techniques combine local branching with locally exact refinements. In an iterative strategy an existing solution is refined by solving restricted mixed integer programs (MIPs) to optimality. These are obtained from the master problem MIP by (1) fixing a subset of binary variables and (2) limiting the number of variable flips among the unfixed variables. We introduce generalized local branching cuts which enforce (1) and (2). Using these concepts we develop an efficient algorithm for the capacitated ring tree problem (CRTP), a recent network design model for reliable capacitated networks that combines cycle and tree structures. Our implementation operates on top of an efficient branch & cut algorithm for the CRTP. The sets of refinement variables are deduced from single and multi-ball CRTP-tailored network node clusters. We provide computational results using a set of literature instances. We show that the approach is capable of improving existing best results for the CRTP when integrated into a multi-start local search heuristic, but is also efficient when used independently.

Keywords: Capacitated ring tree problem; Local branching; Mathematical programming; Local search; Network design; Matheuristic (search for similar items in EconPapers)
Pages: 18 pages
Date: 2014-09
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repository.uantwerpen.be/docman/irua/e2cabc/145281.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ant:wpaper:2014020

Access Statistics for this paper

More papers in Working Papers from University of Antwerp, Faculty of Business and Economics Contact information at EDIRC.
Bibliographic data for series maintained by Joeri Nys ().