IDEAS home Printed from https://ideas.repec.org/a/spr/topjnl/v23y2015i2p591-616.html
   My bibliography  Save this article

Deterministic upper bounds for spatial branch-and-bound methods in global minimization with nonconvex constraints

Author

Listed:
  • Peter Kirst
  • Oliver Stein
  • Paul Steuermann

Abstract

We discuss some difficulties in determining valid upper bounds in spatial branch-and-bound methods for global minimization in the presence of nonconvex constraints. In fact, two examples illustrate that standard techniques for the construction of upper bounds may fail in this setting. Instead, we propose to perturb infeasible iterates along Mangasarian–Fromovitz directions to feasible points whose objective function values serve as upper bounds. These directions may be calculated by the solution of a single linear optimization problem per iteration. Preliminary numerical results indicate that our enhanced algorithm solves optimization problems where a standard branch-and-bound method does not converge to the correct optimal value. Copyright Sociedad de Estadística e Investigación Operativa 2015

Suggested Citation

  • Peter Kirst & Oliver Stein & Paul Steuermann, 2015. "Deterministic upper bounds for spatial branch-and-bound methods in global minimization with nonconvex constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 591-616, July.
    • Handle: RePEc:spr:topjnl:v:23:y:2015:i:2:p:591-616
    DOI: 10.1007/s11750-015-0387-7
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s11750-015-0387-7
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11750-015-0387-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ralph Kearfott, 2014. "On rigorous upper bounds to a global optimum," Journal of Global Optimization, Springer, vol. 59(2), pages 459-476, July.
    2. Ruth Misener & Christodoulos Floudas, 2013. "GloMIQO: Global mixed-integer quadratic optimizer," Journal of Global Optimization, Springer, vol. 57(1), pages 3-50, September.
    3. Sonia Cafieri & Jon Lee & Leo Liberti, 2010. "On convex relaxations of quadrilinear terms," Journal of Global Optimization, Springer, vol. 47(4), pages 661-685, August.
    4. R. Misener & C. A. Floudas, 2010. "Piecewise-Linear Approximations of Multidimensional Functions," Journal of Optimization Theory and Applications, Springer, vol. 145(1), pages 120-147, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Peter Kirst & Fabian Rigterink & Oliver Stein, 2017. "Global optimization of disjunctive programs," Journal of Global Optimization, Springer, vol. 69(2), pages 283-307, October.
    2. Gabriele Eichfelder & Peter Kirst & Laura Meng & Oliver Stein, 2021. "A general branch-and-bound framework for continuous global multiobjective optimization," Journal of Global Optimization, Springer, vol. 80(1), pages 195-227, May.
    3. Gabriele Eichfelder & Kathrin Klamroth & Julia Niebling, 2021. "Nonconvex constrained optimization by a filtering branch and bound," Journal of Global Optimization, Springer, vol. 80(1), pages 31-61, May.
    4. Fengqiao Luo & Sanjay Mehrotra, 2021. "A geometric branch and bound method for robust maximization of convex functions," Journal of Global Optimization, Springer, vol. 81(4), pages 835-859, December.
    5. Gabriele Eichfelder & Oliver Stein & Leo Warnow, 2024. "A Solver for Multiobjective Mixed-Integer Convex and Nonconvex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 203(2), pages 1736-1766, November.
    6. Marendet, Antoine & Goldsztejn, Alexandre & Chabert, Gilles & Jermann, Christophe, 2020. "A standard branch-and-bound approach for nonlinear semi-infinite problems," European Journal of Operational Research, Elsevier, vol. 282(2), pages 438-452.
    7. Peter Kirst & Oliver Stein, 2019. "Global optimization of generalized semi-infinite programs using disjunctive programming," Journal of Global Optimization, Springer, vol. 73(1), pages 1-25, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Emily Speakman & Jon Lee, 2018. "On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation," Journal of Global Optimization, Springer, vol. 72(2), pages 129-153, October.
    2. Boukouvala, Fani & Misener, Ruth & Floudas, Christodoulos A., 2016. "Global optimization advances in Mixed-Integer Nonlinear Programming, MINLP, and Constrained Derivative-Free Optimization, CDFO," European Journal of Operational Research, Elsevier, vol. 252(3), pages 701-727.
    3. Codas, Andrés & Camponogara, Eduardo, 2012. "Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing," European Journal of Operational Research, Elsevier, vol. 217(1), pages 222-231.
    4. Martin Ballerstein & Dennis Michaels, 2014. "Extended formulations for convex envelopes," Journal of Global Optimization, Springer, vol. 60(2), pages 217-238, October.
    5. Emily Speakman & Jon Lee, 2017. "Quantifying Double McCormick," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 1230-1253, November.
    6. Wei Xia & Juan C. Vera & Luis F. Zuluaga, 2020. "Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 40-56, January.
    7. Yanchao Liu, 2019. "A Progressive Motion-Planning Algorithm and Traffic Flow Analysis for High-Density 2D Traffic," Transportation Science, INFORMS, vol. 53(6), pages 1501-1525, November.
    8. Michelle L. Blom & Christina N. Burt & Adrian R. Pearce & Peter J. Stuckey, 2014. "A Decomposition-Based Heuristic for Collaborative Scheduling in a Network of Open-Pit Mines," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 658-676, November.
    9. Kazda, Kody & Li, Xiang, 2024. "A linear programming approach to difference-of-convex piecewise linear approximation," European Journal of Operational Research, Elsevier, vol. 312(2), pages 493-511.
    10. Wu, Yaqing & Maravelias, Christos T., 2024. "Piecewise linear trees as surrogate models for system design and planning under high-frequency temporal variability," European Journal of Operational Research, Elsevier, vol. 315(2), pages 541-552.
    11. Steffen Rebennack & Vitaliy Krasko, 2020. "Piecewise Linear Function Fitting via Mixed-Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 507-530, April.
    12. Pete Janes & Alistair Rendell, 2013. "Deterministic global optimization in ab-initio quantum chemistry," Journal of Global Optimization, Springer, vol. 56(2), pages 537-558, June.
    13. Jean Lasserre & Tung Thanh, 2013. "Convex underestimators of polynomials," Journal of Global Optimization, Springer, vol. 56(1), pages 1-25, May.
    14. Ralph Kearfott, 2015. "Some observations on exclusion regions in branch and bound algorithms," Journal of Global Optimization, Springer, vol. 62(2), pages 229-241, June.
    15. Miten Mistry & Dimitrios Letsios & Gerhard Krennrich & Robert M. Lee & Ruth Misener, 2021. "Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1103-1119, July.
    16. Harsha Nagarajan & Mowen Lu & Site Wang & Russell Bent & Kaarthik Sundar, 2019. "An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs," Journal of Global Optimization, Springer, vol. 74(4), pages 639-675, August.
    17. Pantelis Broukos & Antonios Fragkogios & Nilay Shah, 2022. "A Linearized Mathematical Formulation for Combined Centralized and Distributed Waste Water Treatment Network Design," SN Operations Research Forum, Springer, vol. 3(3), pages 1-29, September.
    18. Xie, Shiwei & Hu, Zhijian & Wang, Jueying, 2020. "Two-stage robust optimization for expansion planning of active distribution systems coupled with urban transportation networks," Applied Energy, Elsevier, vol. 261(C).
    19. Ignacio Araya & Victor Reyes, 2016. "Interval Branch-and-Bound algorithms for optimization and constraint satisfaction: a survey and prospects," Journal of Global Optimization, Springer, vol. 65(4), pages 837-866, August.
    20. Schäffer, Linn Emelie & Helseth, Arild & Korpås, Magnus, 2022. "A stochastic dynamic programming model for hydropower scheduling with state-dependent maximum discharge constraints," Renewable Energy, Elsevier, vol. 194(C), pages 571-581.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:topjnl:v:23:y:2015:i:2:p:591-616. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.