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 条

[1] LINEARIZATION STRATEGIES FOR A CLASS OF ZERO-ONE MIXED INTEGER PROGRAMMING-PROBLEMS [J].

ADAMS, WP ;

SHERALI, HD .

OPERATIONS RESEARCH, 1990, 38 (02) :217-226

[2]

Floudas C. A., 1995, Handbook of global optimization, P217, DOI 10.1007/978-1-4615-2025-2_5

[3] CONVERTING 0-1 POLYNOMIAL PROGRAMMING PROBLEM TO A 0-1 LINEAR PROGRAM [J].

GLOVER, F ;

WOOLSEY, E .

OPERATIONS RESEARCH, 1974, 22 (01) :180-182

[4] FURTHER REDUCTION OF ZERO-ONE POLYNOMIAL PROGRAMMING PROBLEMS TO ZERO-ONE LINEAR PROGRAMMING PROBLEMS [J].

GLOVER, F ;

WOOLSEY, E .

OPERATIONS RESEARCH, 1973, 21 (01) :156-161

[5]

Hansen P., 1979, Discrete Optimisation, P53

[6]

Horst R., 1995, INTRO GLOBAL OPTIMIZ

[7] Prediction of human epileptic seizures based on optimization and phase changes of brain electrical activity [J].

Iasemidis, LD ;

Pardalos, PM ;

Shiau, DS ;

Chaovalitwongse, W ;

Narayanan, K ;

Kumar, S ;

Carney, PR ;

Sackellares, JC .

OPTIMIZATION METHODS & SOFTWARE, 2003, 18 (01) :81-104

[8] Quadratic binary programming and dynamical system approach to determine the predictability of epileptic seizures [J].

Iasemidis, LD ;

Pardalos, P ;

Sackellares, JC ;

Shiau, DS .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2001, 5 (01) :9-26

[9]

Pardalos P. M., 1990, Annals of Operations Research, V22, P271, DOI 10.1007/BF02023057

[10] GRAPH SEPARATION TECHNIQUES FOR QUADRATIC ZERO-ONE PROGRAMMING [J].

PARDALOS, PM ;

JHA, S .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1991, 21 (6-7) :107-113

← 1 2 →