×

zbMATH — the first resource for mathematics

An enhanced logical benders approach for linear programs with complementarity constraints. (English) Zbl 1447.90040
Summary: This work extends the logical Benders approach for solving linear programs with complementarity constraints proposed by J. Hu et al. [SIAM J. Optim. 19, No. 1, 445–471 (2008; Zbl 1163.90031)] and L. Bai et al. [Comput. Optim. Appl. 54, No. 3, 517–554 (2013; Zbl 1295.90035)]. We develop a novel interpretation of the logical Benders method as a reversed branch-and-bound search, where the whole exploration procedure starts from the leaf nodes in an enumeration tree. This insight enables us to provide a new framework over which we can combine the master problem and the cut generation in a single process. It also allows us to diversify the search, leading computationally to stronger cuts. We also present an optimization-based sparsification process which makes the cut generation more efficient. Numerical results are presented to show the effectiveness of this enhanced method. Results are also extended to problems with more complementarity constraints, exceeding those that can be handled by the original method in the cited references.
MSC:
90C26 Nonconvex programming, global optimization
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.: Constraint integer programming. Ph.D. Thesis, Technische University Berlin (2007) · Zbl 1430.90427
[2] Alvarez, AM; Louveaux, Q.; Wehenkel, L., A machine learning-based approximation of strong branching, INFORMS J. Comput., 29, 1, 185-195 (2017) · Zbl 1364.90224
[3] Bai, L.; Mitchell, JE; Pang, JS, On convex quadratic programs with linear complementarity constraints, Comput. Optim. Appl., 54, 3, 517-554 (2013) · Zbl 1295.90035
[4] Bard, JF; Moore, JT, A branch and bound algorithm for the bilevel programming problem, SIAM J. Sci. Stat. Comput., 11, 2, 281-292 (1990) · Zbl 0702.65060
[5] Belotti, P.; Bonami, P.; Fischetti, M.; Lodi, A.; Monaci, M.; Nogales-Gomez, A.; Salvagnin, D., On handling indicator constraints in mixed integer programming, Comput. Optim. Appl., 65, 3, 545-566 (2016) · Zbl 1357.90094
[6] Bonami, P.; Lodi, A.; Tramontani, A.; Wiese, S., On mathematical programming with indicator constraints, Math. Program., 151, 191-223 (2015) · Zbl 1328.90086
[7] Burdakov, OP; Kanzow, C.; Schwartz, A., Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method, SIAM J. Optim., 26, 1, 397-425 (2016) · Zbl 1332.90220
[8] Candes, EJ; Wakin, MB; Boyd, SP, Enhancing sparsity by reweighted \(\ell_1\) minimization, J. Fourier Anal. Appl., 14, 5-6, 877-905 (2008) · Zbl 1176.94014
[9] Feng, M.; Mitchell, JE; Pang, JS; Shen, X.; Wächter, A., Complementarity formulations of \(\ell_0\)-norm optimization problems, Pac. J. Optim., 14, 2, 273-305 (2018)
[10] Fischer, T.; Pfetsch, ME, Branch-and-cut for linear programs with overlapping SOS1 constraints, Math. Program. Comput., 10, 1, 33-68 (2018) · Zbl 1402.90095
[11] Fischetti, M.; Monaci, M., Backdoor branching, INFORMS J. Comput., 25, 4, 693-700 (2013)
[12] Fischetti, M.; Monaci, M., Exploiting erraticism in search, Oper. Res., 62, 1, 114-122 (2014) · Zbl 1291.90148
[13] Fletcher, R.; Leyffer, S., Solving mathematical programs with complementarity constraints as nonlinear programs, Optim. Methods Softw., 19, 1, 15-40 (2004) · Zbl 1074.90044
[14] Gomes, C.P., Kautz, H., Sabharwal, A., Selman, B.: Satisfiability solvers. In: van Harmelen, F., Lifschitz, V., Porter, B. (eds.) Handbook of Knowledge Representation, Elsevier, pp. 89-134 (2008)
[15] Gomes, C.P., Selman, B., Kautz, H.A.: Boosting combinatorial search through randomization. In: Proceedings of AAAI/IAAI 1998, p. online. AAAI (1998)
[16] Gurobi Optimization: Inc.: Gurobi optimizer reference manual, 2015. URL: http://www.gurobi. com (2014)
[17] Hooker, JN; Ottosson, G., Logic-based Benders decomposition, Math. Program., 96, 1, 33-60 (2003) · Zbl 1023.90082
[18] Hu, J.; Mitchell, JE; Pang, JS, An LPCC approach to nonconvex quadratic programs, Math. Program., 133, 1-2, 243-277 (2012) · Zbl 1244.90177
[19] Hu, J.; Mitchell, JE; Pang, JS; Bennett, KP; Kunapuli, G., On the global solution of linear programs with linear complementarity constraints, SIAM J. Optim., 19, 1, 445-471 (2008) · Zbl 1163.90031
[20] Hu, J.; Mitchell, JE; Pang, JS; Yu, B., On linear programs with linear complementarity constraints, J. Glob. Optim., 53, 1, 29-51 (2012) · Zbl 1254.90111
[21] Huang, J.: The effect of restarts on the efficiency of clause learning. In: Proceedings of IJCAI-07, pp. 2318-2323 (2007)
[22] Ibaraki, T., Complementary programming, Oper. Res., 19, 6, 1523-1529 (1971) · Zbl 0228.90045
[23] Ibaraki, T., The use of cuts in complementary programming, Oper. Res., 21, 1, 353-359 (1973) · Zbl 0274.90025
[24] IBM ILOG: Cplex. Book 12.2 User’s Manual (2010)
[25] Jeroslow, RG, Cutting-planes for complementarity constraints, SIAM J. Control Optim., 16, 1, 56-62 (1978) · Zbl 0395.90076
[26] Jeroslow, RG, The polynomial hierarchy and a simple model for competitive analysis, Math. Program., 32, 2, 146-164 (1985) · Zbl 0588.90053
[27] Karzan, FK; Nemhauser, GL; Savelsbergh, MW, Information-based branching schemes for binary linear mixed integer problems, Math. Program. Comput., 1, 4, 249-293 (2009) · Zbl 1184.90114
[28] Leyffer, S.; López-Calva, G.; Nocedal, J., Interior methods for mathematical programs with complementarity constraints, SIAM J. Optim., 17, 1, 52-77 (2006) · Zbl 1112.90095
[29] Lodi, A.; Zarpellon, G., On learning and branching: a survey, TOP, 25, 2, 207-236 (2017) · Zbl 1372.90003
[30] Luo, ZQ; Pang, JS; Ralph, D., Mathematical Programs with Equilibrium Constraints (1996), Cambridge: Cambridge University Press, Cambridge
[31] Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. In: Proceedings of IJCAI-2003, pp. 1173-1178 (2003)
[32] Yu, B.: A branch and cut approach to linear programs with linear complementarity constraints. Ph.D. Thesis, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180 USA (2011)
[33] Yu, B.; Mitchell, JE; Pang, JS, Solving linear programs with complementarity constraints using branch-and-cut, Math. Program. Comput. (2018) · Zbl 1434.90160
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.