An exact completely positive programming formulation for the discrete ordered median problem: an extended version
From MaRDI portal
Publication:2176282
DOI10.1007/S10898-019-00863-1zbMATH Open1442.90132arXiv1808.10625OpenAlexW2993102069MaRDI QIDQ2176282FDOQ2176282
Publication date: 4 May 2020
Published in: Journal of Global Optimization (Search for Journal in Brave)
Abstract: This paper presents a first continuous, linear, conic formulation for the Discrete Ordered Median Problem (DOMP). Starting from a binary, quadratic formulation in the original space of location and allocation variables that are common in Location Analysis (L.A.), we prove that there exists a transformation of that formulation, using the same space of variables, that allows us to cast DOMP as a continuous linear problem in the space of completely positive matrices. This is the first positive result that states equivalence between the family of continuous convex problems and some hard problems in L.A. The result is of theoretical interest because it allows us to share the tools from continuous optimization to shed new light into the difficult combinatorial structure of the class of ordered median problems.
Full work available at URL: https://arxiv.org/abs/1808.10625
Recommendations
- Exact procedures for solving the discrete ordered median problem
- A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem
- The discrete ordered median problem: Models and solution methods.
- Continuous multifacility ordered median location problems
- A fresh view on the discrete ordered median problem based on partial monotonicity
Cites Work
- Genetic algorithms for solving the discrete ordered median problem
- On the copositive representation of binary and continuous nonconvex quadratic programs
- Location Theory
- Completely positive reformulations for polynomial optimization
- On conic QPCCs, conic QCQPs and completely positive programs
- Single-allocation ordered median hub location problems
- Copositive optimization -- recent developments and applications
- The ordered capacitated facility location problem
- Handbook on semidefinite, conic and polynomial optimization
- Revisiting a game theoretic framework for the robust railway network design against intentional attacks
- A gentle, geometric introduction to copositive optimization
- Representing quadratically constrained quadratic programs as generalized copositive programs
- A flexible model and efficient solution strategies for discrete location problems
- Exact procedures for solving the discrete ordered median problem
- Revisiting several problems and algorithms in continuous location with \(\ell _\tau \) norms
- Multifacility ordered median problems on networks: A further analysis
- A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem
- Title not available (Why is that?)
- On discrete optimization with ordering
- Quadratic assignment problems
- Title not available (Why is that?)
- Distribution systems design with role dependent objectives
- A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides
- A fresh CP look at mixed-binary QPs: new formulations and relaxations
Cited In (8)
- Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem
- A fresh view on the discrete ordered median problem based on partial monotonicity
- Discretization and resolution of the \((r| X_ p)\)-medianoid problem involving quality criteria.
- A branch-and-price approach for the continuous multifacility monotone ordered median problem
- Constructing a DC decomposition for ordered median problems
- A comparative study of different formulations for the capacitated discrete ordered median problem
- A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem
- A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem
This page was built for publication: An exact completely positive programming formulation for the discrete ordered median problem: an extended version
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176282)
