A new linearization technique for multi-quadratic 0-1 programming problems

被引：50

作者：

Chaovalitwongse, W ^{[1
]}

Pardalos, PM ^{[1
]}

Prokopyev, OA ^{[1
]}

机构：

[1] Univ Florida, Dept Ind & Syst Engn, Ctr Appl Optimizat, Gainesville, FL 32611 USA

来源：

OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 06期

关键词：

quadratic; 0-1; programming; multi-quadratic; linear mixed 0-1 programming; linearization;

D O I：

10.1016/j.orl.2004.03.005

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the reduction of multi-quadratic 0-1 programming problems to linear mixed 0-1 programming problems. In this reduction, the number of additional continuous variables is O(kn) (n is the number of initial 0-1 variables and k is the number of quadratic constraints). The number of 0-1 variables remains the same. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：517 / 522

页数：6

共 15 条

[11] COMPUTATIONAL ASPECTS OF A BRANCH AND BOUND ALGORITHM FOR QUADRATIC ZERO-ONE PROGRAMMING [J].

PARDALOS, PM ;

RODGERS, GP .

COMPUTING, 1990, 45 (02) :131-144

[12] CONSTRUCTION OF TEST PROBLEMS IN QUADRATIC BIVALENT PROGRAMMING [J].

PARDALOS, PM .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1991, 17 (01) :74-87

[13] COMPLEXITY OF UNIQUENESS AND LOCAL SEARCH IN QUADRATIC 0-1 PROGRAMMING [J].

PARDALOS, PM ;

JHA, S .

OPERATIONS RESEARCH LETTERS, 1992, 11 (02) :119-123

[14]

PARDALOS PM, 2004, IN PRESS MATH PROGRA

[15] REDUCTION OF INTEGER POLYNOMIAL PROGRAMMING PROBLEMS TO ZERO-ONE LINEAR PROGRAMMING [J].

WATTERS, LJ .

OPERATIONS RESEARCH, 1967, 15 (06) :1171-&

← 1 2 →