On reduction of duality gap in quadratic knapsack problems

DOI10.1007/S10898-012-9872-9MaRDI QIDQ693132zbMATH OpenOpenAlexWikidataFDO

Authors X. J. Zheng, Xiaoling Sun, Duan Li, Yifan Xu

Publication date 7 December 2012

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-012-9872-9

zbMATH Keywords

duality gapLagrangian relaxationSDP relaxationquadratic knapsack problemcell enumeration

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Combinatorial optimization (90C27)

Recommendations

• On The Reduction of Duality Gap in Box Constrained Nonconvex Quadratic Program
• On duality gap in binary quadratic programming
• Exact solution methods for the \(k\)-item quadratic knapsack problem
• Duality gap estimation of linear equality constrained binary quadratic programming
• The quadratic knapsack problem -- a survey

Cites work

• scientific article; zbMATH DE number 4112385 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1383707 (Why is no real title available?)
• A new upper bound for the 0-1 quadratic knapsack problem
• A polynomial case of unconstrained zero-one quadratic optimization
• A semidefinite programming approach to the quadratic knapsack problem
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
• Exact Solution of the Quadratic Knapsack Problem
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Global extremal conditions for multi-integer quadratic programming
• Lagrangean methods for the 0-1 quadratic knapsack problem
• On the stability of a dual weak vector variational inequality problem
• On the supermodular knapsack problem
• Quadratic knapsack problems
• Reverse search for enumeration
• Semidefinite programming and integer programming
• Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality
• Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
• The quadratic knapsack problem -- a survey

Cited in

(3)

• Duality gap estimation of linear equality constrained binary quadratic programming
• Improved estimation of duality gap in binary quadratic programming using a weighted distance measure
• On duality gap in binary quadratic programming

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: On reduction of duality gap in quadratic knapsack problems

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