Preprocessing and cutting planes with conflict graphs. (English) Zbl 1510.90189
Summary: This paper addresses the development of conflict graph-based algorithms and data structures into the COIN-OR Branch-and-Cut (CBC) solver, including: (i) an efficient infrastructure for the construction and manipulation of conflict graphs; (ii) a preprocessing routine based on a clique strengthening scheme that can both reduce the number of constraints and produce stronger formulations; (iii) a clique cut separator capable of obtaining dual bounds at the root node LP relaxation that are 19.65% stronger than those provided by the equivalent cut generator of a state-of-the-art commercial solver, 3.62 times better than those attained by the clique cut separator of the GLPK solver and 4.22 times stronger than the dual bounds obtained by the clique separation routine of the COIN-OR Cut Generation Library; and (iv) an odd-cycle cut separator with a new lifting module to produce valid odd-wheel inequalities. The average gap closed by this new version of CBC was up to four times better than its previous version. Moreover, the number of mixed-integer programs solved by CBC in a time limit of three hours was increased by 23.53 %.
MSC:
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
mixed-integer linear programming; conflict graphs; preprocessing; cutting planes; clique inequalities; odd-cycle inequalitiesReferences:
| [1] | Achterberg, T., 2007. Constraint Integer Programming. Ph.D. thesis. Technische Universitat Berlin. Berlin, Germany. · Zbl 1430.90427 |
| [2] | Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E., Weninger, D., 2016. Presolve Reductions in Mixed Integer Programming. Technical Report 16-44. Zuse Institute Berlin. Berlin. |
| [3] | Achterberg, T.; Wunderling, R., Mixed integer programming: Analyzing 12 years of progress, (Facets of Combinatorial Optimization: Festschrift for Martin Grötschel (2013), Springer: Springer Berlin Heidelberg, Berlin, Heidelberg), 449-481 · Zbl 1317.90206 |
| [4] | Araujo, J. A.; Santos, H. G.; Gendron, B.; Jena, S. D.; Brito, S. S.; Souza, D. S., Strong bounds for resource constrained project scheduling: preprocessing and cutting planes, Comput. Oper. Res., 113, Article 104782 pp. (2020) · Zbl 1458.90247 |
| [5] | Atamtürk, A.; Nemhauser, G. L.; Savelsbergh, M. W., Conflict graphs in solving integer programming problems, Eur. J. Oper. Res., 121, 40-55 (2000) · Zbl 0959.90034 |
| [6] | Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex minlp, Optimiz. Methods Software, 24, 597-634 (2009) · Zbl 1179.90237 |
| [7] | Bixby, R.; Rothberg, E., Progress in computational mixed integer programming—a look back from the other side of the tipping point, Ann. Oper. Res., 149, 37-41 (2007) · Zbl 1213.90011 |
| [8] | Bonami, P.; Biegler, L. T.; Conn, A. R.; Cornuéjols, G.; Grossmann, I. E.; Laird, C. D.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optimiz., 5, 186-204 (2008) · Zbl 1151.90028 |
| [9] | Borndorfer, R., 1998. Aspects of Set Packing, Partitioning, and Covering (Ph.D. thesis). Technische Universitat Berlin. Berlin, Germany. |
| [10] | Brearley, A. L.; Mitra, G.; Williams, H. P., Analysis of mathematical programming problems prior to applying the simplex algorithm, Math. Program., 8, 54-83 (1975) · Zbl 0317.90037 |
| [11] | Bron, C.; Kerbosch, J., Algorithm 457: finding all cliques of an undirected graph, Commun. ACM, 16, 575-577 (1973) · Zbl 0261.68018 |
| [12] | Burke, E. K.; Mareček, J.; Parkes, A. J.; Rudová, H., A branch-and-cut procedure for the udine course timetabling problem, Ann. Oper. Res., 194, 71-87 (2012) · Zbl 1251.90276 |
| [13] | Cornuéjols, G., Revival of the gomory cuts in the 1990’s, Ann. Oper. Res., 149, 63-66 (2007) · Zbl 1213.90015 |
| [14] | Danna, E.; Rothberg, E.; Pape, C. L., Exploring relaxation induced neighborhoods to improve mip solutions, Math. Program., 102, 71-90 (2005) · Zbl 1131.90036 |
| [15] | Dias, B.; de Freitas, R.; Maculan, N.; Michelon, P., Constraint and integer programming models for bandwidth coloring and multicoloring in graphs, Proceedings of the XLVIII Brazilian Symposium on Operations Research, 4116-4127 (2016) |
| [16] | Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program., 104, 91-104 (2005) · Zbl 1077.90039 |
| [17] | Fischetti, M.; Lodi, A., Optimizing over the first chvátal closure, Math. Programm. B, 110, 3-20 (2007) · Zbl 1192.90125 |
| [18] | Fonseca, G. H.; Santos, H. G.; Carrano, E. G.; Stidsen, T. J., Integer programming techniques for educational timetabling, Eur. J. Oper. Res., 262, 28-39 (2017) · Zbl 1403.90323 |
| [19] | Gamrath, G.; Koch, T.; Martin, A.; Miltenberger, M.; Weninger, D., Progress in presolving for mixed integer programming, Math. Programm. Comput., 7, 367-398 (2015) · Zbl 1329.90089 |
| [20] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman & Co.: W.H. Freeman & Co. New York · Zbl 0411.68039 |
| [21] | Gleixner, A., Hendel, G., Gamrath, G., Achterberg, T., Bastubbe, M., Berthold, T., Christophel, P., Jarck, K., Koch, T., Linderoth, J., Lübbecke, M., Mittelmann, H.D., Ozyurt, D., Ralphs, T.K., Salvagnin, D., Shinano, Y., 2018. MIPLIB 2017. URL:http://miplib.zib.de. |
| [22] | Gonçalves, L. C.N. I.; Santos, H. G., Optimization in mass higher education institutions: a tactical approach using aps concepts (in portuguese), Anais do XLIII Simpósio Brasileiro de Pesquisa Operacional, 692-703 (2008) |
| [23] | Grotschel, M.; Lovasz, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1993), Springer · Zbl 0837.05001 |
| [24] | Haspeslagh, S.; De Causmaecker, P.; Schaerf, A.; Stølevik, M., The first international nurse rostering competition 2010, Ann. Oper. Res., 218, 221-236 (2014) · Zbl 1301.90036 |
| [25] | Hoffman, K.; Padberg, M., Solving airline crew scheduling problems by branch-and-cut, Manage. Sci., 39, 657-682 (1993) · Zbl 0783.90051 |
| [26] | Kronqvist, J.; Lundell, A.; Westerlund, T., The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Global Optim., 64, 249-272 (2016) · Zbl 1339.90247 |
| [27] | Méndez-Díaz, I.; Zabala, P., A cutting plane algorithm for graph coloring, Discrete Appl. Math., 156, 159-179 (2008) · Zbl 1163.90012 |
| [28] | Mészáros, C.; Suhl, U. H., Advanced preprocessing techniques for linear and quadratic programming, OR Spectrum, 25, 575-595 (2003) · Zbl 1042.90031 |
| [29] | Orlowski, S.; Wessäly, R.; Pióro, M.; Tomaszewski, A., Sndlib 1.0 survivable network design library, Networks, 55, 276-286 (2010) |
| [30] | Pecin, D.; Pessoa, A.; Poggi, M.; Uchoa, E., Improved branch-cut-and-price for capacitated vehicle routing, Math. Programm. Comput., 9, 61-100 (2017) · Zbl 1368.90111 |
| [31] | Pochet, Y., Wolsey, L.A., 2006. Production planning by mixed integer programming. Springer Science & Business Media. · Zbl 1102.90039 |
| [32] | Rebennack, S., Stable set problem: Branch & cut algorithms, (Floudas, C. A.; Pardalos, P. M., Encyclopedia of Optimization (2009), Springer: Springer US), 3676-3688 |
| [33] | Rossi, R. A.; Zhou, R., Graphzip: a clique-based sparse graph compression method, J. Big Data, 5, 10 (2018) |
| [34] | Sadykov, R.; Vanderbeck, F., Bin packing with conflicts: a generic branch-and-price algorithm, INFORMS J. Comput., 25, 244-255 (2013) |
| [35] | Santos, H. G.; Toffolo, T. A.M.; Gomes, R. A.M.; Ribas, S., Integer programming techniques for the nurse rostering problem, Ann. Oper. Res., 239, 225-251 (2016) · Zbl 1336.90063 |
| [36] | Savelsbergh, M. W.P., Preprocessing and probing techniques for mixed integer programming problems, ORSA J. Comput., 6, 445-454 (1994) · Zbl 0814.90093 |
| [37] | Segundo, P. S.; Artieda, J.; Strash, D., Efficiently enumerating all maximal cliques with bit-parallelism, Comput. Oper. Res., 92, 37-46 (2018) · Zbl 1392.68333 |
| [38] | Tomita, E., Tanaka, A., Takahashi, H., 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science 363, 28-42. Computing and Combinatorics. · Zbl 1153.68398 |
| [39] | Van Roy, T. J.; Wolsey, L. A., Solving mixed integer programming problems using automatic reformulation, Oper. Res., 35, 45-57 (1987) · Zbl 0614.90082 |
| [40] | Xu, J.; Li, M.; Kim, D.; Xu, Y., Raptor: Optimal protein threading by linear programming, J. Bioinform. Comput. Biol., 01, 95-117 (2003) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
