On reduction of duality gap in quadratic knapsack problems

DOI10.1007/S10898-012-9872-9zbMATH Open1281.90045OpenAlexW2090620760WikidataQ57445437 ScholiaQ57445437MaRDI QIDQ693132FDOQ693132

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

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

zbMATH Keywords

duality gapLagrangian relaxationSDP relaxationquadratic knapsack problemcell enumeration

Mathematics Subject Classification ID

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

Cites Work

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

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

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)