Guided Dive for the Spatial Branch-and-Bound

Gerard, Damien; Koeppe, Matthias; Louveaux, Quentin

doi:10.1007/s10898-017-0503-3

Download

Article (Scientific journals)

Guided Dive for the Spatial Branch-and-Bound

Gerard, Damien; Koeppe, Matthias; Louveaux, Quentin

2017 • In Journal of Global Optimization

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/208826

DOI
10.1007/s10898-017-0503-3

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

GuidedDiveFinal.pdf

Author postprint (974.88 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

spatial branch-and-bound; local search; globall optimization

Abstract :

[en] We study the spatial Brand-and-Bound algorithm for the global opti- mization 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 opti- mality 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.

Disciplines :

Computer science

Author, co-author :

Gerard, Damien ; Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)

Koeppe, Matthias; University of California, Davis - UC Davis > Department of Mathematics

Louveaux, Quentin ; Université de Liège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation : Optimisation discrète

Language :

English

Title :

Guided Dive for the Spatial Branch-and-Bound

Publication date :

2017

Journal title :

Journal of Global Optimization

ISSN :

0925-5001

eISSN :

1573-2916

Publisher :

Springer

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 30 March 2017

Statistics

Number of views

101 (15 by ULiège)

Number of downloads

489 (13 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

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)
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)
Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4–5), 597–634 (2009)
Berthold, T.: Rens-relaxation enforced neighborhood search. Technical Report 07–28, ZIB, Berlin (2007)
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)
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)
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)
Boggs, P.T., Tolle, J.W.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1995)
Byrd, R.H., Schnabel, R.B., Shultz, G.A.: A trust region algorithm for nonlinearly constrained optimization. SIAM J. Numer. Anal. 24(5), 1152–1170 (1987)
Chung, T.T., Sun, T.C.: Weight optimization for flexural reinforced concrete beams with static nonlinear response. Struct. optim. 8(2), 174–180 (1994)
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)
Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71–91 (2005)
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)
Fiacco, A.V., McCormick, G.P.: Nonlinear Programming; Sequential Unconstrained Minimization Techniques. Wiley, New York (1968)
Fielding, C.: Advanced Techniques for Clearance of Flight Control Laws. Volume 283 of Engineering Online Library. Springer, New York (2002)
Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1), 23–47 (2003)
Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Program. 91(2), 239–269 (2002)
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(4), 1155–1176 (2006)
Gatzke, E.P., Tolsma, J.E., Barton, P.I.: Construction of convex relaxations using automated code generation techniques. Optim. Eng. 3(3), 305–326 (2002)
Gebreslassie, B.H., 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)
Gentilini, I., Margot, F., Shimada, K.: The travelling salesman problem with neighbourhoods: MINLP solution. Optim. Methods Softw. 28(2), 364–378 (2013)
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)
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)
Karuppiah, R., Grossmann, I.E.: Global optimization for the synthesis of integrated water systems in chemical processes. Comput. Chem. Eng. 30, 650–673 (2006)
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)
Lin, Y., Schrage, L.: The global solver in the LINDO API. Optim. Methods Softw. 24(4–5), 657–668 (2009)
Misener, R., Floudas, C.A.: Antigone: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2–3), 503–526 (2014)
Mladenović, N., Hanse, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)
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)
Nannicini, G., Belotti, P.: Rounding-based heuristics for nonconvex MINLPs. Math. Program. Comput. 4(1), 1–31 (2012)
Nannicini, G., Belotti, P., Liberti, L.: A local branching heuristic for MINLPs. Tech. Rep. 0812.2188. arXiv:0812.2188 (2008)
Nesterov, Y., Nemirovski, A.: Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics, Society for Industrial and Applied Mathematics Philadelphia (1994)
Neumaier, A.: Complete search in continuous global optimization and constraint satisfaction. Acta Numer. 13, 271–369 (2004)
Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006)
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)
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)
Raghunathan, A.U., Gopal, V., Subramanian, D., Biegler, L.T., Samad, T.: Dynamic optimization strategies for three-dimensional conflict resolution of multiple aircraft. J. Guid. Control Dyn. 27(4), 586–594 (2004)
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)
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)
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)
Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)