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

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