×

zbMATH — the first resource for mathematics

Random sampling and machine learning to understand good decompositions. (English) Zbl 07153647
Summary: Motivated by its implications in the development of general purpose solvers for decomposable Mixed Integer Programs (MIPs), we address a fundamental research question, that is how to exploit data-driven techniques to obtain automatic decomposition methods. We preliminary investigate the link between static properties of MIP input instances and good decomposition patterns. We devise a random sampling algorithm, considering a set of generic MIP base instances, and generate a large, balanced and well diversified set of decomposition patterns, that we analyze with machine learning tools. We also propose and test a minimal proof of concept framework performing data-driven automatic decomposition. The use of supervised techniques highlights interesting structures of random decompositions, as well as proving (under certain conditions) that data-driven methods are fruitful in our context, triggering at the same time perspectives for future research.
MSC:
68T Artificial intelligence
90C Mathematical programming
90 Operations research, mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdi, H.; Williams, Lj, Principal component analysis, Wiley Interdisciplinary Reviews: Computational Statistics, 2, 4, 433-459 (2010)
[2] Achterberg, T., SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1, 1-41 (2009) · Zbl 1171.90476
[3] Achterberg, T.; Koch, T.; Martin, A., MIPLIB 2003, Operations Research Letters, 34, 4, 361-372 (2006) · Zbl 1133.90300
[4] Basso, S., & Ceselli, A. (2017). Asynchronous column generation. In Proceedings of the ninteenth workshop on algorithm engineering and experiments (ALENEX) (pp. 197-206). · Zbl 1429.65120
[5] Basso, S., Ceselli, S., & Tettamanzi, A. (2018). Understanding good decompositions: An exploratory data analysis. Technical report, Università degli Studi di Milano. http://hdl.handle.net/2434/487931.
[6] Bergner, M.; Caprara, A.; Ceselli, A.; Furini, F.; Lübbecke, M.; Malaguti, E.; Traversi, E., Automatic Dantzig-Wolfe reformulation of mixed integer programs, Mathematical Programming A, 149, 1-2, 391-424 (2015) · Zbl 1307.90114
[7] Bettinelli, A.; Ceselli, A.; Righini, G., A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint, Annals of Operations Research, 179, 221-241 (2010) · Zbl 1201.90168
[8] Brooks, Jp; Lee, Ek, Analysis of the consistency of a mixed integer programming-based multi-category constrained discriminant model, Annals of Operations Research, 174, 1, 147-168 (2010) · Zbl 1185.90156
[9] Burges, C., A tutorial on support vector machines for pattern recognition, Data Mining and Knowledge Discovery, 2, 2, 121-167 (1998)
[10] Ceselli, A.; Liberatore, F.; Righini, G., A computational evaluation of a general branch-and-price framework for capacitated network location problems, Annals of Operations Research, 167, 209-251 (2009) · Zbl 1172.90007
[11] Delorme, M.; Iori, M.; Martello, S., Bin packing and cutting stock problems: Mathematical models and exact algorithms, European Journal of Operational Research, 255, 1, 1-20 (2016) · Zbl 1346.90700
[12] Desaulniers, G.; Desrosiers, J.; Solomon, Mm, Column generation (2005), Berlin: Springer, Berlin
[13] FICO xpress webpage. (2017). http://www.fico.com/en/products/fico-xpress-optimization-suite. Last accessed March, 2017
[14] Fisher, Ra; Kotz, S.; Johnson, Nl, Statistical methods for research workers, Breakthroughs in statistics. Springer series in statistics (perspectives in statistics) (1992), New York, NY: Springer, New York, NY
[15] Gamrath, G., & Lübbecke, M. E. (2010). Experiments with a generic Dantzig-Wolfe decomposition for integer programs. LNCS 6049 (pp. 239-252).
[16] GUROBI webpage. (2017). http://www.gurobi.com. Last accessed March, 2017
[17] He, H.; Garcia, Ea, Learning from imbalanced data, IEEE Transactions on Knowledge and Data Engineering, 21, 9, 1263-1284 (2009)
[18] Hutter, F.; Xu, L.; Hoos, Hh; Leyton-Brown, K., Algorithm runtime prediction: Methods & evaluation, Artificial Intelligence, 206, 1, 79-111 (2014) · Zbl 1334.68185
[19] IBM Cplex webpage. (2016). http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html. Last accessed August, 2016
[20] Khalil, E. B. (2016). Machine learning for integer programming. In Proceedings of the twenty-fifth international joint conference on artificial intelligence.
[21] Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, Re; Danna, E.; Gamrath, G.; Gleixner, Am; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, De; Wolter, K., MIPLIB 2010, Mathematical Programming Computation, 3, 2, 103-163 (2011)
[22] Kruber, M., Luebbecke, M. E., & Parmentier, A. (2016). Learning when to use a decomposition. RWTH technical report 2016-037.
[23] Larose, Dt; Larose, Cd, Data mining and predictive analytics (2015), Hoboken: Wiley, Hoboken
[24] Mitzenmacher, M.; Upfal, E., Probability and computing: Randomized algorithms and probabilistic analysis (2005), New York, NY: Cambridge University Press, New York, NY · Zbl 1092.60001
[25] Puchinger, J.; Stuckey, Pj; Wallace, Mg; Brand, S., Dantzig-Wolfe decomposition and branch-and-price solving in G12, Constraints, 16, 1, 77-99 (2011) · Zbl 1213.90174
[26] R Core Team. (2016). R: A language and environment for statistical computing. R Foundation for Statistical Computing. https://www.R-project.org/.
[27] Ralphs, T. K., & Galati, M. V. (2017). DIP—decomposition for integer programming. https://projects.coin-or.org/Dip. Last accessed March, 2017.
[28] Schrijver, A., Theory of linear and integer programming (1998), Hoboken: Wiley, Hoboken · Zbl 0970.90052
[29] Smola, Aj; Scholkopf, B., A tutorial on support vector regression, Statistics and Computing, 14, 199-222 (2004)
[30] Vanderbeck, F. (2017). BaPCod—A generic branch-and-price code. https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/BaPCod. Last accessed March, 2017.
[31] Vanderbeck, F.; Wolsey, L.; Jünger, M.; Liebling, Thm; Naddef, D.; Nemhauser, Gl; Pulleyblank, Wr; Reinelt, G.; Rinaldi, G.; Wolsey, La, Reformulation and decomposition of integer programs, 50 years of integer programming 1958-2008 (2010), Berlin: Springer, Berlin
[32] Wang, J., & Ralphs, T. (2013). Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization. In C. Gomes & M. Sellmann (Eds.), Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. LNCS 7874 (pp. 394-402). · Zbl 1382.90119
[33] Wolsey, L., Integer programming (1998), Hoboken: Wiley, Hoboken · Zbl 0930.90072
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.