Heuristics for a continuous multi-facility location problem with demand regions

Date

2015-10

Author

Dinler, Derya
Tural, Mustafa Kemal
İyigün, Cem

Metadata

Show full item record

Item Usage Stats

122
views

0
downloads

We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.

Subject Keywords

Facility location problems, Second order cone programming, Minimum sum of squares clustering, Hyperbolic smoothing

URI

https://hdl.handle.net/11511/28541

Journal

Computers & Operations Research

DOI

https://doi.org/10.1016/j.cor.2014.09.001

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Continuous optimization approaches for clustering via minimum sum of squares Akteke-Ozturk, Basak; Weber, Gerhard Wilhelm; Kropat, Erik (2008-05-23) In this paper, we survey the usage of semidefinite programming (SDP), and nonsmooth optimization approaches for solving the minimum sum of squares problem which is of fundamental importance in clustering. We point out that the main clustering idea of support vector clustering (SVC) method could be interpreted as a minimum sum of squares problem and explain the derivation of semidefinite programming and a nonsmooth optimization formulation for the minimum sum of squares problem. We compare the numerical resu...
A two-level iterative scheme for general sparse linear systems based on approximate skew-symmetrizers Mehrmann, Volker; Manguoğlu, Murat (2021-01-01) We propose a two-level iterative scheme for solving general sparse linear systems. The proposed scheme consists of a sparse preconditioner that increases the norm of the skew-symmetric part relative to the rest and makes the main diagonal of the coefficient matrix as close to the identity as possible so that the preconditioned system is as close to a shifted skew-symmetric matrix as possible. The preconditioned system is then solved via a particular Minimal Residual Method for Shifted Skew-Symmetric Systems...
Basis reduction and the complexity of branch-and-bound Pataki, Gábor; Tural, Mustafa Kemal; Wong, Erick B. (2010-05-06) The classical branch-and-bound algorithm for the integer feasibility problem [GRAPHICS] has exponential worst case complexity. We prove that, it. is surprisingly efficient on reformulations of (01), in which the columns of the constraint, matrix are short and near orthogonal, i e, a reduced basis of the generated lattice. when the entries of A ale from {1, ,M} for a large enough M, branch-and-bound solves almost all reformulated instances at the root. node For all A matrices we prove an upper bound on th...
A visual interactive approach for scenario-based stochastic multi-objective problems and an application Balibek, E.; Köksalan, Mustafa Murat (2012-12-01) In many practical applications of stochastic programming, discretization of continuous random variables in the form of a scenario tree is required. In this paper, we deal with the randomness in scenario generation and present a visual interactive method for scenario-based stochastic multi-objective problems. The method relies on multi-variate statistical analysis of solutions obtained from a multi-objective stochastic problem to construct joint confidence regions for the objective function values. The decis...
Optimising a nonlinear utility function in multi-objective integer programming Ozlen, Melih; Azizoğlu, Meral; Burton, Benjamin A. (2013-05-01) In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective i...

Citation Formats

D. Dinler, M. K. Tural, and C. İyigün, “Heuristics for a continuous multi-facility location problem with demand regions,” Computers & Operations Research, pp. 237–256, 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/28541.