×

zbMATH — the first resource for mathematics

Guided dive for the spatial branch-and-bound. (English) Zbl 1379.90028
Summary: We study the spatial Brand-and-Bound algorithm for the global optimization of nonlinear problems. In particular we are interested in a method to find quickly good feasible solutions. Most spatial Branch-and-Bound-based solvers use a non-global solver at a few nodes to try to find better incumbents. We show that it is possible to improve the branching rules and the node priority by exploiting the solutions from the non-global solver. We also propose several smart adaptive strategies to choose when to run the non-global solver. We show that despite the time spent in solving more NLP problems in the nodes, the new strategies enable the algorithm to find the first good incumbents faster and to prove the global optimality faster. Numerous easy, medium size as well as hard NLP instances from the Coconut library are benchmarked. All experiments are run using the open source solver Couenne.
MSC:
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abichandani, P., Benson, H.Y., Kam, M.: Multi-vehicle path coordination under communication constraints. In: Proceedings of the American Control Conference, pp. 650-656 (2008)
[2] Adjiman, C.S., Dallwig, S., Floudas, C.A., Neumaier, A.: A global optimization method, alpha BB, for general twice-differentiable constrained NLPs-I. Theoretical advances. Comput. Chem. Eng. 22, 1137-1158 (1998) · Zbl 1035.90063
[3] 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) · Zbl 1179.90237
[4] Berthold, T.: Rens-relaxation enforced neighborhood search. Technical Report 07-28, ZIB, Berlin (2007) · Zbl 1099.90047
[5] Berthold, T., Gamrath, G., Gleixner, A.M., Heinz, S., Koch, T., Shinano, Y.: Solving mixed integer linear and nonlinear problems using the SCIP optimization suite. Technical Report 12-27, ZIB (2012)
[6] Biegler, L.: Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes. MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics. SIAM, Pittsburgh (2010) · Zbl 1207.90004
[7] Biegler, L.T.: Efficient nonlinear programming algorithms for chemical process control and operations. In: System Modeling and Optimization: 23rd IFIP TC 7 Conference, Cracow, Poland, 23-27 July 2007, Revised Selected Papers, pp. 21-35. Springer, Berlin (2009)
[8] Boggs, PT; Tolle, JW, Sequential quadratic programming, Acta Numer., 4, 1-51, (1995) · Zbl 0828.65060
[9] Byrd, RH; Schnabel, RB; Shultz, GA, A trust region algorithm for nonlinearly constrained optimization, SIAM J. Numer. Anal., 24, 1152-1170, (1987) · Zbl 0631.65068
[10] Chung, TT; Sun, TC, Weight optimization for flexural reinforced concrete beams with static nonlinear response, Struct. optim., 8, 174-180, (1994)
[11] Costa-Montenegro, E., González-Castaño, F.J., Rodríguez-Hernández, P.S., Burguillo-Rial, J.C.: Nonlinear optimization of IEEE 802.11 mesh networks. In: Computational Science—ICCS 2007: 7th International Conference, Beijing, China, 27-30 May 2007, Proceedings, Part IV, pp. 466-473. Springer, Berlin (2007) · Zbl 1177.90325
[12] Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71-91 (2005) · Zbl 1131.90036
[13] Donde, V., Lopez, V., Lesieutre, B., Pinar, A., Yang, C., Meza, J.: Identification of severe multiple contingencies in electric power networks. In: Power Symposium, 2005. Proceedings of the 37th Annual North American, pp. 59-66 (2005) · Zbl 1301.90063
[14] Fiacco, A.V., McCormick, G.P.: Nonlinear Programming; Sequential Unconstrained Minimization Techniques. Wiley, New York (1968) · Zbl 0193.18805
[15] Fielding, C.: Advanced Techniques for Clearance of Flight Control Laws. Volume 283 of Engineering Online Library. Springer, New York (2002) · Zbl 1001.93003
[16] Fischetti, M; Lodi, A, Local branching, Math. Program., 98, 23-47, (2003) · Zbl 1060.90056
[17] Fletcher, R; Leyffer, S, Nonlinear programming without a penalty function, Math. Program., 91, 239-269, (2002) · Zbl 1049.90088
[18] Fügenschuh, A; Herty, M; Klar, A; Martin, A, Combinatorial and continuous models for the optimization of traffic flows on networks, SIAM J. Optim., 16, 1155-1176, (2006) · Zbl 1131.90015
[19] Gatzke, EP; Tolsma, JE; Barton, PI, Construction of convex relaxations using automated code generation techniques, Optim. Eng., 3, 305-326, (2002) · Zbl 1035.90063
[20] Gebreslassie, BH; Slivinsky, M; Wang, B; You, F, Life cycle optimization for sustainable design and operations of hydrocarbon biorefinery via fast pyrolysis, hydrotreating and hydrocracking, Comput. Chem. Eng., 50, 71-91, (2013)
[21] Gentilini, I; Margot, F; Shimada, K, The travelling salesman problem with neighbourhoods: MINLP solution, Optim. Methods Softw., 28, 364-378, (2013) · Zbl 1270.90055
[22] Isshiki, M., Sinclair, D., Kaneko, S.: Lens design: global optimization of both performance and tolerance sensitivity. In: International Optical Design. Optical Society of America, Vancouver (2006) · Zbl 1060.90056
[23] Jackson, J.R., Hofmann, J., Wassick, J., Grossmann, I.E.: A nonlinear multiperiod process optimization model for production planning in multi-plant facilities. In: Proceedings FOCAPO 2003, pp. 281-284 (2003) · Zbl 0631.65068
[24] Karuppiah, R., Grossmann, I.E.: Global optimization for the synthesis of integrated water systems in chemical processes. Comput. Chem. Eng. 30, 650-673 (2006) · Zbl 1257.90059
[25] Liberti, L., Nannicini, G., Mladenović, N.: A good recipe for solving MINLPs. In: Maniezzo, V., Stützle, T., Voß, S. (eds.) Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, pp. 231-244. Springer, Boston (2010) · Zbl 1049.90088
[26] Lin, Y; Schrage, L, The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668, (2009) · Zbl 1177.90325
[27] Misener, R; Floudas, CA, Antigone: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063
[28] Mladenović, N., Hanse, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097-1100 (1997) · Zbl 1301.90063
[29] Momoh, J.A., Koessler, R.J., Bond, M.S., Stott, B., Sun, D., Papalexopoulos, A., Ristanovic, P.: Challenges to optimal power flow. IEEE Trans. Power Syst. 12(1), 444-455 (1997)
[30] Nannicini, G; Belotti, P, Rounding-based heuristics for nonconvex minlps, Math. Program. Comput., 4, 1-31, (2012) · Zbl 1257.90059
[31] Nannicini, G., Belotti, P., Liberti, L.: A local branching heuristic for MINLPs. Tech. Rep. 0812.2188. arXiv:0812.2188 (2008) · Zbl 0631.65068
[32] Nesterov, Y., Nemirovski, A.: Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics, Society for Industrial and Applied Mathematics Philadelphia (1994)
[33] Neumaier, A, Complete search in continuous global optimization and constraint satisfaction, Acta Numer., 13, 271-369, (2004) · Zbl 1113.90124
[34] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[35] Pfetsch, M.E., Fügenschuh, A., Geis̈ler, B., Geis̈ler, N., Gollmer, R., Hiller, B., Humpola, J., Koch, T., Lehmann, T., Martin, A., Morsi, A., Rövekamp, J., Schewe, L., Schmidt, M., Schultz, R., Schwarz, R., Schweiger, J., Stangl, C., Steinbach, M.C., Vigerske, S., Willert, B.M.: Validation of nominations in gas network optimization: models, methods, and solutions. Optim. Methods Softw. 30(1), 15-53 (2015) · Zbl 1325.90019
[36] Quist, A.J., van Geemert, R., Hoogenboom, J.E., Illés, T., Roos, C., Terlaky, T.: Application of nonlinear optimization to reactor core fuel reloading. Ann. Nucl. Energy 26(5), 423-448 (1999)
[37] Raghunathan, AU; Gopal, V; Subramanian, D; Biegler, LT; Samad, T, Dynamic optimization strategies for three-dimensional conflict resolution of multiple aircraft, J. Guid. Control Dyn., 27, 586-594, (2004)
[38] Smith, E.M.B., Pantelides, C.C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23(4-5), 457-478 (1999) · Zbl 1179.90237
[39] Soleimanipour, M., Zhuang, W., Freeman, G.H.: Optimal resource management in wireless multimedia wideband CDMA systems. IEEE Trans. Mob. Comput. 1(2), 143-160 (2002) · Zbl 1049.90088
[40] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Nonconvex Optimization and Its Applications. Springer (2002) · Zbl 1031.90022
[41] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.