Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem

DOI10.1016/j.ejor.2020.10.047zbMath1487.90549OpenAlexW3097492990MaRDI QIDQ2030649

Laura Galli, Carlos Rey, Paolo Toth, Silvano Martello

Publication date: 7 June 2021

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

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

zbMATH Keywords

Lagrangian relaxationcombinatorial optimizationbinary quadratic programmingreformulation linearization techniquequadratic multiple knapsack

Mathematics Subject Classification ID

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

Related Items

Knapsack problems with dependencies through non-additive measures and Choquet integral, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Lagrangian matheuristics for the quadratic multiple knapsack problem, A hybrid evolutionary search for the generalized quadratic multiple knapsack problem, Introduction to special issue, A branch-and-bound algorithm for the quadratic multiple knapsack problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized quadratic multiple knapsack problem and two solution approaches
• Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• The quadratic knapsack problem -- a survey
• A bound and bound algorithm for the zero-one multiple knapsack problem
• Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints
• Tabu-enhanced iterated greedy algorithm: a case study in the quadratic multiple knapsack problem
• Theoretical and computational study of several linearisation techniques for binary quadratic problems
• Iterated responsive threshold search for the quadratic multiple knapsack problem
• Strategic oscillation for the quadratic multiple knapsack problem
• Constrained 0-1 quadratic programming: basic approaches and extensions
• Upper bounds and exact algorithms for \(p\)-dispersion problems
• Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Quadratic knapsack problems
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Exact Solution of the Quadratic Knapsack Problem
• Generalized Bundle Methods
• An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program