Description

In the past few years, the area of Machine Learning has witnessed tremendous advancements and achievements, becoming a pervasive technology in a wide range of applications, from industrial domains to everyday-used apps. One area that can significantly benefit from the use of machine learning is combinatorial optimization. Modeling and solving, the two pillar activities for dealing with Constraint Satisfaction and Optimization Problems, can both Machine Learning techniques for boosting their accuracy, efficiency and effectiveness.

In this tutorial we will show how Machine Learning techniques can be used to support the modeling activity by providing model components through machine learning; and to boost the search effectiveness, by understanding which parts of the search space are more promising, or by selecting the most suitable algorithm for a given problem from a portfolio of techniques. Connections with model predictive control and black box optimization will also be covered.

The tutorial will be composed of a talk, covering related recent literature and a hands-on session where some integration techniques will be explained and used.

We have now setup a web site to collect material related to Empirical Model Learning, a technique that allows embedding an ML model within an optimization model.

The web site is available at:

http://emlopt.github.io

It contains:

• The slides of this tutorial!
• A running survey on methods to boost optimization modeling activities via ML (not limited to Empirical Model Learning)
• The EMLlib repository, which implements a growing collection of methods to integrate ML models in optimization
• The EMLTutorial repository, which shows how EML can be used to a problem that may not be so real, but has a very realistic structure :-)

You are invited to head there to get more information!

Planned Outline

Talk:

• Optimization for boosting Machine Learning: a few details
• Machine Learning for boosting optimization: an overview
• Supporting the modeling activity:
  • Machine Learning to detect constraints (e.g. Constraint Acquisition, Model Seeker)
  • Machine Learning models as constraints (e.g. Empirical Model Learning, partially defined constraints)
  • Objective function learning
• Boosting Search
  • No good learning and recording
  • Reinforcement learning for search
  • Approximating branching heuristics
• Algorithm selection and tuning
  • Using ML to predict the run time
  • Using ML to select the best approach
• Similar approaches
  • Black box optimization with surrogate models
  • LION (Learning and Intelligent OptimizatioN) approach, metaheuristics
  • Model predictive control
• Concluding remarks and future research directions

Hands-on session (about Empirical Model Learning)

• Overview of the target problem (Off-line/on-line optimization)
• Overview of the tools
• Sampling the on-line input space to build a training set
• Approximating the on-line behavior via ML
• Embedding the ML model in a combinatorial model

Intended Audience

The tutorial is mainly addressed to: (1) researchers in decision support systems, constraint reasoning and optimization, (2) researchers in Machine Learning, (3) practitioners interested in applications where data are available and decision support systems are needed (examples, industrial applications, smart cities, mobility, energy, etc.).

The needed background knowledge concerns decision support systems, the main machine learning techniques, but the tutorial will provide also an introduction on the main techniques used and the concepts underlying them. Some knowledge of the Python programming language is required for the hands-on session.

The Speakers

Michele Lombardi is a fixed-term Assistant Professor at the DISI department of the University of Bologna; his PhD thesis on hybrid methods for resource allocation and scheduling won the AIxIA Marco Cadoli award in 2010, and honorable mentions ad CP2011 and ICAPS 2012. He works on Combinatorial Optimization and Decision Support Systems. In particular, his research activity is focused on hybrid optimization methods, based on heterogeneous techniques such as Constraint Programming, (Mixed) Integer Linear (and Non-Linear) Programming, and Machine Learning. His main application fields are Resource allocation and Scheduling problems, Off-line/on-line optimization and optimization under uncertainty, and optimization on complex systems. He is member of the editorial board of the Constraints Journal, and a co-founder of the MindIT AI start-up in Italy.

Michela Milano is full professor at the Department Computer Science and Engineering of the University of Bologna. She received her Ph.D. in Computer Science in 1998. Her research interests cover the area of hybrid optimization, a multi-disciplinary field at the cross-road of computer science and applied mathematics, the integration of machine learning with optimization and decision support techniques, optimization for embedded system design, computational sustainability. She is Board member of the European Association of Artificial Intelligence (EurAI) and executive councillor of AAAI. She is Editor in Chief of the Constraint Journal, Area Editor of Constraint Programming Letters and Area Editor of INFORMS Journal on Computing. She is the recipient of the Google Faculty Research Award on DeepOpt: Embedding deep networks in Combinatorial Optimization. She has been the coordinator of the EU FP7 project e-POLICY - Engineering the POlicy making LIfe CYcle (2011-2014), aimed at integrating optimization and decision support techniques with social simulation and machine learning to help policy makers in their decision process, and participant of a number of FP7 and H2020 EU projects on mobility, energy and computing.

Michela Milano and Michele Lombardi have been working in the area of Machine Learning for optimization since 2010. They are the main proponent of the Empirical Model Learning Learning framework, one of the methods to integrate ML and optimization for problem modeling.

Some References (more to come)

• Michele Lombardi, Michela Milano, Andrea Bartolini: Empirical decision model learning. Artif. Intell. 244: 343-367 (2017)
• Michele Lombardi, Stefano Gualandi: A lagrangian propagator for artificial neural networks in constraint programming. Constraints 21(4): 435-462 (2016)
• Michela Milano, Pascal Van Hentenryck: Emerging Architectures for Global System Science. AAAI 2015: 4042-4046
• Alessio Bonfietti, Michele Lombardi, Michela Milano: Embedding Decision Trees and Random Forests in Constraint Programming. CPAIOR 2015: 74-90
• Michela Milano, Michele Lombardi: Strategic decision making on complex systems. Constraints 19(2): 174-185 (2014)
• Andrea Bartolini, Michele Lombardi, Michela Milano, Luca Benini: Optimization and Controlled Systems: A Case Study on Thermal Aware Workload Dispatching. AAAI 2012
• Marco Gavanelli, Michela Milano, Alan Holland, Barry O'Sullivan: What-If Analysis Through Simulation-Optimization Hybrids. ECMS 2012: 624-630
• Andrea Bartolini, Michele Lombardi, Michela Milano, Luca Benini: Neuron Constraints to Model Complex Real-World Problems. CP 2011: 115-129
• Harold Abelson, Gerald Jay Sussman, and Julie Sussman. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, Massachusetts, 1985.
• Robert Baumgartner, Georg Gottlob, and Sergio Flesca. Visual information extraction with Lixto. In Proceedings of the 27th International Conference on Very Large Databases, pages 119–128, Rome, Italy, September 2001. Morgan Kaufmann.
• Nicolas Beldiceanu and Helmut Simonis. A Constraint Seeker: Finding and Ranking Global Constraints from Examples, pages 12–26. Springer Berlin Heidelberg, 2011.
• Christian Bessiere, Frdric Koriche, Nadjib Lazaar, and Barry O’Sullivan. Con- straint acquisition. Artificial Intelligence, 244(Supplement C):315 – 342, 2017. Combining Constraint Solving with Mining and Learning.
• Christian Bessiere, Luc De Raedt, Tias Guns, Lars Kotthoff, Mirco Nanni, Siegfried Nijssen, Barry O’Sullivan, Anastasia Paparrizou, Dino Pedreschi, and Helmut Simonis. The inductive constraint programming loop. IEEE Intelligent Systems, 32(5):44–52, 2017.
• Ronald J. Brachman and James G. Schmolze. An overview of the KL-ONE knowledge representation system. Cognitive Science, 9(2):171–216, April–June 1985.
• Paolo Campigotto, Andrea Passerini, and Roberto Battiti. Active Learning of Combinatorial Features for Interactive Optimization, pages 336–350. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
• Panagiotis D. Christofides, Riccardo Scattolini, David Munoz de la Pena, and Jinfeng Liu. Distributed model predictive control: A tutorial review and future research directions. Computers & Chemical Engineering, 51:21–41, 2013.
• Priya Donti, J. Zico Kolter, and Brandon Amos. Task-based end-to-end model learning in stochastic optimization. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural In- formation Processing Systems 30, pages 5490–5500. Curran Associates, Inc., 2017.
• Andrea Galassi, Michele Lombardi, Paola Mello, and Michela Milano. Model agnostic solution of CSPs via deep learning: a preliminary study. In Proceedings of the 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence and Operations Research, 2018.
• Georg Gottlob. Complexity results for nonmonotonic logics. Journal of Logic and Computation, 2(3):397–425, June 1992.
• Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64(3):579–627, May 2002.
• Andre Hottung, Shunji Tanaka, and Kevin Tierney. Deeplearning assisted heuristic tree search for the container pre-marshalling problem. In arXiv:1709.09972v1, 2017.
• Frank Hutter, Lin Xu, Holger H. Hoos, and Kevin Leyton-Brown. Algorithm runtime prediction: Methods & evaluation. Artif. Intell., 206:79–111, 2014.
• Manuel Laguna. Optquest optimization of complex systems. In OptQuest White Papers, 2011.
• Arnaud Lallouet and Andrei Legtchenko. Partially defined constraints in constraint-based design. AI EDAM, 20(4):297–311, 2006.
• Arnaud Lallouet and Andrei Legtchenko. Building consistencies for partially defined constraints with decision trees and neural networks. International Journal on Artificial Intelligence Tools, 16(4):683–706, 2007.
• Andrei Legtchenko and Arnaud Lallouet. Consistency for partially defined constraints. In Principles and Practice of Constraint Programming - CP 2005, 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005, Proceedings, page 854, 2005.
• Hector J. Levesque. Foundations of a functional approach to knowledge representation. Artificial Intelligence, 23(2):155–212, July 1984.
• Hector J. Levesque. A logic of implicit and explicit belief. In Proceedings of the Fourth National Conference on Artificial Intelligence, pages 198–202, Austin, Texas, August 1984. American Association for Artificial Intelligence.
• Michele Lombardi, Michela Milano, and Andrea Bartolini. Empirical decision model learning. Artificial Intelligence, 244(Supplement C):343 – 367, 2017. Combining Constraint Solving with Mining and Learning.
• Jean-Baptiste Mairy. Reinforced adaptive large neighborhood search. In Proceedings of the Seventeenth International Conference on Principles and Practice of Constraint Programming, 2011.
• Yuri Malitsky and Meinolf Sellmann. 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, pages 244–259, 2012.
• Bernhard Nebel. On the compilability and expressive power of propositional planning formalisms. Journal of Artificial Intelligence Research, 12:271–315, 2000.
• Barry O’Sullivan. Automated modelling and solving in constraint programming. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010, 2010.
• Nestor V. Queipo, Raphael T. Haftka, Wei Shyy, Tushar Goel, Rajkumar Vaidyanathan, and P. Kevin Tucker. Surrogate-based analysis and optimization. Progress in Aerospace Sciences, 41(1):1 – 28, 2005.
• Sicco Verwer, Yingqian Zhang, and Qing Chuan Ye. Auction optimization using regression trees and linear models as integer programs. Artificial Intelligence, 244(Supplement C):368 – 395, 2017. Combining Constraint Solving with Mining and Learning.
• Sicco Verwer, Yingqian Zhang, and Qing Chuan Ye. Auction optimization using regression trees and linear models as integer programs. Artif. Intell., 244:368–395, 2017.
• Zachary T. Wilson and Nikolaos V. Sahinidis. The ALAMO approach to machine learning. Computers & Chemical Engineering, 106:785–795, 2017.