Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems

DOI10.1016/j.cor.2019.104769zbMath1458.90503arXiv1802.00897OpenAlexW2968238625MaRDI QIDQ2329727

Michael Friesen, Abraham P. Punnen, Pooja Pandey

Publication date: 18 October 2019

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

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

zbMATH Keywords

combinatorial optimization0-1 quadratic programmingset covering problemequivalent formulationsexperimental analysis of algorithms

Mathematics Subject Classification ID

Integer programming (90C10) Quadratic programming (90C20) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (6)

Introduction to QUBO ⋮ Mathematical Programming Models and Exact Algorithms ⋮ The Rank-One Quadratic Assignment Problem ⋮ A Branch-and-Bound Algorithm for Team Formation on Social Networks ⋮ The quadratic cycle cover problem: special cases and efficient bounds ⋮ The linearization problem of a binary quadratic problem and its applications

Uses Software

• CPLEX
• Gurobi

Cites Work

• Exact quadratic convex reformulations of mixed-integer quadratically constrained problems
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• The unconstrained binary quadratic programming problem: a survey
• SC-Hamiltonian graphs and digraphs: new necessary conditions and their impacts
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• The quadratic knapsack problem -- a survey
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• A characterization of linear admissible transformations for the m- travelling salesmen problem
• Computational experience with approximation algorithms for the set covering problem
• The quadratic assignment problem. Theory and algorithms
• Weighted graphs with all Hamiltonian cycles of the same length
• On a linearization technique for solving the quadratic set covering problem and variations
• The bilinear assignment problem: complexity and polynomially solvable special cases
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• The constant objective value property for multidimensional assignment problems
• The quadratic shortest path problem: complexity, approximability, and solution methods
• An algorithm for set covering problem
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Combinatorial optimization with interaction costs: complexity and solvable cases
• Approximation of the quadratic set covering problem
• A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs
• An improved linearization strategy for zero-one quadratic programming problems
• Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs
• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• The Quadratic Assignment Problem
• Solving Mixed Integer Bilinear Problems Using MILP Formulations
• An O(n⁴) Algorithm for the QAP Linearization Problem
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• A New Lower Bound for the Quadratic Assignment Problem
• Minimization and maximization versions of the quadratic travelling salesman problem
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems