A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1 programming problems

被引：21

作者：

Borrero, Juan S. ^{[1
]}

Gillen, Colin ^{[1
]}

Prokopyev, Oleg A. ^{[1
,2
]}

机构：

[1] Univ Pittsburgh, Dept Ind Engn, Pittsburgh, PA 15261 USA

[2] Natl Res Univ Higher Sch Econ, Lab Algorithms & Technol Networks Anal, Nizhnii Novgorod 603093, Russia

来源：

OPERATIONS RESEARCH LETTERS | 2016年 / 44卷 / 04期

关键词：

Fractional; 0-1; programming; Hyperbolic; Linearization; Binary representations; Mixed integer linear programs; GLOBAL APPROACH; OPTIMIZATION; BRANCH; VARIABLES;

D O I：

10.1016/j.orl.2016.03.015

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider reformulations of fractional (hyperbolic) 0-1 programming problems as equivalent mixed integer linear programs (MILP). The key idea of the proposed technique is to exploit binary representations of certain linear combinations of the 0-1 decision variables. Consequently, under some mild conditions, the number of product terms that need to be linearized can be greatly decreased. We perform numerical experiments comparing the proposed approach against the previous MILP reformulations used in the literature. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：479 / 486

页数：8

共 29 条

[1] A simple recipe for concise mixed 0-1 linearizations [J].

Adam, WP ;

Forrester, RJ .

OPERATIONS RESEARCH LETTERS, 2005, 33 (01) :55-61

[2] Linear forms of nonlinear expressions: New insights on old ideas [J].

Adams, Warren P. ;

Forrester, Richard J. .

OPERATIONS RESEARCH LETTERS, 2007, 35 (04) :510-518

[3] Base-2 Expansions for Linearizing Products of Functions of Discrete Variables [J].

Adams, Warren P. ;

Henry, Stephen M. .

OPERATIONS RESEARCH, 2012, 60 (06) :1477-1490

[4] ALTERNATE METHOD ON INTEGER SOLUTIONS TO LINEAR FRACTIONAL FUNCTIONALS BY A BRANCH AND BOUND TECHNIQUE [J].

AGRAWAL, SC .

ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 1977, 57 (01) :52-53

[5] Hyperbolic set covering problems with competing ground-set elements [J].

Amaldi, Edoardo ;

Bosio, Sandro ;

Malucelli, Federico .

MATHEMATICAL PROGRAMMING, 2012, 134 (02) :323-348

[6]

[Anonymous], INDIAN J PURE APPL M

[7] Feature selection for consistent biclustering via fractional 0-1 programming [J].

Busygin, S ;

Prokopyev, OA ;

Pardalos, PM .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 10 (01) :7-21

[8] A new linearization technique for multi-quadratic 0-1 programming problems [J].

Chaovalitwongse, W ;

Pardalos, PM ;

Prokopyev, OA .

OPERATIONS RESEARCH LETTERS, 2004, 32 (06) :517-522

[9] A LINEAR-PROGRAMMING APPROACH TO THE CUTTING STOCK PROBLEM .2. [J].

GILMORE, PC ;

GOMORY, RE .

OPERATIONS RESEARCH, 1963, 11 (06) :863-888

[10]

Granot D., 1976, CAN J OPER RES INF P, V14, P241

← 1 2 3 →