Penalty alternating direction methods for mixed-integer optimization: a new view on feasibility pumps. (English) Zbl 1371.65051
Summary: Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only a few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. Moreover, we propose a novel penalty framework that encompasses this alternating direction method, which allows us to refrain from random perturbations that are applied in standard versions of feasibility pumps in case of failure. We present a convergence theory for the new penalty based alternating direction method and compare the new variant of the feasibility pump with existing versions in an extensive numerical study for mixed-integer linear and nonlinear problems.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C11 | Mixed integer programming |
| 90C05 | Linear programming |
| 90C30 | Nonlinear programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
mixed integer nonlinear optimization; mixed integer linear optimization; feasibility pump; alternating direction methods; penalty methods; numerical examples; convergenceReferences:
| [1] | T. Achterberg and T. Berthold, {\it Improving the feasibility pump}, Discrete Optim., 4 (2007), pp. 77-86, . · Zbl 1170.90443 |
| [2] | D. Baena and J. Castro, {\it Using the analytic center in the feasibility pump}, Oper. Res. Lett., 39 (2011), pp. 310-317, . · Zbl 1235.90098 |
| [3] | L. Bertacco, M. Fischetti, and A. Lodi, {\it A feasibility pump heuristic for general mixed-integer problems}, Discrete Optim., 4 (2007), pp. 63-76, . · Zbl 1169.90415 |
| [4] | T. Berthold, {\it Primal Heuristics for Mixed Integer Programs}, Diploma Thesis, TU Berlin, Berlin, Germany, 2006. |
| [5] | T. Berthold, {\it Heuristic Algorithms in Global MINLP Solvers}, Ph.D. thesis, Technische Universität Berlin, Berlin, Germany, 2014. |
| [6] | N. L. Boland, A. C. Eberhard, F. Engineer, and A. Tsoukalas, {\it A new approach to the feasibility pump in mixed integer programming}, SIAM J. Optim., 22 (2012), pp. 831-861, . · Zbl 1277.90077 |
| [7] | N. L. Boland, A. C. Eberhard, F. G. Engineer, M. Fischetti, M. W. P. Savelsbergh, and A. Tsoukalas, {\it Boosting the feasibility pump}, Math. Program. Comput., 6 (2014), pp. 255-279, . · Zbl 1323.65065 |
| [8] | P. Bonami, G. Cornuéjols, A. Lodi, and F. Margot, {\it A feasibility pump for mixed integer nonlinear programs}, Math. Program., 119 (2009), pp. 331-352, . · Zbl 1163.90013 |
| [9] | P. Bonami and J. P. M. Gonçalves, {\it Heuristics for convex mixed integer nonlinear programs}, Comput. Optim. Appl., 51 (2012), pp. 729-747, . · Zbl 1241.90189 |
| [10] | P. Bonami, M. Kilinç, and J. Linderoth, {\it Algorithms and software for convex mixed integer nonlinear programs}, in Mixed Integer Nonlinear Programming, IMA Vol. Math. Appl. 154, J. Lee and S. Leyffer, eds., Springer, New York, 2012, pp. 1-39, . · Zbl 1242.90121 |
| [11] | S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, {\it Distributed optimization and statistical learning via the alternating direction method of multipliers}, Found. Trends Mach. Learn., 3 (2011), pp. 1-122, . · Zbl 1229.90122 |
| [12] | M. R. Bussieck, A. S. Drud, and A. Meeraus, {\it MINLPLib–a collection of test models for mixed-integer nonlinear programming}, INFORMS J. Comput., 15 (2003), pp. 114-119, . · Zbl 1238.90104 |
| [13] | G. D. Corporation, {\it General Algebraic Modeling System (GAMS) Release 24.5.4}, Washington, DC, 2015, . |
| [14] | E. Danna, E. Rothberg, and C. L. Pape, {\it Exploring relaxation induced neighborhoods to improve mip solutions}, Math. Program., 102 (2005), pp. 71-90, . · Zbl 1131.90036 |
| [15] | M. De Santis, S. Lucidi, and F. Rinaldi, {\it A new class of functions for measuring solution integrality in the feasibility pump approach}, SIAM J. Optim., 23 (2013), pp. 1575-1606, . · Zbl 1282.90099 |
| [16] | M. De Santis, S. Lucidi, and F. Rinaldi, {\it Feasibility pump-like heuristics for mixed integer problems}, Discrete Appl. Math., 165 (2014), pp. 152-167, . · Zbl 1471.90098 |
| [17] | S. S. Dey, A. Iroume, M. Molinaro, and D. Salvagnin, {\it Improving the Randomization Step in Feasibility Pump}, preprint, , 2016. · Zbl 1391.90426 |
| [18] | E. D. Dolan and J. J. Moré, {\it Benchmarking optimization software with performance profiles}, Math. Program., 91 (2002), pp. 201-213, . · Zbl 1049.90004 |
| [19] | A. S. Drud, {\it CONOPT–a large-scale GRG code}, ORSA J. Comput., 6 (1994), pp. 207-216, . · Zbl 0806.90113 |
| [20] | M. A. Duran and I. E. Grossmann, {\it An outer-approximation algorithm for a class of mixed-integer nonlinear programs}, Math. Program., 36 (1986), pp. 307-339, . · Zbl 0619.90052 |
| [21] | C. D’Ambrosio, A. Frangioni, L. Liberti, and A. Lodi, {\it Experiments with a feasibility pump approach for nonconvex MINLPs}, in Experimental Algorithms, Lecture Notes in Comput. Sci. 6049, P. Festa, ed., Springer, Berlin, Heidelberg, 2010, pp. 350-360, . |
| [22] | C. D’Ambrosio, A. Frangioni, L. Liberti, and A. Lodi, {\it A storm of feasibility pumps for nonconvex MINLP}, Math. Program., 136 (2012), pp. 375-402, . · Zbl 1257.90056 |
| [23] | J. Eckstein and M. Nediak, {\it Pivot, cut, and dive: A heuristic for 0-1 mixed integer programming}, J. Heuristics, 13 (2007), pp. 471-503, . |
| [24] | M. Fischetti, F. Glover, and A. Lodi, {\it The feasibility pump}, Math. Program., 104 (2005), pp. 91-104, . · Zbl 1077.90039 |
| [25] | M. Fischetti and A. Lodi, {\it Local branching}, Math. Program., 98 (2003), pp. 23-47, . · Zbl 1060.90056 |
| [26] | M. Fischetti and D. Salvagnin, {\it Feasibility pump 2.0}, Math. Program. Comput., 1 (2009), pp. 201-222, . · Zbl 1180.90208 |
| [27] | M. Frank and P. Wolfe, {\it An algorithm for quadratic programming}, Naval Res. Logist. Quart., 3 (1956), pp. 95-110, . |
| [28] | D. Gabay and B. Mercier, {\it A dual algorithm for the solution of nonlinear variational problems via finite element approximation}, Comput. Math. Appl., 2 (1976), pp. 17-40, . · Zbl 0352.65034 |
| [29] | B. Geiß ler, A. Morsi, L. Schewe, and M. Schmidt, {\it Solving power-constrained gas transportation problems using an MIP-based alternating direction method}, Comput. Chem. Eng., 82 (2015), pp. 303-317, . |
| [30] | R. Glowinski and A. Marroco, {\it Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires}, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér., 9 (1975), pp. 41-76, . · Zbl 0368.65053 |
| [31] | J. Gorski, F. Pfeuffer, and K. Klamroth, {\it Biconvex sets and optimization with biconvex functions: A survey and extensions}, Math. Methods Oper. Res., 66 (2007), pp. 373-407, . · Zbl 1146.90495 |
| [32] | Gurobi Optimization, Inc., {\it Gurobi Optimizer Reference Manual, Version 6.5}, 2015. |
| [33] | S.-P. Han and O. L. Mangasarian, {\it Exact penalty functions in nonlinear programming}, Math. Program., 17 (1979), pp. 251-269, . · Zbl 0424.90057 |
| [34] | S. Hanafi, J. Lazić, and N. Mladenović, {\it Variable neighbourhood pump heuristic for \textup0-1 mixed integer programming feasibility}, Electron. Notes Discrete Math., 36 (2010), pp. 759-766, . · Zbl 1237.90161 |
| [35] | T. Koch, T. Achterberg, E. Andersen, O. Bastert, T. Berthold, R. E. Bixby, E. Danna, G. Gamrath, A. M. Gleixner, S. Heinz, A. Lodi, H. Mittelmann, T. Ralphs, D. Salvagnin, D. E. Steffy, and K. Wolter, {\it MIPLIB 2010}, Math. Program. Comput., 3 (2011), pp. 103-163, . |
| [36] | O. L. Mangasarian, {\it Solution of general linear complementarity problems via nondifferentiable concave minimization}, Acta Math. Vietnam., 22 (1997), pp. 199-205. · Zbl 0895.90167 |
| [37] | J. Nocedal and S. J. Wright, {\it Numerical Optimization}, Springer Series Oper. Res. Financ. Eng., 2nd ed., Springer, New York, 2006, . · Zbl 1104.65059 |
| [38] | I. Nowak, {\it Relaxation and decomposition methods for mixed integer nonlinear programming}, 2005, pdf: urn:nbn:de:kobv:11-10038479, available online at . · Zbl 1089.90039 |
| [39] | S. Sharma, {\it Mixed-integer nonlinear programming heuristics applied to a shale gas production optimization problem}, 2013, available online at . |
| [40] | S. Sharma, B. R. Knudsen, and B. Grimstad, {\it Towards an objective feasibility pump for convex MINLPs}, Comput. Optim. Appl., 63 (2015), pp. 737-753, . · Zbl 1343.90053 |
| [41] | R. E. Wendell and A. P. Hurter, Jr., {\it Minimization of a non-separable objective function subject to disjoint constraints}, Operations Res., 24 (1976), pp. 643-657, . · Zbl 0347.90044 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
