The voice of optimization
By Dimitris J. Bertsimas, Bartolomeo Stellato. 2018
99 citations recorded by the source corpus.
We introduce the idea that using optimal classification trees (OCTs) and optimal classification trees with-hyperplanes (OCT-Hs), interpretable machine learning algorithms developed by Bertsimas and Dunn (Mach Learn 106(7):1039–1082, 2017), we are able to obtain insight on the strategy behind the optimal solution in continuous and mixed-integer convex optimization problem as a function of key parameters that affect the problem. In this way, optimization is not a black box anymore. Instead, we redefine optimization as a multiclass classification problem where the predictor gives insights on the logic behind the optimal solution. In other words, OCTs and OCT-Hs give optimization a voice. We show on several realistic examples that the accuracy behind our method is in the 90–100% range, while even when the predictions are not correct, the degree of suboptimality or infeasibility is very low. We compare optimal strategy predictions of OCTs and OCT-Hs and feedforward neural networks (NNs) and conclude that the performance of OCT-Hs and NNs is comparable. OCTs are somewhat weaker but often competitive. Therefore, our approach provides a novel insightful understanding of optimal strategies to solve a broad class of continuous and mixed-integer optimization problems.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Wuyang Chen
- Zhangyang Wang
- Tianlong Chen
- Andres Gomez
- Sina Aghaei
- Jialin Liu
- Phebe Vayanos
- Howard Heaton
Citations in the corpus
- Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, background): “, Bertsimas and Stellato (2018). The problem of learning optimal decision trees is an NP-hard problem, see Hyafil and Rivest (1976) and Breiman (2017). It can intuitively be viewed as a combinatorial optimization problem with an exponential number of decision variables: at each internal node of the ”
- Learning to Optimize: A Primer and A Benchmark (2021, background): “Lastly, let us mention recent works that leverage ML for combinatorial and discrete optimization [123; 61; 24; 25; 38].”