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 (17)

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

This page was built for publication: Constrained 0-1 quadratic programming: basic approaches and extensions