A Heuristic for Complementarity Problems Using Difference of Convex Functions

References

• Ahmed S, Xie W (2018) Relaxations and approximations of chance constraints under finite distributions. Math. Programming 170(1):43–65.Crossref, Google Scholar
• An LTH, Tao PD (2005) The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133(1):23–46.Crossref, Google Scholar
• ApS M (2019) MOSEK Optimization Suite, Version 8.1. Manual (MOSEK ApS, Copenhagen).Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• Bonami P, Lejeune MA (2009) An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Oper. Res. 57(3):650–670.Link, Google Scholar
• Boyd N (2024) Equilibrium programming for improved management of water-resource systems. PhD thesis, University of Maryland, College Park, MD.Google Scholar
• Bynum ML, Hackebeil GA, Hart WE, Laird CD, Nicholson BL, Siirola JD, Watson J-P, et al.. (2021) Pyomo–Optimization Modeling in Python, 3rd ed., vol. 67 (Springer Science & Business Media, New York).Crossref, Google Scholar
• Byong-Hun A (1983) Iterative methods for linear complementarity problems with upper bounds on primary variables. Math. Programming 26(3):295–315.Crossref, Google Scholar
• Cafieri S, D’Apuzzo M, Marino M, Mucherino A, Toraldo G (2006) Interior-point solver for large-scale quadratic programming problems with bound constraints. J. Optim. Theory Appl. 129(1):55–75.Crossref, Google Scholar
• Conejo AJ, Carrión M, Morales JM, et al. (2010) Decision Making Under Uncertainty in Electricity Markets, vol. 1 (Springer, New York).Crossref, Google Scholar
• Constante-Flores G, Conejo A, Constante-Flores S (2022) Solving certain complementarity problems in power markets via convex programming. TOP 30(1):1–27.Google Scholar
• Cottle RW, Pang J-S, Stone RE (2009) The Linear Complementarity Problem (SIAM, Philadelphia).Crossref, Google Scholar
• de Oliveira W (2020) The ABC of DC programming. Set Valued Variance Anal. 28(3):679–706.Crossref, Google Scholar
• Dinh Tao P, Le An TH (1997) Convex analysis approach to D.C. programming: Theory, algorithms and applications. Acta Math. Vietnam 22(1):289–355.Google Scholar
• Dirkse SP, Ferris MC (1995) The PATH solver: A nommonotone stabilization scheme for mixed complementarity problems. Optim. Methods Software 5(2):123–156.Crossref, Google Scholar
• Fathi Y (1979) Computational complexity of LCPs associated with positive definite symmetric matrices. Math. Programming 17(3):335–344.Crossref, Google Scholar
• Ferris MC, Munson TS (1999) Interfaces to PATH 3.0: Design, implementation and usage. Computational Optimization: A Tribute to Olvi Mangasarian Volume I. (Kluwer Academic Publishers, Boston), 207–227.Crossref, Google Scholar
• Fletcher R, Leyffer S (2004) Solving mathematical programs with equilibrium constraints as nonlinear programs. Optim. Methods Software 19(1):15–40.Crossref, Google Scholar
• Floudas CA (1995) Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications (Oxford University Press, New York).Crossref, Google Scholar
• Gabriel SA (2017) Solving discretely constrained mixed complementarity problems using a median function. Optim. Engrg. 18(3):631–658.Crossref, Google Scholar
• Gabriel SA, García-Bertrand R, Sahakij P, Conejo AJ (2006) A practical approach to approximate bilinear functions in mathematical programming problems by using Schur’s decomposition and SOS type 2 variables. J. Oper. Res. Soc. 57(8):995–1004.Crossref, Google Scholar
• Gabriel SA, Conejo AJ, Fuller JD, Hobbs BF, Ruiz C (2012) Complementarity Modeling in Energy Markets, vol. 180 (Springer Science & Business Media, New York).Google Scholar
• Gabriel SA, Flocco D, Boomsma TK, Schmidt M, Lejeune MA (2025a) A heuristic for complementarity problems using difference of convex functions. https://doi.org/10.1287/ijoc.2024.0822.cd, https://github.com/INFORMSJoC/2024.0822.Google Scholar
• Gabriel SA, Flocco DC, Mazzini FF, Sotelo D, Castor KdS, Levorato M (2025b) Theoretical results for gas market equilibrium modeling with application to Brazil. Comput. Management Sci. 22(1):2–25. Crossref, Google Scholar
• Geiger C, Kanzow C (1996) On the resolution of monotone complementarity problems. Comput. Optim. Appl. 5(2):155–173.Crossref, Google Scholar
• Harker PT, Pang J-S (1990) Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Math. Programming 48(1–3):161–220.Crossref, Google Scholar
• Hart WE, Watson J-P, Woodruff DL (2011) Pyomo: Modeling and solving mathematical programs in Python. Math. Programming Comput. 3(3):219–260.Crossref, Google Scholar
• Hoai An LT, Tao PD, Nguyen Canh N, Van Thoai N (2009) DC programming techniques for solving a class of nonlinear bilevel programs. J. Global Optim. 44(1):313–337.Crossref, Google Scholar
• Jara-Moroni F, Pang J-S, Wächter A (2018) A study of the difference-of-convex approach for solving linear programs with complementarity constraints. Math. Programming 169(1):221–254.Crossref, Google Scholar
• Labbé M, Violin A (2013) Bilevel programming and price setting problems. 4OR 11(1):1–30.Crossref, Google Scholar
• Lampariello L, Neumann C, Ricci JM, Sagratella S, Stein O (2021) Equilibrium selection for multi-portfolio optimization. Eur. J. Oper. Res. 295(1):363–373.Crossref, Google Scholar
• Le Thi HA (2020) DC programming and DCA for supply chain and production management: State-of-the-art models and methods. Internat. J. Production Res. 58(20):6078–6114.Crossref, Google Scholar
• Le Thi HA, Dinh TP (2001) A continuous approach for globally solving linearly constrained quadratic. Optimization 50(1–2):93–120.Crossref, Google Scholar
• Le Thi HA, Pham Dinh T (2011) On solving linear complementarity problems by DC programming and DCA. Comput. Optim. Appl. 50(3):507–524.Crossref, Google Scholar
• Le Thi HA, Pham Dinh T (2018) DC programming and DCA: Thirty years of developments. Math. Programming 169(1):5–68.Crossref, Google Scholar
• Le Thi HA, Pham Dinh T (2023) Open issues and recent advances in DC programming and DCA. J. Global Optim. 88(3):533–590.Crossref, Google Scholar
• Le Thi HA, Ho VT, Pham Dinh T (2019) A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning. J. Global Optim. 73(2):279–310.Crossref, Google Scholar
• Le Thi HA, Huynh VN, Dinh TP (2014) DC programming and DCA for general DC programs. Proc. 2nd Internat. Conf. Comput. Sci. Appl. Math. Applications (ICCSAM 2014) (Springer, New York), 15–35.Google Scholar
• Le Thi HA, Nguyen TMT, Dinh TP (2023) On solving difference of convex functions programs with linear complementarity constraints. Comput. Optim. Appl. 86(1):163–197.Crossref, Google Scholar
• Lejeune M, Prékopa A (2018) Relaxations for probabilistically constrained stochastic programming problems: Review and extensions. Ann. Oper. Res. 271(1):1–22. Google Scholar
• Murty KG (1988) Linear complementarity. Linear and Nonlinear Programming (Heldermann Verlag, Berlin).Google Scholar
• Nguyen HN, Lisser A, Singh VV (2024) Random games under normal mean–variance mixture distributed independent linear joint chance constraints. Statist. Probability Lett. 208:110036.Crossref, Google Scholar
• Pang J-S, Gabriel SA (1993) NE/SQP: A robust algorithm for the nonlinear complementarity problem. Math. Programming 60(1–3):295–337.Crossref, Google Scholar
• Pham Dinh T, Le Thi HA, Akoa F (2008) Combining DCA (DC algorithms) and interior point techniques for large-scale nonconvex quadratic programming. Optim. Methods Software 23(4):609–629.Crossref, Google Scholar
• Prékopa A, Ruszczyński A, Shapiro A (2003) Probabilistic programming models. Handbooks in Operations Research and Management Science, vol. 10 (Elsevier, Amsterdam), 267–351.Google Scholar
• Scheel H, Scholtes S (2000) Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25(1):1–22.Link, Google Scholar
• Siddiqui S, Gabriel SA (2013) An SOS1-based approach for solving MPECs with a natural gas market application. Network Spatial Econom. 13(2):205–227.Crossref, Google Scholar