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

DOI10.1016/S0377-2217(03)00244-3zbMATH Open1067.90126OpenAlexW2024911991MaRDI QIDQ703909FDOQ703909

Authors: Alain Billionnet, Éric Soutif 

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

Recommendations

• A new upper bound for the 0-1 quadratic knapsack problem
• Lagrangean methods for the 0-1 quadratic knapsack problem
• 0-1 quadratic knapsack problems: an exact approach based on a \(t\)-linearization
• Exact solution methods for the \(k\)-item quadratic knapsack problem
• Linear programming for the \(0-1\) quadratic knapsack problem

zbMATH Keywords

Lagrangian decompositionBranch-and-boundComputational results0--1 quadratic programmingKnapsack

Mathematics Subject Classification ID

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

Cites Work

• Quadratic knapsack problems
• A Decomposition Method for Quadratic Zero-One Programming
• Exact Solution of the Quadratic Knapsack Problem
• Linear programming for the \(0-1\) quadratic knapsack problem
• Lagrangean methods for the 0-1 quadratic knapsack problem
• Title not available (Why is that?)
• A new upper bound for the 0-1 quadratic knapsack problem
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems

Cited In (42)

• Theoretical and computational study of several linearisation techniques for binary quadratic problems
• A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs
• 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
• Solution of large quadratic knapsack problems through aggressive reduction
• A new variable reduction technique for convex integer quadratic programs
• On reduction of duality gap in quadratic knapsack problems
• Simple solution methods for separable mixed linear and quadratic knapsack problem
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• Dantzig-Wolfe reformulations for binary quadratic problems
• 0-1 quadratic knapsack problems: an exact approach based on a \(t\)-linearization
• Lagrangean methods for 0-1 quadratic problems
• Using modifications to Grover's search algorithm for quantum global optimization
• Exact solution method to solve large scale integer quadratic multidimensional knapsack problems
• Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem
• Lagrangian heuristics for the quadratic knapsack problem
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Interval uncertainty-based robust optimization for convex and non-convex quadratic programs with applications in network infrastructure planning
• Asymptotic behavior of the quadratic knapsack problem
• Global optimality conditions and optimization methods for quadratic knapsack problems
• Dual mean field search for large scale linear and quadratic knapsack problems
• Generalized quadratic multiple knapsack problem and two solution approaches
• A cut-and-branch algorithm for the quadratic knapsack problem
• Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation
• Solving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm
• Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Hub-and-spoke network design and fleet deployment for string planning of liner shipping
• Combining Constraint Propagation and Discrete Ellipsoid-Based Search to Solve the Exact Quadratic Knapsack Problem
• Inductive linearization for binary quadratic programs with linear constraints: a computational study
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• Reformulation of the quadratic multidimensional knapsack problem as copositive/completely positive programs
• A computational study on the quadratic knapsack problem with multiple constraints
• Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem
• Quadratic Combinatorial Optimization Using Separable Underestimators
• Iterated responsive threshold search for the quadratic multiple knapsack problem
• A note on semidefinite relaxation for 0-1 quadratic knapsack problems
• A new Lagrangian based branch and bound algorithm for the 0-1 knapsack problem
• Exact solution methods for the \(k\)-item quadratic knapsack problem
• A lifted-space dynamic programming algorithm for the quadratic knapsack problem
• A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems
• An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating

Uses Software

• Knapsack

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703909)