Upper bounds and exact algorithms for \(p\)-dispersion problems

DOI10.1016/j.cor.2004.09.033zbMath1092.90027OpenAlexW2064370739WikidataQ58826447 ScholiaQ58826447MaRDI QIDQ2496032

David Pisinger

Publication date: 30 June 2006

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2004.09.033

zbMATH Keywords

upper boundsbranch-and-boundlocational analysis

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Continuous location (90B85)

Related Items (26)

Effective methods for solving the bi-criteria \(p\)-center and \(p\)-dispersion problem ⋮ On the unified dispersion problem: efficient formulations and exact algorithms ⋮ An integer programming approach for solving the \(p\)-dispersion problem ⋮ \(p\)-median and \(p\)-dispersion problems: a bi-criteria analysis ⋮ Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster ⋮ On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study ⋮ A general heuristic for vehicle routing problems ⋮ Subset selection from large datasets for kriging modeling ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ Variable neighborhood search for large offshore wind farm layout optimization ⋮ A review on discrete diversity and dispersion maximization from an OR perspective ⋮ An exact cutting plane method for the Euclidean max-sum diversity problem ⋮ On linearization techniques for budget-constrained binary quadratic programming problems ⋮ \(t\)-linearization for the maximum diversity problem ⋮ Constrained 0-1 quadratic programming: basic approaches and extensions ⋮ Heuristic solution approaches for the maximum minsum dispersion problem ⋮ A new compact formulation for the discrete \(p\)-dispersion problem ⋮ Transmitter location for maximum coverage and constructive-destructive interference management ⋮ Measuring diversity. A review and an empirical analysis ⋮ Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem ⋮ Construction and improvement algorithms for dispersion problems ⋮ Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem ⋮ The conditional \(p\)-dispersion problem ⋮ The equitable dispersion problem ⋮ Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method ⋮ The Location of Undesirable Facilities

Uses Software

• Knapsack
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Good solutions to discrete noxious location problems via metaheuristics
• Discrete location problems with push-pull objectives
• The discrete p-dispersion problem
• Clustering and domination in perfect graphs
• An exact algorithm for large multiple knapsack problems
• Linear programming for the \(0-1\) quadratic knapsack problem
• Lagrangean methods for the 0-1 quadratic knapsack problem
• A lower bound for a constrained quadratic \(0\)-\(1\) minimization problem
• Approximation algorithms for maximum dispersion
• A semidefinite programming approach to the quadratic knapsack problem
• Complexity of finding dense subgraphs
• A new upper bound for the 0-1 quadratic knapsack problem
• Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Quadratic knapsack problems
• Heuristic and Special Case Algorithms for Dispersion Problems
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
• Exact Solution of the Quadratic Knapsack Problem
• Quadratic knapsack relaxations using cutting planes and semidefinite programming
• Greedily Finding a Dense Subgraph
• The traveling-salesman problem and minimum spanning trees: Part II

This page was built for publication: Upper bounds and exact algorithms for \(p\)-dispersion problems