A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem
From MaRDI portal
Publication:3386785
DOI10.1287/IJOC.2019.0915zbMATH Open1451.90085arXiv1802.03191OpenAlexW2937321088WikidataQ126398684 ScholiaQ126398684MaRDI QIDQ3386785FDOQ3386785
Authors: Samuel Deleplanque, Martine Labbé, Diego Ponce, Justo Puerto 
Publication date: 7 January 2021
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Abstract: The Discrete Ordered Median Problem (DOMP) is formulated as a set partitioning problem using an exponential number of variables. Each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding costs. We develop a column generation approach to solve the continuous relaxation of this model. Then, we apply a branch-price-and-cut algorithm to solve to optimality small to moderate size of DOMP in competitive computational time.
Full work available at URL: https://arxiv.org/abs/1802.03191
Recommendations
- A branch‐and‐price algorithm for the capacitated p‐median problem
- A branch-and-price approach for the continuous multifacility monotone ordered median problem
- A branch-and-price algorithm for solving the Hamiltonian \(p\)-median problem
- A branch-and-cut method for the obnoxious \(p\)-median problem
- A branch-and-price approach to \(p\)-median location problems
- The discrete ordered median problem: Models and solution methods.
- A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem
- A parallelized lagrangean relaxation approach for the discrete ordered median problem
- An exact completely positive programming formulation for the discrete ordered median problem: an extended version
- Exact procedures for solving the discrete ordered median problem
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Discrete location and assignment (90B80)
Cites Work
- Genetic algorithms for solving the discrete ordered median problem
- Title not available (Why is that?)
- Stabilized column generation
- A column generation approach to capacitated \(p\)-median problems
- Branching rules revisited
- Branch-and-price: Column generation for solving huge integer programs
- A Primer in Column Generation
- Title not available (Why is that?)
- Computational study of large-scale \(p\)-median problems
- A specialized branch \& bound \& cut for single-allocation ordered median hub location problems
- Single-allocation ordered median hub location problems
- A probabilistic heuristic for a computationally difficult set covering problem
- Greedy randomized adaptive search procedures
- Minimax regret single-facility ordered median location problems on networks
- Branch and price for large-scale capacitated hub location problems with single assignment
- An extended covering model for flexible discrete and equity location problems
- A flexible model and efficient solution strategies for discrete location problems
- A modified variable neighborhood search for the discrete ordered median problem
- Exact procedures for solving the discrete ordered median problem
- Finding the nucleolus of any \(n\)-person cooperative game by a single linear program
- Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
- A computational evaluation of a general branch-and-price framework for capacitated network location problems
- A comparative study of formulations and solution methods for the discrete ordered \(p\)-median problem
- A branch-and-price approach to \(p\)-median location problems
- A branch‐and‐price algorithm for the capacitated p‐median problem
- Experiments in mixed-integer linear programming
- Geometrical properties of the symmetrical single facility location problem
- On discrete optimization with ordering
- A new formulation of the capacitated discrete ordered median problems with \(\{0,1\}\)-assignment
- Title not available (Why is that?)
- Ordered weighted average combinatorial optimization: formulations and their properties
- Title not available (Why is that?)
- A branch-and-price algorithm and new test problems for spectrum auctions
- Heuristic procedures for solving the discrete ordered median problem
- A constraint-programming-based branch-and-price-and-cut approach for operating room planning and scheduling
- A revised variable neighborhood search for the discrete ordered median problem
- Ordered weighted average optimization in multiobjective spanning tree problem
- Mathematical programming formulations for the efficient solution of the \(k\)-sum approval voting problem
Cited In (14)
- Exact procedures for solving the discrete ordered median problem
- Alternative formulations for the obnoxious \(p\)-median problem
- Mixed-integer linear programming formulations and column generation algorithms for the minimum normalized cuts problem on networks
- Constraint relaxation for the discrete ordered median problem
- Segmentation of scanning-transmission electron microscopy images using the ordered median problem
- A fresh view on the discrete ordered median problem based on partial monotonicity
- Ordered \(p\)-median problems with neighbourhoods
- A branch-and-price approach for the continuous multifacility monotone ordered median problem
- A flexible model and efficient solution strategies for discrete location problems
- The discrete ordered median problem: Models and solution methods.
- A branch-and-price procedure for clustering data that are graph connected
- A comparative study of different formulations for the capacitated discrete ordered median problem
- A branch-and-price approach to \(p\)-median location problems
- Improved heuristics for solving large-scale scanning transmission electron microscopy image segmentation using the ordered median problem
Uses Software
This page was built for publication: A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386785)
