Constrained 0-1 quadratic programming: basic approaches and extensions

DOI10.1016/j.ejor.2006.09.028zbMath1138.90455OpenAlexW2048804785MaRDI QIDQ2467302

Alberto Caprara

Publication date: 21 January 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2006.09.028

zbMATH Keywords

Lagrangian relaxationbounding proceduresreformulation

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

Speeding up IP-based algorithms for constrained quadratic 0-1 optimization, Lower bounds and exact algorithms for the quadratic minimum spanning tree problem, Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation, On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study, Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach, Wave order picking under the mixed-shelves storage strategy: a solution method and advantages, New formulations of the multiple sequence alignment problem, Quadratic Combinatorial Optimization Using Separable Underestimators, A note on representations of linear inequalities in non-convex mixed-integer quadratic programs, Extending the QCR method to general mixed-integer programs, A multilevel analysis of the Lasserre hierarchy, An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations, The quadratic shortest path problem: complexity, approximability, and solution methods, Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem, Theoretical and computational study of several linearisation techniques for binary quadratic problems, DC Programming and DCA for Challenging Problems in Bioinformatics and Computational Biology, Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• Linear programming for the \(0-1\) quadratic knapsack problem
• A Lagrangian-based heuristic for large-scale set covering problems
• The quadratic assignment problem. Theory and algorithms
• The cut polytope and the Boolean quadric polytope
• A dual framework for lower bounds of the quadratic assignment problem based on linearization
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Upper bounds and exact algorithms for \(p\)-dispersion problems
• The Quadratic Assignment Problem
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Quadratic knapsack problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Exact Solution of the Quadratic Knapsack Problem
• A Fast Parametric Maximum Flow Algorithm and Applications
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• A Heuristic Method for the Set Covering Problem
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• The traveling-salesman problem and minimum spanning trees: Part II
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem