A Feasibility Pump for mixed integer nonlinear programs

被引：76

作者：

Bonami, Pierre ^{[2
]}

Cornuejols, Gerard ^{[1
,2
]}

Lodi, Andrea ^{[3
]}

Margot, Francois ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA

[2] LIF, Fac Sci Luminy, F-13288 Marseille, France

[3] Univ Bologna, DEIS, I-40136 Bologna, Italy

来源：

MATHEMATICAL PROGRAMMING | 2009年 / 119卷 / 02期

基金：

美国国家科学基金会;

关键词：

90C113;

D O I：

10.1007/s10107-008-0212-2

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration within an outer approximation scheme. We report computational results.

引用

页码：331 / 352

页数：22

共 11 条

[1] Improving the feasibility pump [J].

Achterberg, Tobias ;

Berthold, Timo .

DISCRETE OPTIMIZATION, 2007, 4 (01) :77-86

[2] A feasibility pump heuristic for general mixed-integer problems [J].

Bertacco, Livio ;

Fischetti, Matteo ;

Lodi, Andrea .

DISCRETE OPTIMIZATION, 2007, 4 (01) :63-76

[3]

Boddy MS, 2003, LECT NOTES COMPUT SC, V2861, P142

[4]

BONAMI P, 2008, DISCRETE OP IN PRESS

[5] AN OUTER-APPROXIMATION ALGORITHM FOR A CLASS OF MIXED-INTEGER NONLINEAR PROGRAMS [J].

DURAN, MA ;

GROSSMANN, IE .

MATHEMATICAL PROGRAMMING, 1986, 36 (03) :307-339

[6]

Fiacco AV, 1990, Nonlinear Programming: Sequential Unconstrained Minimization Techniques

[7] The feasibility pump [J].

Fischetti, M ;

Glover, F ;

Lodi, A .

MATHEMATICAL PROGRAMMING, 2005, 104 (01) :91-104

[8]

Mangasarian OL, 1994, NONLINEAR PROGRAMMIN

[9]

Nowak I., 2005, RELAXATION DECOMPOSI

[10]

DICOPT

← 1 2 →