An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem

DOI10.1016/S0377-2217(03)00244-3zbMath1067.90126OpenAlexW2024911991MaRDI QIDQ703909

Publication date: 12 January 2005

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(03)00244-3

zbMATH Keywords

Lagrangian decomposition Branch-and-bound Computational results Knapsack 0--1 quadratic programming

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (34)

Dantzig-Wolfe reformulations for binary quadratic problems ⋮ Dual mean field search for large scale linear and quadratic knapsack problems ⋮ A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs ⋮ On exact solution approaches for bilevel quadratic 0-1 knapsack problem ⋮ Exact solution method to solve large scale integer quadratic multidimensional knapsack problems ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Asymptotic behavior of the quadratic knapsack problem ⋮ Generalized quadratic multiple knapsack problem and two solution approaches ⋮ An iterated ``hyperplane exploration approach for the quadratic knapsack problem ⋮ Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem ⋮ A cut-and-branch algorithm for the quadratic knapsack problem ⋮ A lifted-space dynamic programming algorithm for the quadratic knapsack problem ⋮ On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem ⋮ Quadratic Combinatorial Optimization Using Separable Underestimators ⋮ Global optimality conditions and optimization methods for quadratic knapsack problems ⋮ An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating ⋮ A new variable reduction technique for convex integer quadratic programs ⋮ A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs ⋮ On reduction of duality gap in quadratic knapsack problems ⋮ Simple solution methods for separable mixed linear and quadratic knapsack problem ⋮ A computational study on the quadratic knapsack problem with multiple constraints ⋮ Interval uncertainty-based robust optimization for convex and non-convex quadratic programs with applications in network infrastructure planning ⋮ Using modifications to Grover's search algorithm for quantum global optimization ⋮ Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem ⋮ Hub-and-spoke network design and fleet deployment for string planning of liner shipping ⋮ Lagrangian heuristics for the quadratic knapsack problem ⋮ Theoretical and computational study of several linearisation techniques for binary quadratic problems ⋮ Reformulation of the Quadratic Multidimensional Knapsack Problem as Copositive/Completely Positive Prorams ⋮ Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation ⋮ Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method ⋮ Iterated responsive threshold search for the quadratic multiple knapsack problem ⋮ Solving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm ⋮ A note on semidefinite relaxation for 0-1 quadratic knapsack problems ⋮ A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems

Uses Software

Knapsack

Cites Work

This page was built for publication: An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem