A new upper bound for the 0-1 quadratic knapsack problem

DOI10.1016/S0377-2217(97)00414-1zbMATH Open0933.90049OpenAlexW2057884923MaRDI QIDQ1806683FDOQ1806683

Authors: Alain Billionnet, Alain Faye, Éric Soutif 

Publication date: 8 November 1999

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(97)00414-1

Recommendations

• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• Linear programming 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
• Decomposition and linearization for 0-1 quadratic programming

zbMATH Keywords

quadratic programmingcomputational experimentsupper boundLagrangian decomposition0-1 quadratic knapsack problemquadratic pseudo-Boolean function

Mathematics Subject Classification ID

Boolean programming (90C09)

Cites Work

• Clustering and domination in perfect graphs
• Validation of subgradient optimization
• Quadratic knapsack problems
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Decomposition Method for Quadratic Zero-One Programming
• Quadratic Binary Programming with Application to Capital-Budgeting Problems
• Min-cut clustering
• A semidefinite programming approach to 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?)
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
• A new bound for the quadratic knapsack problem and its use in a branch and bound algorithm

Cited In (25)

• Upper bounds and exact algorithms for \(p\)-dispersion problems
• A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs
• The polynomial robust knapsack problem
• Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1
• On exact solution approaches for bilevel quadratic 0-1 knapsack problem
• A column generation approach for the unconstrained binary quadratic programming problem
• On reduction of duality gap in quadratic knapsack problems
• A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization
• The generalized quadratic knapsack problem. A neuronal network approach
• Lagrangean methods for 0-1 quadratic problems
• Upper bounds for large scale integer quadratic multidimensional knapsack problems
• Lagrangian heuristics for the quadratic knapsack problem
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Decomposition and linearization for 0-1 quadratic programming
• Parametric convex quadratic relaxation of the quadratic knapsack problem
• Global optimality conditions and optimization methods for quadratic knapsack problems
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Title not available (Why is that?)
• The quadratic knapsack problem -- a survey
• Lagrangean decompositions for the unconstrained binary quadratic programming problem
• Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem
• The quadratic 0-1 knapsack problem with series-parallel support
• A note on semidefinite relaxation for 0-1 quadratic knapsack problems
• A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems

This page was built for publication: A new upper bound 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 Q1806683)