(373aj) Learning to Reduce Dimensionality in Mixed Integer Optimization

Mixed Integer Linear Programming (MILP) serves as a critical modeling tool across various fields such as science, engineering, and management, tackling complex problems in planning, scheduling, control, and routing. Given that these problems are often NP-hard and have a combinatorial nature due to numerous discrete decisions, traditional solvers utilize custom heuristics for decision-making and computational tasks. Recent literature highlights the potential of machine learning (ML) to either replace traditional MIP solvers (Abbasi et al., 2020) or to enhance them by leveraging the structural aspects of problems (Bengio et al., 2021). For instance, machine learning has shown promise in boosting the performance of exact algorithms by aiding in the selection of branching variables (Zarpellon et al., 2021), nodes (Yilmaz and Yorke-Smith, 2021), primal heuristics (Nair et al., 2020), and cutting planes (Paulus et al., 2022), as well as enhancing decomposition strategies (Mitrai and Daoutidis, 2023a) or determining the feasibility of decomposition itself (Basso et al., 2020; Mitrai and Daoutidis, 2023b).

In this work, we present a methodology that utilizes deep learning to decompose large-scale MILP problems by estimating complicating variables and pinpointing the problem's significant dimensions. Our approach is threefold: generating synthetic data, training deep-learning classifiers (specifically, Artificial Neural Networks (ANNs) and Convolutional Neural Networks (CNNs)) with Bayesian optimization to fine-tune for the selection of global optimum solutions, and using these classifiers to approximate complicating variables. The classifiers, trained on precomputed MIP instances, aim to identify the active dimensions of a MIP by approximating complicating binary variables, with the notable inclusion of an "infeasible" label to predict infeasibility, thus potentially saving computational resources on unsolvable instances. Upon identifying the active dimensions, we solve the reduced MIP using a commercial solver targeted at the relevant dimensions. We applied our framework to a flow-based facility location-allocation MILP model, which describes the long-term investment and medium-term tactical planning in a cell therapy supply chain for personalized medicine. Remarkably, the CNN classifier guided us to the global optimum in 91.47% of the test instances, whereas the ANN achieved this in 81.32% of the cases.

References

Abbasi, B., Babaei, T., Hosseinifard, Z., Smith-Miles, K., Dehghani, M., 2020. Predicting solutions of large-scale optimization problems via machine learning: A case study in blood supply chain management. Comput Oper Res 119, 104941.

Bengio, Y., Lodi, A., Prouvost, A., 2021. Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur J Oper Res 290, 405–421.

Mitrai, I., Daoutidis, P., 2023a. Taking the human out of decomposition-based optimization via artificial intelligence: Part II. Learning to initialize. arXiv:2310.07082.

Mitrai, I., Daoutidis, P., 2023b. Taking the human out of decomposition-based optimization via artificial intelligence: Part I. Learning when to decompose, arXiv:2310.07068.

Nair, V., Bartunov, S., Gimeno, F., von Glehn, I., Lichocki, P., Lobov, I., O’Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., Addanki, R., Hapuarachchi, T., Keck, T., Keeling, J., Kohli, P., Ktena, I., Li, Y., Vinyals, O., Zwols, Y., 2020. Solving Mixed Integer Programs Using Neural Networks. arXiv preprint arXiv:2012.13349.

Paulus, M.B., Zarpellon, G., Krause, A., Charlin, L., Maddison, C., 2022. Learning to cut by looking ahead: Cutting plane selection via imitation learning, in: International Conference on Machine Learning. PMLR, pp. 17584–17600.

Triantafyllou, N., Bernardi, A., Lakelin, M., Shah, N., Papathanasiou, M.M., 2022. A digital platform for the design of patient-centric supply chains. Sci Rep 12, 17365.

Zarpellon, G., Jo, J., Lodi, A., Bengio, Y., 2021. Parameterizing branch-and-bound search trees to learn branching policies, in: Proceedings of the AAAI Conference on Artificial Intelligence. pp. 3931–3939.