IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v73y2019i4d10.1007_s10898-018-0728-9.html
   My bibliography  Save this article

Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming

Author

Listed:
  • Tiago Andrade

    (Pontifícia Universidade Católica do Rio de Janeiro (Puc-Rio) R. Marquês de São Vicente)

  • Fabricio Oliveira

    (Aalto University)

  • Silvio Hamacher

    (Pontifícia Universidade Católica do Rio de Janeiro (Puc-Rio) R. Marquês de São Vicente)

  • Andrew Eberhard

    (RMIT University)

Abstract

We propose methods for improving the relaxations obtained by the normalized multiparametric disaggregation technique (NMDT). These relaxations constitute a key component for some methods for solving nonconvex mixed-integer quadratically constrained quadratic programming (MIQCQP) problems. It is shown that these relaxations can be more efficiently formulated by significantly reducing the number of auxiliary variables (in particular, binary variables) and constraints. Moreover, a novel algorithm for solving MIQCQP problems is proposed. It can be applied using either its original NMDT or the proposed reformulation. Computational experiments are performed using both benchmark instances from the literature and randomly generated instances. The numerical results suggest that the proposed techniques can improve the quality of the relaxations.

Suggested Citation

  • Tiago Andrade & Fabricio Oliveira & Silvio Hamacher & Andrew Eberhard, 2019. "Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming," Journal of Global Optimization, Springer, vol. 73(4), pages 701-722, April.
    • Handle: RePEc:spr:jglopt:v:73:y:2019:i:4:d:10.1007_s10898-018-0728-9
    DOI: 10.1007/s10898-018-0728-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-018-0728-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-018-0728-9?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. João Teles & Pedro Castro & Henrique Matos, 2013. "Multi-parametric disaggregation technique for global optimization of polynomial programming problems," Journal of Global Optimization, Springer, vol. 55(2), pages 227-251, February.
    2. R. C. Jeroslow, 1973. "There Cannot be any Algorithm for Integer Programming with Quadratic Constraints," Operations Research, INFORMS, vol. 21(1), pages 221-224, February.
    3. Scott Kolodziej & Pedro Castro & Ignacio Grossmann, 2013. "Global optimization of bilinear programs with a multiparametric disaggregation technique," Journal of Global Optimization, Springer, vol. 57(4), pages 1039-1063, December.
    4. Lakshman S. Thakur, 1991. "Domain Contraction in Nonlinear Programming: Minimizing a Quadratic Concave Objective Over a Polyhedron," Mathematics of Operations Research, INFORMS, vol. 16(2), pages 390-407, May.
    5. Li, Han-Lin & Chang, Ching-Ter, 1998. "An approximate approach of global optimization for polynomial programming problems," European Journal of Operational Research, Elsevier, vol. 107(3), pages 625-632, June.
    6. Marcia Fampa & Jon Lee & Wendel Melo, 2017. "On global optimization with indefinite quadratics," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 309-337, September.
    7. Bomze, Immanuel M., 2012. "Copositive optimization – Recent developments and applications," European Journal of Operational Research, Elsevier, vol. 216(3), pages 509-520.
    8. Faiz A. Al-Khayyal & James E. Falk, 1983. "Jointly Constrained Biconvex Programming," Mathematics of Operations Research, INFORMS, vol. 8(2), pages 273-286, May.
    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. Tiago Andrade & Nikita Belyak & Andrew Eberhard & Silvio Hamacher & Fabricio Oliveira, 2022. "The p-Lagrangian relaxation for separable nonconvex MIQCQP problems," Journal of Global Optimization, Springer, vol. 84(1), pages 43-76, September.
    2. Immanuel M. Bomze & Bo Peng, 2023. "Conic formulation of QPCCs applied to truly sparse QPs," Computational Optimization and Applications, Springer, vol. 84(3), pages 703-735, April.

    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. Teles, João P. & Castro, Pedro M. & Matos, Henrique A., 2013. "Univariate parameterization for global optimization of mixed-integer polynomial problems," European Journal of Operational Research, Elsevier, vol. 229(3), pages 613-625.
    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. Marcia Fampa & Jon Lee, 2021. "Convexification of bilinear forms through non-symmetric lifting," Journal of Global Optimization, Springer, vol. 80(2), pages 287-305, June.
    4. Natashia Boland & Thomas Kalinowski & Fabian Rigterink, 2016. "New multi-commodity flow formulations for the pooling problem," Journal of Global Optimization, Springer, vol. 66(4), pages 669-710, December.
    5. Jianhui Xie & Qiwei Xie & Yongjun Li & Liang Liang, 2021. "Solving data envelopment analysis models with sum-of-fractional objectives: a global optimal approach based on the multiparametric disaggregation technique," Annals of Operations Research, Springer, vol. 304(1), pages 453-480, September.
    6. Pedro Castro & Ignacio Grossmann, 2014. "Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems," Journal of Global Optimization, Springer, vol. 59(2), pages 277-306, July.
    7. Radu Baltean-Lugojan & Ruth Misener, 2018. "Piecewise parametric structure in the pooling problem: from sparse strongly-polynomial solutions to NP-hardness," Journal of Global Optimization, Springer, vol. 71(4), pages 655-690, August.
    8. Enayati, Shakiba & Özaltın, Osman Y., 2020. "Optimal influenza vaccine distribution with equity," European Journal of Operational Research, Elsevier, vol. 283(2), pages 714-725.
    9. Xin Cheng & Xiang Li, 2022. "Discretization and global optimization for mixed integer bilinear programming," Journal of Global Optimization, Springer, vol. 84(4), pages 843-867, December.
    10. N. V. Thoai, 2000. "Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints," Journal of Optimization Theory and Applications, Springer, vol. 107(2), pages 331-354, November.
    11. R. Cambini & R. Riccardi & D. Scopelliti, 2023. "Solving linear multiplicative programs via branch-and-bound: a computational experience," Computational Management Science, Springer, vol. 20(1), pages 1-32, December.
    12. Evrim Dalkiran & Hanif Sherali, 2013. "Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality," Journal of Global Optimization, Springer, vol. 57(4), pages 1147-1172, December.
    13. 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.
    14. Wong, Man Hong & Zhang, Shuzhong, 2014. "On distributional robust probability functions and their computations," European Journal of Operational Research, Elsevier, vol. 233(1), pages 23-33.
    15. 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.
    16. 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.
    17. Bomze, Immanuel M. & Gabl, Markus, 2023. "Optimization under uncertainty and risk: Quadratic and copositive approaches," European Journal of Operational Research, Elsevier, vol. 310(2), pages 449-476.
    18. Keith Zorn & Nikolaos Sahinidis, 2014. "Global optimization of general nonconvex problems with intermediate polynomial substructures," Journal of Global Optimization, Springer, vol. 59(2), pages 673-693, July.
    19. Ngueveu, Sandra Ulrich, 2019. "Piecewise linear bounding of univariate nonlinear functions and resulting mixed integer linear programming-based solution methods," European Journal of Operational Research, Elsevier, vol. 275(3), pages 1058-1071.
    20. Tsao, Yu-Chung & Lu, Jye-Chyi & An, Na & Al-Khayyal, Faiz & Lu, Richard W. & Han, Guanghua, 2014. "Retailer shelf-space management with trade allowance: A Stackelberg game between retailer and manufacturers," International Journal of Production Economics, Elsevier, vol. 148(C), pages 133-144.

    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:jglopt:v:73:y:2019:i:4:d:10.1007_s10898-018-0728-9. 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.