Abstract
This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution \(\bar{x}\) of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables \(x_j\) with \(\bar{x} _{j} \in \mathbb {Z}\) and bounding the remaining integer variables to \(x_{j} \in \{ \lfloor \bar{x} _{j} \rfloor , \lceil \bar{x} _{j} \rceil \}\). We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLP s, using solely software which is available in source code. It turns out that for these problem classes 60 to 70 % of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.
Similar content being viewed by others
Notes
Stage 3 of the Feasibility Pump solves (a reformulation of) the original MIP with a new objective function. It minimizes the distance to an infeasible point gained from the pumping algorithm; more precisely to the one which was closest to the polyhedron associated to the LP relaxation. For details, see [9].
This holds, to a certain extent, for all general MINLP test sets that the author is aware of.
For a detailed discussion of the shifted geometric mean, see Achterberg [2, Appendix A3].
References
Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 1–12 (2006). http://miplib.zib.de/miplib2003/
Achterberg, T.: Constraint Integer Programming. PhD thesis, Technische Universität Berlin, 2007
Achterberg, T., Berthold, T.: Improving the feasibility pump. Discret Optim. 4(1), 77–86 (2007). (Special Issue)
Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009)
Balas, E.: Facets of the knapsack polytope. Math. Program. 8, 146–164 (1975)
Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G.: Octane: a new heuristic for pure 0–1 programs. Operat. Res. 49, 207–225 (2001)
Balas, E., Schmieta, S., Wallace, C.: Pivot and shift—a mixed integer programming heuristic. Discret. Optim. 1(1), 3–12 (2004)
Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24, 597–634 (2009)
Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discret. Optim. 4(1), 77–86 (2007). (Special Issue)
Berthold, T., Feydy, T., Stuckey, P.J.: Rapid learning for binary programs. In: Lodi, A., Milano, M., Toth, P. (eds.) Proceedings of CPAIOR 2010, vol 6140 of LNCS, pp. 51–55. Springer, Berlin (2010)
Berthold, T., Gleixner, A.M.: Undercover—a primal heuristic for MINLP based on sub-MIPs generated by set covering. In: Bonami, P., Liberti, L., Miller, A.J., Sartenaer, A. (eds.) Proceedings of the EWMINLP, pp. 103–112 (2010)
Berthold, T., Gleixner, A.M.: Undercover—a primal MINLP heuristic exploring a largest sub-MIP. Math. Program. A (2013). doi:10.1007/s10107-013-0635-2
Berthold, T., Heinz, S., Pfetsch, M.E., Vigerske, S.: Large neighborhood search beyond MIP. In: Gaspero, L.D., Schaerf, A., Stützle, T. (eds.) Proceedings of the 9th Metaheuristics International Conference (MIC 2011), pp. 51–60 (2011)
Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611–614 (2013)
Berthold, T.: Primal heuristics for mixed integer programs. Technische Universität Berlin, Diploma thesis (2006)
Berthold, T.: Heuristics of the branch-cut-and-price-framework SCIP. In: Kalcsics, J., Nickel, S. (eds.) Operations Research Proceedings 2007, pp. 31–36. Springer-Verlag, Berlin (2008)
Berthold, T., Heinz, S., Vigerske, S.: Extending a CIP framework to solve MIQCPs. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications, pp. 427–444. Springer, Berlin (2011)
Berthold, T., Gleixner, A.M., Heinz, S., Vigerske, S.: Analyzing the computational impact of MIQCP solver components. Numer. Algebra, Control Optim. 2(4), 739–748 (2012)
Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.: An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12–15 (1998)
Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: MIP: theory and practice—closing the gap. In: Powell, M., Scholtes, S. (eds.) Systems Modelling and Optimization: Methods, Theory, and Applications, pp. 19–49. Kluwer Academic Publisher, Dordrecht (2000)
Bonami, P., Gonçalves, J.: Heuristics for convex mixed integer nonlinear programs. Comput. Optim. Appl. 51(2), 729–747 (2012)
Bonami, P., Biegler, L., Conn, A., Cornuéjols, G., Grossmann, I., Laird, C., Lee, J., Lodi, A., Margot, F., Sawaya, N., Wächter, A.: An algorithmic framework for convex mixed integer nonlinear programs. Disc. Opt. 5, 186–204 (2008)
Bonami, P., Cornuéjols, G., Lodi, A., Margot, F.: A feasibility pump for mixed integer nonlinear programs. Math. Program. 119(2), 331–352 (2009)
Bussieck, M., Drud, A., Meeraus, A.: MINLPLib—a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1), 114–119 (2003)
Bussieck, M.R., Vigerske, S.: MINLP solver software. In: Cochran, J.J., Cox, L.A., Keskinocak, P., Kharoufeh, J.P., Smith, J.C. (eds.) Wiley Encyclopedia of Operations Research and Management Science. Wiley (2010)
CBC user guide - COIN-OR. http://www.coin-or.org/Cbc
CppAD. A Package for Differentiation of C++ Algorithms. http://www.coin-or.org/CppAD/
D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: Experiments with a feasibility pump approach for nonconvex MINLPs. In: Festa, P. (ed.) Experimental Algorithms. Lecture Notes in Computer Science, pp. 350–360. Springer, Berlin (2010)
D’Ambrosio, C., Lodi, A.: Mixed integer nonlinear programming tools: a practical overview. 4OR: Q. J. Operat. Res. 9, 329–349 (2011)
D’Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: A storm of feasibility pumps for nonconvex MINLP. Math. Program. 136, 375–402 (2012)
Danna, E., Rothberg, E., Pape, C.L.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. A 102(1), 71–90 (2004)
Fischetti, M., Monaci, M.: Proximity search for 0–1 mixed-integer convex programming. Technical report, DEI, University of Padova (2012)
Fischetti, M., Lodi, A.: Local branching. Mathematical Programming B 98(1–3), 23–47 (2003)
Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. A 104(1), 91–104 (2005)
Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. C 1, 201–222 (2009)
Ghosh, S.: DINS, a MIP improvement heuristic. In: Fischetti, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization (IPCO 2007), volume 4513 of LNCS, pp. 310–323 (2007)
Glover, F., Løkketangen, A., Woodruff, D.L.: Scatter search to generate diverse MIP solutions. In: Laguna, M., González-Velarde, J.L. (eds.) OR Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, pp. 299–317. Kluwer Academic Publishers, Dordrecht (2000)
Glover, F., Laguna, M.: General purpose heuristics for integer programming—part I. J. Heuristics 2(4), 343–358 (1997)
Glover, F., Laguna, M.: General purpose heuristics for integer programming—part II. J. Heuristics 3(2), 161–179 (1997)
Hammer, P.L., Johnson, E.L., Peled, U.N.: Facets of regular 0–1 polytopes. Math. Program. 8, 179–206 (1975)
Hansen, P., Mladenović, N., Urošević, D.: Variable neighborhood search and local branching. Comput. Operat. Res. 33(10), 3034–3045 (2006)
Ipopt (Interior Point OPTimizer). http://www.coin-or.org/Ipopt/
Jones, E., Oliphant, T., Peterson, P., et al.: SciPy: open source scientific tools for Python (2001)
Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Program. Comput. 3(2), 103–163 (2011)
Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28(3), 497–520 (1960)
Liberti, L., Mladenović, N., Nannicini, G.: A recipe for finding good solutions to MINLPs. Math. Program. Comput. 3(4), 349–390 (2011)
LindoGlobal. Lindo Systems, Inc. http://www.lindo.com
Løkketangen, A.: Heuristics for 0–1 mixed integer programming. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied, Optimization, pp. 474–477. Oxford University Press, New York (2002)
Løkketangen, A., Glover, F.: Solving zero/one mixed integer programming problems using tabu search. Eur. J. Operat. Res. 106, 624–658 (1998)
Mittelmann, H.: Decision tree for optimization software: Benchmarks for optimization software. http://plato.asu.edu/bench.html
Nannicini, G., Belotti, P., Liberti, L.: A local branching heuristic for MINLPs. ArXiv e-prints (2008)
Nannicini, G., Belotti, P.: Rounding-based heuristics for nonconvex MINLPs. Math. Program. Comput. 4(1), 1–31 (2012)
Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19(4), 534–541 (2007)
Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6, 445–454 (1994)
SBB. ARKI Consulting & Development A/S and GAMS Inc. http://www.gams.com/solvers/solvers.htm#SBB
SCIP. Solving Constraint Integer Programs. http://scip.zib.de/
SoPlex. An open source LP solver implementing the revised simplex algorithm. http://soplex.zib.de/
Tawarmalani, M., Sahinidis, N.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Program. 99, 563–591 (2004)
Vigerske, S.: Decomposition in Multistage Stochastic Programming and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming. PhD thesis, Humboldt-Universität zu Berlin (2013)
Wächter, A., Biegler, L.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)
Wallace, C.: ZI round, a MIP rounding heuristic. J. Heuristics 16(5), 715–722 (2010)
Wolsey, L.A.: Faces for a linear inequality in 0–1 variables. Math. Program. 8, 165–178 (1975)
Wunderling, R.: Paralleler und objektorientierter Simplex-Algorithmus. PhD thesis, Technische Universität Berlin (1996)
Acknowledgments
Many thanks go to Ambros M. Gleixner and Daniel E. Steffy for their thorough proof-reading and to two anonymous reviewers for their helpful comments. This research has been supported by the DFG Research Center Matheon Mathematics for key technologies in Berlin.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Berthold, T. RENS. Math. Prog. Comp. 6, 33–54 (2014). https://doi.org/10.1007/s12532-013-0060-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12532-013-0060-9
Keywords
- Mixed integer programming
- Mixed integer nonlinear programming
- Primal heuristic
- Large neighborhood search
- Rounding