Optimization Online


Integrating cut-and-solve and semi-Lagrangean based dual ascent for the single-source capacitated facility location problem

S.L. Gadegaard(sgadegaard***at***econ.au.dk)

Abstract: This paper describes how the cut-and-solve framework and semi-Lagrangean based dual ascent algorithms can be integrated in two natural ways in order to solve the single source capacitated facility location problem. The first uses the cut-and-solve framework both as a heuristic and as an exact solver for the semi-Lagrangean subproblems. The other uses a semi-Lagrangean based dual ascent algorithm to solve the sparse problems arising in the cut-and-solve algorithm. Furthermore, we developed a simple way to separate a special type of cutting planes from what we denote the effective capacity polytope with generalized upper bounds. From our computational study, we show that the semi-Lagrangean relaxation approach has its merits when the instances are tightly constrained with regards to the capacity of the system, but that it is very hard to compete with a standalone implementation of the cut-and-solve algorithm. We were, however, able to increase the size of the instances solvable by almost 25 percent compared to methodologies proposed in the literature.

Keywords: capacitated location problem; single source; semi-Lagrangean; cut-and-solve; dual ascent

Category 1: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 04/22/2016
Entry Accepted: 04/22/2016
Entry Last Modified: 04/22/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society