Maximizing the product of two linear functions in 0-1 variables

被引：7

作者：

Hammer, PL

Hansen, P

Pardalos, PM

Rader, DJ

机构：

[1] Rose Hulman Inst Technol, Dept Math, Terre Haute, IN 47803 USA

[2] Rutgers State Univ, RUTCOR, New Brunswick, NJ 08903 USA

[3] Ecole Hautes Etud Commerciales, Gerad, Montreal, PQ, Canada

[4] Univ Florida, Dept Ind & Syst Engn, Gainesville, FL 32611 USA

来源：

OPTIMIZATION | 2002年 / 51卷 / 03期

基金：

美国国家科学基金会; 加拿大自然科学与工程研究理事会;

关键词：

quadratic; 0-1; programming; continuous problem; discrete problem; polynomial algorithms; continuous relaxation; penalties for nonnegative optimal solutions; computational results;

D O I：

10.1080/02331930290009847

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study both the continuous and discrete problems of maximizing the product of two linear functions subject to all variables being between, 0 and 1. We first give linear and low-order polynomial algorithms for the solution of the continuous problem. In addition, we describe penalties that help to fix variables in the discrete problem. Extensive computational tests demonstrate the effectiveness of these results.

引用

页码：511 / 537

页数：27

共 15 条

[1] AN ALGORITHM FOR LARGE ZERO-ONE KNAPSACK-PROBLEMS [J].