A CONIC APPROXIMATION METHOD FOR THE 0-1 QUADRATIC KNAPSACK PROBLEM

被引：6

作者：

Zhou, Jing ^{[1
]}

Chen, Dejun ^{[1
]}

Wang, Zhenbo ^{[1
]}

Xing, Wenxun ^{[1
]}

机构：

[1] Tsinghua Univ, Dept Math Sci, Beijing 100084, Peoples R China

来源：

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION | 2013年 / 9卷 / 03期

基金：

中国国家自然科学基金;

关键词：

0-1 quadratic knapsack problem; nonnegative quadratic function cone; conic approximation; MAXIMAL CLIQUE PROBLEM; PROGRAMMING PROBLEMS; DUALITY;

D O I：

10.3934/jimo.2013.9.531

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This paper solves the 0-1 quadratic knapsack problem using a conic approximation method. We propose a nonnegative quadratic function cone program to equivalently represent the problem. Based on the technique of linear matrix inequality, we present an adaptive approximation scheme to obtain a global optimal solution or lower bound for the problem by using computable cones. Some computational examples are provided to show the effectiveness of the proposed method.

引用

页码：531 / 547

页数：17