Ranking constraint relaxations for mixed integer programs using a machine learning approach. (English) Zbl 07836956
Summary: Solving large-scale Mixed Integer Linear Programs (MIP) can be difficult without advanced algorithms such as decomposition based techniques. Even if a decomposition technique might be appropriate, there are still many possible decompositions for any large MIP and it may not be obvious which will be the most effective. The quality of a decomposition depends on both the tightness of the dual bound, in our case generated via Lagrangian Relaxation, and the computational time required to produce that bound. Both of these factors are difficult to predict, motivating the use of a Machine Learning function to predict decomposition quality based a score that combines both bound quality and computational time. This paper presents a comprehensive analysis of the predictive capabilities of a ML function for predicting the quality of MIP decompositions created via constraint relaxation. In this analysis, the role of instance similarity and ML prediction quality is explored, as well as the benchmarking of a ML ranking function against existing heuristic functions. For this analysis, a new dataset consisting of over 40000 unique decompositions sampled from across 24 instances from the MIPLIB2017 library has been established. These decompostions have been created by both a greedy relaxation algorithm as well as a population based multi-objective algorithm, which has previously been shown to produce high quality decompositions. In this paper, we demonstrate that a ML ranking function is able to provide state-of-the-art predictions when benchmarked against existing heuristic ranking functions. Additionally, we demonstrate that by only considering a small set of features related to the relaxed constraints in each decomposition, a ML ranking function is still able to be competitive with heuristic techniques. Such a finding is promising for future constraint relaxation approaches, as these features can be used to guide decomposition creation. Finally, we highlight where a ML ranking function would be beneficial in a decomposition creation framework.
MSC:
| 90C11 | Mixed integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Achterberg, T.; Koch, T.; Martin, A., MIPLIB 2003. Oper. Res. Lett., 361-372 (2006) · Zbl 1133.90300 |
| [2] | Barahona, F.; Anbil, R., The volume algorithm: producing primal solutions with a subgradient method. Math. Program., 385-399 (2000) · Zbl 0961.90058 |
| [3] | Basso, S.; Ceselli, A., Computational evaluation of ranking models in an automatic decomposition framework. Electron. Notes Discrete Math., 245-252 (2018) |
| [4] | Basso, S.; Ceselli, A.; Tettamanzi, A., Random sampling and machine learning to understand good decompositions. Ann. Oper. Res., 501-526 (2020) · Zbl 1497.90136 |
| [5] | Bergner, M.; Caprara, A.; Ceselli, A.; Furini, F.; Lübbecke, M. E.; Malaguti, E.; Traversi, E., Automatic Dantzig-Wolfe reformulation of mixed integer programs. Math. Program., 391-424 (2015) · Zbl 1307.90114 |
| [6] | Biscani, F.; Izzo, D. (2019), esa/pagmo2: pagmo 2.11.4 |
| [7] | Dantzig, G. B.; Wolfe, P., Decomposition principle for linear programs. Oper. Res., 101-111 (1960) · Zbl 0093.32806 |
| [8] | Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput., 182-197 (2002) |
| [9] | Derrac, J.; García, S.; Molina, D.; Herrera, F., A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol. Comput., 3-18 (2011) |
| [10] | Ernst, A. T.; Singh, G., Lagrangian particle swarm optimization for a resource constrained machine scheduling problem, 1-8 |
| [11] | Fisher, M. L., The Lagrangian relaxation method for solving integer programming problems. Manag. Sci., 1861-1871 (2004) |
| [12] | Gamrath, G.; Lübbecke, M. E., Experiments with a generic Dantzig-Wolfe decomposition for integer programs, 239-252 |
| [13] | Geoffrion, A. M., Generalized benders decomposition. J. Optim. Theory Appl., 237-260 (1972) · Zbl 0229.90024 |
| [14] | Geoffrion, A. M., Lagrangean relaxation for integer programming, 82-114 · Zbl 0395.90056 |
| [15] | 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., MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. Math. Program. Comput. (2021) · Zbl 1476.90191 |
| [16] | Karypis, G.; Aggarwal, R.; Kumar, V.; Shekhar, S., Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 69-79 (1999) |
| [17] | Khaniyev, T.; Elhedhli, S.; Erenay, F. S., Structure detection in mixed-integer programs. INFORMS J. Comput., 570-587 (2018) · Zbl 1528.90161 |
| [18] | Kruber, M.; Lübbecke, M. E.; Parmentier, A., Learning when to use a decomposition, 202-210 · Zbl 1489.68253 |
| [19] | Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev., 60-100 (1991) · Zbl 0734.90060 |
| [20] | Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; Duchesnay, E., Scikit-learn: machine learning in {P}ython. J. Mach. Learn. Res., 2825-2830 (2011) · Zbl 1280.68189 |
| [21] | Sammut, C.; Webb, G. I., Leave-one-out cross-validation, 600-601 |
| [22] | Triantaphyllou, E., Multi-Criteria Decision Making Methods a Comparative Study. Applied Optimization (2000), Springer US: Springer US New York, NY · Zbl 0980.90032 |
| [23] | Wedelin, D., An algorithm for large scale 0-1 integer programming with application to airline crew scheduling. Ann. Oper. Res., 283-301 (1995) · Zbl 0831.90087 |
| [24] | Weiner, J.; Ernst, A.; Li, X.; Sun, Y., Automatic decomposition of mixed integer programs for Lagrangian relaxation using a multiobjective approach, 263-270 |
| [25] | Weiner, J.; Ernst, A. T.; Li, X.; Sun, Y.; Deb, K., Solving the maximum edge disjoint path problem using a modified Lagrangian particle swarm optimisation hybrid. Eur. J. Oper. Res., 847-862 (2021) · Zbl 1487.90574 |
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.
