Abstract
A large number of real-world optimization problems can be formulated as Mixed Integer Linear Programs (MILP). MILP solvers expose numerous configuration parameters to control their internal algorithms. Solutions, and their associated costs or runtimes, are significantly affected by the choice of the configuration parameters, even when problem instances have the same number of decision variables and constraints. On one hand, using the default solver configuration leads to suboptimal solutions. On the other hand, searching and evaluating a large number of configurations for every problem instance is time-consuming and, in some cases, infeasible. In this study, we aim to predict configuration parameters for unseen problem instances that yield lower-cost solutions without the time overhead of searching-and-evaluating configurations at the solving time. Toward that goal, we first investigate the cost correlation of MILP problem instances that come from the same distribution when solved using different configurations. We show that instances that have similar costs using one solver configuration also have similar costs using another solver configuration in the same runtime environment. After that, we present a methodology based on Deep Metric Learning to learn MILP similarities that correlate with their final solutions’ costs. At inference time, given a new problem instance, it is first projected into the learned metric space using the trained model, and configuration parameters are instantly predicted using previously-explored configurations from the nearest neighbor instance in the learned embedding space. Empirical results on real-world problem benchmarks show that our method predicts configuration parameters that improve solutions’ costs by up to 38% compared to existing approaches.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Also called incumbent configuration in the context of parameters configuration search; not to be confused with the incumbent solution of the solver itself, which is the \(\textbf{x}\)’s assignment with minimum cost of the MILP objective function.
The implementation of shallow embedding is provided in the supplementary material. There is no publicly available implementation of Hydra-MIP.
References
Achterberg, T., Berthold, T., Koch, T., & Wolter, K. (2008). Constraint integer programming: A new approach to integrate cp and mip. In: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems: 5th international conference, cpaior 2008 paris, france, may 20-23, 2008 proceedings 5, pp. 6–20. springer
Ansótegui, C., Gabas, J., Malitsky, Y., & Sellmann, M. (2016). MaxSAT by improved instance-specific algorithm configuration. Artificial Intelligence, 235, 26–39.
Balaprakash, P., Birattari, M., & Stützle, T. (2007). Improvement strategies for the f-race algorithm: Sampling design and iterative refinement. In: Proceedings of Hybrid metaheuristics: 4th international workshop, HM 2007, Dortmund, Germany, October 8-9, 2007, pp. 108–122. Springer
Becker, H., Araujo, O., & Buriol, L. S. (2021). Extending an integer formulation for the guillotine 2d bin packing problem. Procedia Computer Science, 195, 499–507.
Bello, I., Pham, H., Le, Q.V., Norouzi, M., & Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940.
Bengio, Y., Lodi, A., & Prouvost, A. (2021). Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2), 405–421.
Bergstra, J., & Bengio, Y. (2012). Random search for hyper-parameter optimization. Journal of Machine Learning Research,13(2).
Birattari, M., Stützle, T., Paquete, L. & Varrentrapp, K., et al. (2002). A racing algorithm for configuring metaheuristics. In: Gecco, vol. 2. Citeseer
Birattari, M., Yuan, Z., Balaprakash, P., & Stützle, T. (2010). F-race and iterated f-race: An overview. Experimental methods for the analysis of optimization algorithms, 311–336.
Birattari, M. (2009). Tuning Metaheuristics. Studies in Computational Intelligence. https://doi.org/10.1007/978-3-642-00483-4
Bixby, B. (2007). The Gurobi optimizer. Transportation Research Part B, 41(2), 159–178.
Bonami, P., Lodi, A., & Zarpellon, G. (2018). Learning a classification of mixed-integer quadratic programming problems. In: International conference on the integration of constraint programming, artificial intelligence, and operations research, pp. 595–604. Springer
Cappart, Q., Chételat, D., Khalil, E., Lodi, A., Morris, C., & Veličković, P. (2021). Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544.
Davis, J. V., & Dhillon, I. S. (2008). Structured metric learning for high dimensional problems. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 195–203.
De Maesschalck, R., Jouan-Rimbaud, D., & Massart, D. L. (2000). The mahalanobis distance. Chemometrics and Intelligent Laboratory Systems, 50(1), 1–18.
Deng, J., Guo, J., Xue, N., & Zafeiriou, S. (2019). Arcface: Additive angular margin loss for deep face recognition. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 4690–4699.
Deveci, M., & Demirel, N. Ç. (2018). A survey of the literature on airline crew scheduling. Engineering Applications of Artificial Intelligence, 74, 54–69.
Eryoldaş, Y., & Durmuşoglu, A. (2022). A literature survey on offline automatic algorithm configuration. Applied Sciences, 12(13), 6316.
Fey, M., & Lenssen, J.E. (2019). Fast graph representation learning with PyTorch Geometric. In: ICLR workshop on representation learning on graphs and manifolds.
Floudas, C. A., & Lin, X. (2005). Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research, 139, 131–162.
Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.-K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., & Halbig, K., et al. (2020). The scip optimization suite 7.0.
Gasse, M., Chételat, D., Ferroni, N., Charlin, L., & Lodi, A. (2019). Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems,32.
Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive representation learning on large graphs. Advances in neural Information Processing Systems,30.
Hoos, H. H. (2012). Automated algorithm configuration and parameter tuning. Autonomous Search, pp. 37–71.
Hutter, F., Hoos, H.H., & Leyton-Brown, K. (2011). Sequential model-based optimization for general algorithm configuration. In: International conference on learning and intelligent optimization, pp. 507–523. Springer.
Hutter, F., Hoos, H.H., Leyton-Brown, K., & Murphy, K. (2010). Time-bounded sequential parameter optimization. In: Learning and intelligent optimization: 4th international conference, LION 4, Venice, Italy, January 18-22, 2010. Selected Papers 4, pp. 281–298. Springer
Jones, D. R., Schonlau, M., & Welch, W. J. (1998). Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4), 455.
Kadioglu, S., Malitsky, Y., Sellmann, M., & Tierney, K. (2010). ISAC–instance-specific algorithm configuration. In: ECAI 2010, pp. 751–756. IOS Press, Lisbon, Portugal.
Kaya, M., & Bilge, H. Ş. (2019). Deep metric learning: A survey. Symmetry, 11(9), 1066.
Kerschke, P., Hoos, H. H., Neumann, F., & Trautmann, H. (2019). Automated algorithm selection: Survey and perspectives. Evolutionary Computation, 27(1), 3–45.
Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L. (2017). Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems,30.
Khalil, E.B., Dilkina, B., Nemhauser, G.L., Ahmed, S., & Shao, Y. (2017). Learning to run heuristics in tree search. In: Ijcai, pp. 659–666.
Kipf, T.N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907
Koch, G., Zemel, R., & Salakhutdinov, R., et al. (2015). Siamese neural networks for one-shot image recognition. In: ICML Deep Learning Workshop, vol. 2. Lille
Kool, W., Van Hoof, H., & Welling, M. (2018). Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475.
Kruber, M., Lübbecke, M.E., & Parmentier, A. (2017). Learning when to use a decomposition. In: International conference on AI and OR techniques in constraint programming for combinatorial optimization problems, pp. 202–210. Springer
Kulis, B., et al. (2013). Metric learning a survey. Foundations and Trends® in Machine Learning, 5(4), 287–364.
Lee, J., Abu-El-Haija, S., Varadarajan, B., & Natsev, A. (2018). Collaborative deep metric learning for video understanding. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 481–490.
Lee, S., Choi, J., & Son, Y. (2023). Efficient visibility algorithm for high-frequency time-series: application to fault diagnosis with graph convolutional network. Annals of Operations Research, 1–21.
Li, Z., Chen, Q., & Koltun, V. (2018). Combinatorial optimization with graph convolutional networks and guided tree search. Advances in Neural Information Processing Systems,31.
Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., & Talwalkar, A. (2017). Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1), 6765–6816.
Lindauer, M., Eggensperger, K., Feurer, M., Biedenkapp, A., Deng, D., Benjamins, C., Ruhkopf, T., Sass, R., & Hutter, F. (2022). SMAC3: A versatile Bayesian optimization package for hyperparameter optimization. Journal of Machine Learning Research, 23(54), 1–9.
López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., & Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3, 43–58.
Louati, A., Lahyani, R., Aldaej, A., Mellouli, R., & Nusir, M. (2021). Mixed integer linear programming models to solve a real-life vehicle routing problem with pickup and delivery. Applied Sciences, 11(20), 9551.
Maher, S., Miltenberger, M., Pedroso, J. P., Rehfeldt, D., Schwarz, R., & Serrano, F. (2016). PySCIPOpt: Mathematical programming in python with the SCIP optimization suite. In: Mathematical Software–ICMS 2016, pp. 301–307. Springer, Cham. https://doi.org/10.1007/978-3-319-42432-3_37
Malitsky, Y., & Sellmann, M. (2012). Instance-specific algorithm configuration as a method for non-model-based portfolio generation. In: Integration of AI and OR techniques in contraint programming for combinatorial optimzation problems: 9th international conference, CPAIOR 2012, Nantes, France, May 28–June1, 2012. Proceedings 9, pp. 244–259. Springer
Manual, C. U. (2018). IBM ILOG CPLEX optimization studio. Version, 12, 1987–2018.
Maron, O., & Moore, A. W. (1997). The racing algorithm: Model selection for lazy learners. Artificial Intelligence Review, 11, 193–225.
ML4CO: Machine learning for combinatorial optimization - NeurIPS 2021 competition. ML4CO Competition. https://www.ecole.ai/2021/ml4co-competition/. Accessed 16 May 2022 (2021)
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. (2019). Weisfeiler and leman go neural: Higher-order graph neural networks. In: Proceedings of the AAAI conference on artificial intelligence, Vol. 33, pp. 4602–4609.
Musgrave, K., Belongie, S., & Lim, S.-N. (2020). PyTorch metric learning.
Olson, R. S., Bartley, N., Urbanowicz, R. J., & Moore, J. H. (2016). Evaluation of a tree-based pipeline optimization tool for automating data science. In: Proceedings of the genetic and evolutionary computation conference 2016, pp. 485–492.
Paschos, V. T. (2014). Applications of combinatorial optimization (Vol. 3). New York: Wiley.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019). Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems,32.
Prouvost, A., Dumouchelle, J., Scavuzzo, L., Gasse, M., Chételat, D., & Lodi, A. (2020). Ecole: A gym-like library for machine learning in combinatorial optimization solvers. In: Learning meets combinatorial algorithms at NeurIPS. https://openreview.net/forum?id=IVc9hqgibyB
Schroff, F., Kalenichenko, D., & Philbin, J. (2015). Facenet: A unified embedding for face recognition and clustering. In: Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 815–823.
Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., & De Freitas, N. (2015). Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1), 148–175.
Snoek, J., Larochelle, H., & Adams, R. P. (2012). Practical bayesian optimization of machine learning algorithms. Advances in Neural Information Processing Systems,25.
Valentin, R., Ferrari, C., Scheurer, J., Amrollahi, A., Wendler, C., & Paulus, M.B. (2022). Instance-wise algorithm configuration with graph neural networks. https://doi.org/10.48550/ARXIV.2202.04910.
Van der Maaten, L., & Hinton, G. (2008). Visualizing data using t-SNE. Journal of Machine Learning Research,9(11).
Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer networks. Advances in Neural Information Processing Systems,28.
Wang, F., & Liu, H. (2021). Understanding the behaviour of contrastive loss. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 2495–2504
Wang, R., Hua, Z., Liu, G., Zhang, J., Yan, J., Qi, F., Yang, S., Zhou, J., & Yang, X. (2021). A bi-level framework for learning to solve combinatorial optimization on graphs. Advances in Neural Information Processing Systems,34.
Wang, H., Wang, Y., Zhou, Z., Ji, X., Gong, D., Zhou, J., Li, Z., & Liu, W. (2018). Cosface: Large margin cosine loss for deep face recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5265–5274.
Wang, D., Zhu, J., Yin, Y., Ignatius, J., Wei, X., & Kumar, A. (2023). Dynamic travel time prediction with spatiotemporal features: using a gnn-based deep learning method. Annals of Operations Research, pp. 1–21.
Xie, J., Girshick, R., & Farhadi, A. (2016). Unsupervised deep embedding for clustering analysis. In: International conference on machine learning, pp. 478–487. PMLR
Xu, L., Hutter, F., Hoos, H.H., & Leyton-Brown, K. (2011). Hydra-mip: Automated algorithm configuration and selection for mixed integer programming. In: RCRA workshop on experimental evaluation of algorithms for solving problems with combinatorial explosion at the international joint conference on artificial intelligence (IJCAI), pp. 16–30.
Funding
This study was partially funded by NSF grants 1814920 and DoD ARO grant W911NF-19-1-0484.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
Abdelrahman Hosny declares that he has no conflict of interest. Sherief Reda declares that he has no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix A: Data management
Appendix A: Data management
In order to offer a seamless integration of our method in existing environments, a data store is required to save the results from the offline configuration space search. In this work, we use MongoDBFootnote 10 for that purpose. For each benchmark, we create a collection that contains records for each problem instance in that dataset. Listing 1 shows the schema used for each instance. It keeps track of configurations explored for that instance along with their costs. In addition, it records the embedding vector of the instance in order to be searched later with the nearest neighbor algorithm. The parameters presented in the listing are the ones that were used for the configuration space exploration using SMAC (Lindauer et al., 2022). A detailed description of the definition of these parameters can be found in their official documentation.Footnote 11 As discussed in Sect. 5, the metric learning approach does not limit the number of configuration parameters explored offline. It also does not limit which parameters are explored since it focuses on learning an embedding space where similarity between instances can be quantified reliably. Thus, it is possible to learn a model for similarity once and keep expanding the offline configuration space search without requiring to re-train the model.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Hosny, A., Reda, S. Automatic MILP solver configuration by learning problem similarities. Ann Oper Res 339, 909–936 (2024). https://doi.org/10.1007/s10479-023-05508-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-023-05508-x