Mixed-Integer Models for Nonseparable Piecewise-Linear Optimization: Unifying Framework and Extensions

被引：242

作者：

Vielma, Juan Pablo ^{[1
]}

Ahmed, Shabbir ^{[1
]}

Nemhauser, George ^{[1
]}

机构：

[1] Georgia Inst Technol, H Milton Stewart Sch Ind & Syst Engn, Atlanta, GA 30332 USA

来源：

OPERATIONS RESEARCH | 2010年 / 58卷 / 02期

基金：

美国国家科学基金会;

关键词：

PROGRAMMING-PROBLEMS; OUTER-APPROXIMATION; BINARY VARIABLES; ALGORITHM; NONCONVEX; CONCAVE; REPRESENTABILITY;

D O I：

10.1287/opre.1090.0721

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study the modeling of nonconvex piecewise-linear functions as mixed-integer programming (MIP) problems. We review several new and existing MIP formulations for continuous piecewise-linear functions with special attention paid to multivariate nonseparable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study the extension of these formulations to lower semicontinuous piecewise-linear functions.

引用

页码：303 / 315

页数：13

共 45 条

[1] Towards compatible triangulations
Aichholzer, O
Aurenhammer, F
Hurtado, F
Krasser, H
[J]. THEORETICAL COMPUTER SCIENCE, 2003, 296 (01) : 3 - 13
[2] [Anonymous], 1989, COMBINATORIAL ALGORI
[3] [Anonymous], 2003, Linear programming 2: theory and extensions
[4] [Anonymous], 1993, AMPL, a modeling language for mathematical programming
[5] A COMPOSITE ALGORITHM FOR A CONCAVE-COST NETWORK FLOW PROBLEM
BALAKRISHNAN, A
GRAVES, SC
[J]. NETWORKS, 1989, 19 (02) : 175 - 202
[6] Balas E., 1979, ANN DISCRETE MATH, V5, P3, DOI DOI 10.1016/S0167-5060(08)70342-X
[7] An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms
Bergamini, Maria Lorena
Grossmann, Ignacio
Scenna, Nicolas
Aguirre, Pio
[J]. COMPUTERS & CHEMICAL ENGINEERING, 2008, 32 (03) : 477 - 493
[8] Logic-based outer approximation for globally optimal synthesis of process networks
Bergamini, ML
Aguirre, P
Grossmann, I
[J]. COMPUTERS & CHEMICAL ENGINEERING, 2005, 29 (09) : 1914 - 1933
[9] Piecewise linear interpolants to Lagrange and Hermite convex scattered data
Carnicer, JM
Floater, MS
[J]. NUMERICAL ALGORITHMS, 1996, 13 (3-4) : 345 - 364
[10] Coppersmith D., 2005, DISCRETE OPTIM, V2, P190

← 1 2 3 4 5 →