×

Empirical decision model learning. (English) Zbl 1404.68113

Summary: One of the biggest challenges in the design of real-world decision support systems is coming up with a good combinatorial optimization model. Often enough, accurate predictive models (e.g. simulators) can be devised, but they are too complex or too slow to be employed in combinatorial optimization.
In this paper, we propose a methodology called Empirical Model Learning (EML) that relies on Machine Learning for obtaining components of a prescriptive model, using data either extracted from a predictive model or harvested from a real system. In a way, EML can be considered as a technique to merge predictive and prescriptive analytics.
All models introduce some form of approximation. Citing [G. E. P. Box and N. R. Draper, Empirical model-building and response surfaces. John Wiley & Sons, Hoboken, NJ (1987; Zbl 0614.62104)] “Essentially, all models are wrong, but some of them are useful”. In EML, models are useful if they provide adequate accuracy, and if they can be effectively exploited by solvers for finding high-quality solutions.
We show how to ground EML on a case study of thermal-aware workload dispatching. We use two learning methods, namely Artificial Neural Networks and Decision Trees and we show how to encapsulate the learned model in a number of optimization techniques, namely Local Search, Constraint Programming, Mixed Integer Non-Linear Programming and SAT Modulo Theories. We demonstrate the effectiveness of the EML approach by comparing our results with those obtained using expert-designed models.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization

Citations:

Zbl 0614.62104
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Box, G. E.; Draper, N. R., Empirical Model-Building and Response Surfaces, 424 (1987), Wiley: Wiley New York · Zbl 0614.62104
[2] Brailsford, S.; Churilov, L.; Dangerfield, B., Discrete-Event Simulation and System Dynamics for Management Decision Making (2014), John Wiley & Sons
[4] Bartolini, A.; Lombardi, M.; Milano, M.; Benini, L., Neuron constraints to model complex real-world problems, (Principles and Practice of Constraint Programming. Principles and Practice of Constraint Programming, CP (2011)), 115-129
[5] Bonfietti, A.; Lombardi, M.; Milano, M., Embedding decision trees and random forests in constraint programming, (Integration of AI and OR Techniques in Constraint Programming. Integration of AI and OR Techniques in Constraint Programming, CPAIOR (2015)), 74-90 · Zbl 1459.68189
[6] Howard, J.; Dighe, S., A 48-core IA-32 message-passing processor with DVFS in 45nm CMOS, (International Solid-State Circuits Conference. International Solid-State Circuits Conference, ISSCC (2010)), 108-109
[7] Bennett, K. P.; Parrado-Hernández, E., The interplay of optimization and machine learning research, J. Mach. Learn. Res., 7, 1265-1281 (2006) · Zbl 1222.68146
[8] Sra, S.; Nowozin, S.; Wright, S. J., Optimization for Machine Learning (2011), MIT Press
[9] Raedt, L. D.; Guns, T.; Nijssen, S., Constraint programming for data mining and machine learning, (Proc. of 24th AAAI Conference on Artificial Intelligence (2010), AAAI), 1671-1675
[10] Guns, T.; Nijssen, S.; Raedt, L. D., k-Pattern set mining under constraints, IEEE Trans. Knowl. Data Eng., 25, 2, 402-418 (2013)
[11] Raedt, L. D.; Nijssen, S.; O’Sullivan, B.; Hentenryck, P. V., Constraint programming meets machine learning and data mining (2011), available at:
[12] Malitsky, Y.; Sellmann, M., Instance-specific algorithm configuration as a method for non-model-based portfolio generation, (Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR (2012)), 244-259
[13] Hutter, F.; Xu, L.; Hoos, H.; Leyton-Brown, K., Algorithm runtime prediction: methods & evaluation, Artif. Intell., 206, 79-111 (2014) · Zbl 1334.68185
[14] Kotthoff, L.; Gent, I. P.; Miguel, I., An evaluation of machine learning in algorithm selection for search problems, AI Commun., 25, 3, 257-270 (2012)
[15] Hernando, L.; Mendiburu, A.; Lozano, J. A., Generating customized landscapes in permutation-based combinatorial optimization problems, (Learning and Intelligent Optimization - LION. Learning and Intelligent Optimization - LION, Lecture Notes in Computer Science, vol. 7997 (2013)), 299-303
[16] Bessière, C.; Coletta, R.; Freuder, E. C.; O’Sullivan, B., Leveraging the learning power of examples in automated constraint acquisition, (Principles and Practice of Constraint Programming. Principles and Practice of Constraint Programming, CP (2004)), 123-137 · Zbl 1152.68540
[17] Bessière, C.; Coletta, R.; O’Sullivan, B.; Paulin, M., Query-driven constraint acquisition, (International Joint Conference on Artificial Intelligence. International Joint Conference on Artificial Intelligence, IJCAI (2007)), 50-55
[18] Beldiceanu, N.; Simonis, H., A model seeker: Extracting global constraint models from positive examples, (Principles and Practice of Constraint Programming. Principles and Practice of Constraint Programming, IJCAI (2012)), 141-157
[19] Bessiere, C.; Coletta, R.; Hebrard, E.; Katsirelos, G.; Lazaar, N.; Narodytska, N.; Quimper, C.-G.; Walsh, T., Constraint acquisition via partial queries, (International Joint Conference on Artificial Intelligence (2013)), 475-481
[20] O’Sullivan, B., Automated modelling and solving in constraint programming, (Proc. of the 24th AAAI Conference (2010)), 1493-1497
[21] Queipo, N. V.; Haftka, R. T.; Shyy, W.; Goel, T.; Vaidyanathan, R.; Tucker, P. K., Surrogate-based analysis and optimization, Prog. Aerosp. Sci., 41, 1, 1-28 (2005)
[22] Cozad, A.; Sahinidis, N. V.; Miller, D. C., Learning surrogate models for simulation-based optimization, AIChE J., 60, 6, 2211-2227 (2014)
[23] Gopalakrishnan, K.; Asce, A. M., Neural network - swarm intelligence hybrid nonlinear optimization algorithm for pavement moduli back-calculation, J. Transp. Eng., 136, 6, 528-536 (2009)
[24] Zaabab, A. H.; Zhang, Q.; Nakhla, M., A neural network modeling approach to circuit optimization and statistical design, IEEE Trans. Microw. Theory Tech., 43, 6, 1349-1358 (1995)
[25] Battiti, R.; Brunato, M., The LION way: machine learning plus intelligent optimization (2014), LIONlab, University of Trento
[26] Gavanelli, M.; Nonato, M.; Peano, A.; Alvisi, S.; Franchini, M., Genetic algorithms for scheduling devices operation in a water distribution system in response to contamination events, (Evolutionary Computation in Combinatorial Optimization. Evolutionary Computation in Combinatorial Optimization, EvoCOP (2012)), 124-135 · Zbl 1292.90329
[27] Conn, A. R.; Scheinberg, K.; Vicente, L. N., Introduction to Derivative-Free Optimization, MPS/SIAM Series on Optimization, vol. 8 (2009), SIAM · Zbl 1163.49001
[28] Audet, C., A survey on direct search methods for blackbox optimization and their applications, (Mathematics Without Boundaries (2014), Springer), 31-56 · Zbl 1321.90125
[29] Jones, D. R.; Schonlau, M.; Welch, W. J., Efficient global optimization of expensive black-box functions, J. Glob. Optim., 13, 455-492 (1998) · Zbl 0917.90270
[30] Fu, M. C., Optimization via simulation: a review, Ann. Oper. Res., 53, 199-248 (1994) · Zbl 0833.90089
[31] Glover, F.; Kelly, J. P.; Laguna, M., New advances for wedding optimization and simulation, (Winter Simulation Conference, vol. 1. Winter Simulation Conference, vol. 1, WSC (1999), IEEE), 255-260
[32] Huang, W.; Ghosh, S.; Velusamy, S., Hotspot: a compact thermal modeling methodology for early-stage VLSI design, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 14, 5, 501-513 (2006)
[33] Bonfietti, A.; Lombardi, M., The weighted average constraint, (Principles and Practice of Constraint Programming. Principles and Practice of Constraint Programming, CP (2012)), 191-206
[34] Haykin, S., Neural Networks: A Comprehensive Foundation (1998), Prentice Hall PTR: Prentice Hall PTR Upper Saddle River, NJ, USA · Zbl 0828.68103
[35] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131 (2013) · Zbl 1291.65172
[36] Rossi, F.; Beek, P. V.; Walsh, T., Handbook of Constraint Programming (2006), Elsevier · Zbl 1175.90011
[37] Lombardi, M.; Gualandi, S., A new propagator for two-layer neural networks in empirical model learning, (Principles and Practice of Constraint Programming. Principles and Practice of Constraint Programming, CP (2013)), 448-463
[38] Rokach, L.; Maimon, O., Data Mining with Decision Trees: Theory and Applications (2008), World Scientific Publishing Co., Inc.: World Scientific Publishing Co., Inc. River Edge, NJ, USA · Zbl 1154.68098
[39] Moura, L. D.; Bjørner, N., Z3: an efficient smt solver, (Tools and Algorithms for the Construction and Analysis of Systems (2008), Springer), 337-340
[40] Régin, J. C., Generalized arc consistency for global cardinality constraint, (Proc. of the 13th National Conference on Artificial Intelligence, vol. 1 (1996), AAAI Press), 209-215
[41] Flach, P., Machine Learning: The Art and Science of Algorithms That Make Sense of Data (2012), Cambridge University Press · Zbl 1267.68010
[43] Quinlan, J., C4.5: Programs for Machine Learning (1993), Morgan Kaufmann
[44] Hall, M.; Frank, E.; Holmes, G.; Pfahringer, B.; Reutemann, P.; Witten, I. H., The WEKA data mining software: an update, ACM SIGKDD Explor. Newsl., 11, 1, 10-18 (2009)
[45] Benoist, T.; Estellon, B.; Gardi, F.; Megel, R.; Nouioua, K., Localsolver 1.x: a black-box local-search solver for 0-1 programming, 4OR, 9, 3, 299-316 (2011) · Zbl 1231.90318
[46] Bussieck, M. R.; Pruessner, A., Mixed-integer nonlinear programming, SIAG/OPT Newsl. Views News, 14, 1, 19-22 (2003)
[47] Sahinidis, N. V., BARON 12.1.0: global optimization of mixed-integer nonlinear programs, User’s manual (2013), available at:
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.