IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i6p3117-3133.html
   My bibliography  Save this article

A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems

Author

Listed:
  • Marianna De Santis

    (Dipartimento di Ingegneria informatica automatica e gestionale Antonio Ruberti, Sapienza Università di Roma, 00185 Roma, Italy)

  • Sven de Vries

    (Department of Mathematics, Trier University, 54296 Trier, Germany)

  • Martin Schmidt

    (Department of Mathematics, Trier University, 54296 Trier, Germany)

  • Lukas Winkel

    (Department of Mathematics, Trier University, 54296 Trier, Germany)

Abstract

Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations and also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well-studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, almost no tailored algorithms are known besides reformulations of the problem that allow us to apply general purpose mixed integer linear programming solvers. In this paper, we present, theoretically analyze, enhance, and test a novel branch-and-bound method for MILCPs. The main property of this method is that we do not “branch” on constraints as usual but by adding suitably chosen penalty terms to the objective function. By doing so, we can either provably compute an MILCP solution if one exists or compute an approximate solution that minimizes an infeasibility measure combining integrality and complementarity conditions. We enhance the method by MILCP-tailored valid inequalities, node selection strategies, branching rules, and warm-starting techniques. The resulting algorithm is shown to clearly outperform two benchmark approaches from the literature.

Suggested Citation

  • Marianna De Santis & Sven de Vries & Martin Schmidt & Lukas Winkel, 2022. "A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3117-3133, November.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:6:p:3117-3133
    DOI: 10.1287/ijoc.2022.1216
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1216
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1216?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
    ---><---

    References listed on IDEAS

    as
    1. William H. Cunningham & James F. Geelen, 1998. "Integral Solutions of Linear Complementarity Problems," Mathematics of Operations Research, INFORMS, vol. 23(1), pages 61-68, February.
    2. Marianna De Santis & Stefano Lucidi & Francesco Rinaldi, 2013. "A new class of functions for measuring solution integrality in the Feasibility Pump approach: Complete Results," DIAG Technical Reports 2013-05, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    3. W. X. Zhu, 2003. "Penalty Parameter for Linearly Constrained 0–1 Quadratic Programming," Journal of Optimization Theory and Applications, Springer, vol. 116(1), pages 229-239, January.
    4. Steven Gabriel & Sauleh Siddiqui & Antonio Conejo & Carlos Ruiz, 2013. "Solving Discretely-Constrained Nash–Cournot Games with an Application to Power Markets," Networks and Spatial Economics, Springer, vol. 13(3), pages 307-326, September.
    5. R. Chandrasekaran & S. N. Kabadi & R. Sridhar, 1998. "Integer Solution for Linear Complementarity Problem," Mathematics of Operations Research, INFORMS, vol. 23(2), pages 390-402, May.
    6. Richard Weinhold & Steven A. Gabriel, 2020. "Discretely constrained mixed complementary problems: Application and analysis of a stylised electricity market," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 71(2), pages 237-249, February.
    7. S. Lucidi & F. Rinaldi, 2010. "Exact Penalty Functions for Nonlinear Integer Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 145(3), pages 479-488, June.
    Full references (including those not matched with items on IDEAS)

    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. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2005. "Computing Integral Solutions of Complementarity Problems," Other publications TiSEM b8e0c74e-2219-4ab0-99a2-0, Tilburg University, School of Economics and Management.
    2. Ma, Cheng & Zhang, Liansheng, 2015. "On an exact penalty function method for nonlinear mixed discrete programming problems and its applications in search engine advertising problems," Applied Mathematics and Computation, Elsevier, vol. 271(C), pages 642-656.
    3. Hanna Sumita & Naonori Kakimura & Kazuhisa Makino, 2015. "The Linear Complementarity Problems with a Few Variables per Constraint," Mathematics of Operations Research, INFORMS, vol. 40(4), pages 1015-1026, October.
    4. Hanna Sumita & Naonori Kakimura & Kazuhisa Makino, 2019. "Total dual integrality of the linear complementarity problem," Annals of Operations Research, Springer, vol. 274(1), pages 531-553, March.
    5. Dimitri J. Papageorgiou & Francisco Trespalacios & Stuart Harwood, 2021. "A Note on Solving Discretely-Constrained Nash-Cournot Games via Complementarity," Networks and Spatial Economics, Springer, vol. 21(2), pages 325-330, June.
    6. Zaifu Yang, 2008. "On the Solutions of Discrete Nonlinear Complementarity and Related Problems," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 976-990, November.
    7. M. Santis & F. Rinaldi, 2012. "Continuous Reformulations for Zero–One Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 153(1), pages 75-84, April.
    8. Dávid Csercsik & László Á. Kóczy, 2017. "Efficiency and Stability in Electrical Power Transmission Networks: a Partition Function Form Approach," Networks and Spatial Economics, Springer, vol. 17(4), pages 1161-1184, December.
    9. Hassan Shavandi & Mehrdad Pirnia & J. David Fuller, 2018. "Extended opportunity cost model to find near equilibrium electricity prices under non-convexities," Papers 1809.09734, arXiv.org.
    10. Dávid Csercsik, 2016. "Competition and Cooperation in a Bidding Model of Electrical Energy Trade," Networks and Spatial Economics, Springer, vol. 16(4), pages 1043-1073, December.
    11. Olufolajimi Oke & Daniel Huppmann & Max Marshall & Ricky Poulton & Sauleh Siddiqui, 2019. "Multimodal Transportation Flows in Energy Networks with an Application to Crude Oil Markets," Networks and Spatial Economics, Springer, vol. 19(2), pages 521-555, June.
    12. Filippo Fabiani & Barbara Franci, 2023. "On Distributionally Robust Generalized Nash Games Defined over the Wasserstein Ball," Journal of Optimization Theory and Applications, Springer, vol. 199(1), pages 298-309, October.
    13. Meijia Han & Wenxing Zhu, 2023. "Nonnegative partial s-goodness for the equivalence of a 0-1 linear program to weighted linear programming," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-37, July.
    14. Massimo De Mauri & Joris Gillis & Jan Swevers & Goele Pipeleers, 2020. "A proximal-point outer approximation algorithm," Computational Optimization and Applications, Springer, vol. 77(3), pages 755-777, December.
    15. Dimitri J. Papageorgiou & Francisco Trespalacios & Stuart Harwood, 2020. "A Note on Solving Discretely-Constrained Nash-Cournot Games via Complementarity," Papers 2003.01536, arXiv.org.
    16. Löschenbrand, Markus, 2020. "Finding multiple Nash equilibria via machine learning-supported Gröbner bases," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1178-1189.
    17. Marianna De Santis & Stefano Lucidi & Francesco Rinaldi, 2013. "A new class of functions for measuring solution integrality in the Feasibility Pump approach: Complete Results," DIAG Technical Reports 2013-05, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    18. Guastaroba, G. & Savelsbergh, M. & Speranza, M.G., 2017. "Adaptive Kernel Search: A heuristic for solving Mixed Integer linear Programs," European Journal of Operational Research, Elsevier, vol. 263(3), pages 789-804.
    19. Hesamzadeh, M. & Holmberg, P. & Sarfati, M., 2018. "Simulation and Evaluation of Zonal Electricity Market Designs," Cambridge Working Papers in Economics 1829, Faculty of Economics, University of Cambridge.
    20. Dominik Garmatter & Margherita Porcelli & Francesco Rinaldi & Martin Stoll, 2023. "An improved penalty algorithm using model order reduction for MIPDECO problems with partial observations," Computational Optimization and Applications, Springer, vol. 84(1), pages 191-223, January.

    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:inm:orijoc:v:34:y:2022:i:6:p:3117-3133. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.