Intersection Cuts for Factorable MINLP

被引:10
作者
Serrano, Felipe [1 ]
机构
[1] Zuse Inst Berlin, Optimizat Dept, Takustr 7, D-14195 Berlin, Germany
来源
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2019 | 2019年 / 11480卷
关键词
Mixed-integer nonlinear programming; Intersection cuts; Monoidal strengthening; CONVEXITY CUTS; GLOBAL OPTIMIZATION; ALGORITHM; PROGRAMS;
D O I
10.1007/978-3-030-17953-3_29
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.
引用
收藏
页码:385 / 398
页数:14
相关论文
共 43 条
[1]  
Achterberg T., 2013, Facets of Combinatorial Optimization, P449, DOI [DOI 10.1007/978-3-642-38189-8, DOI 10.1007/978-3-642-38189-8_18, 10.1007/978-3-642-38189-8, 10.1007/978-3-642-38189-8_18]
[2]  
[Anonymous], 2011, Surv. Op. Res. Manag. Sci
[3]  
Balas E., 1979, Discrete Optimisation, P3
[4]   INTERSECTION CUTS - NEW TYPE OF CUTTING PLANES FOR INTEGER PROGRAMMING [J].
BALAS, E .
OPERATIONS RESEARCH, 1971, 19 (01) :19-+
[5]   Monoidal cut strengthening revisited [J].
Balas, E. ;
Qualizza, A. .
DISCRETE OPTIMIZATION, 2012, 9 (01) :40-49
[6]   A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS [J].
BALAS, E ;
CERIA, S ;
CORNUEJOLS, G .
MATHEMATICAL PROGRAMMING, 1993, 58 (03) :295-324
[7]   STRENGTHENING CUTS FOR MIXED INTEGER PROGRAMS [J].
BALAS, E ;
JEROSLOW, RG .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1980, 4 (04) :224-234
[8]   Generalized intersection cuts and a new cut generating paradigm [J].
Balas, Egon ;
Margot, Francois .
MATHEMATICAL PROGRAMMING, 2013, 137 (1-2) :19-35
[9]  
Basu A, 2011, J CONVEX ANAL, V18, P427
[10]  
Belotti P, 2012, IMA VOL MATH APPL, V154, P117