Optimization Online


A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method

Jordi Castro(jordi.castro***at***upc.edu)
Stefano Nasini(snasini***at***iese.edu)
Francisco Saldanha-da-Gama(faconceicao***at***fc.ul.pt)

Abstract: We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either exact or inexact) efficient solution of large instances. The effect of different modeling conditions and problem specifications on the computational performance are also investigated both theoretically and empirically, providing a deeper understanding of the significant factors influencing the overall efficiency of the cutting-plane method. This approach allowed the solution of instances of up to 200 potential locations, one million customers and three periods, resulting in mixed integer linear optimization problems of up to 600 binary and 600 millions of continuous variables. Those problems were solved by the specialized approach in less than one hour, outperforming other state-of-the-art methods, which exhausted the (144 Gigabytes of) available memory in the largest instances.

Keywords: mixed integer linear optimization; interior-point methods; multi-period facility location; cutting planes; Benders decomposition; large-scale optimization

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: J. Castro, S. Nasini, F. Saldanha-da-Gama. A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method. Research Report DR2015-01, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, Barcelona, 2015.

Download: [PDF]

Entry Submitted: 06/10/2015
Entry Accepted: 06/10/2015
Entry Last Modified: 06/10/2015

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