On a linearization technique for solving the quadratic set covering problem and variations

DOI10.1007/S11590-016-1081-XMaRDI QIDQ1676486zbMATH OpenOpenAlexFDO

Authors Pooja Pandey, Abraham P. Punnen

Publication date 9 November 2017

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.06305

zbMATH Keywords

0-1 programmingagorithmsheuristicquadratic programmingset covering problem

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: In this paper we identify some inaccuracies in the paper by R.R. Saxena and S.R. Arora, A Linearization technique for solving the Quadratic Set Covering Problem, Optimization, 39 (1997) 33-42. In particular, we observe that their algorithm need not guarantee optimality, contrary to what is claimed. Experimental analysis with the algorithm has been carried out to evaluate its merit as a heuristic and compared with CPLEX. The results disclose that for some class of problems the algorithm is reasonably effective while for some other class, it's performance is very poor. we also discussion similar inaccuracies in another related paper.

Recommendations

• A Linearization technique for solving the quadratic set covering problem
• Approximation of the quadratic set covering problem
• An algorithm for set covering problem
• Linearization approach to multi-objective quadratic set covering problem
• The set covering problem: Complexity, algorithms, experiments

Cites work

• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• A Cutting-Plane Algorithm for the Quadratic Set-Covering Problem
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• A Linearization technique for solving the quadratic set covering problem
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• Approximation of the quadratic set covering problem
• Compact linearization for binary quadratic problems
• Computational experience with approximation algorithms for the set covering problem
• scientific article; zbMATH DE number 4121754 (Why is no real title available?)
• scientific article; zbMATH DE number 3410784 (Why is no real title available?)
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Set Covering by Single-Branch Enumeration with Linear-Programming Subproblems

Cited in

(3)

• Relation between set partitioning and set covering problems with quadratic fractional objective functions
• Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
• A Branch-and-Bound Algorithm for Team Formation on Social Networks

This page was built for publication: On a linearization technique for solving the quadratic set covering problem and variations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1676486)