Combinatorial Machine Learning and Incomplete MaxSAT Solving
In the first part of the talk, we introduce the Predict+Optimise problem setting and discuss developing machine learning algorithms that are specifically designed to be used with combinatorial problems. These algorithms are important when machine learning and optimisation must interact. For instance, when optimisation is to be performed on data that is not entirely correct but is rather estimated with machine learning. The main challenge is that conventional machine learning metrics, such as mean-square error, are not necessarily indicative of the outcome of optimisation procedure. Ideally, the latter would be used as a criterion of success. However, not only does this involve solving an (NP-hard) optimisation problem, but in addition, this gives riseto a nonlinear, noncontinuous, and nondifferentiable function. Hence, techniques widely used in machine learning, e.g. gradient descent, cannot be applied. The standard approach is to view optimisation and machine learning as two separate black boxes, but potentially better results can be obtained if the process is merged into a single pipeline. Although both combinatorial optimisation and machine learning have been thoroughly studied, their interplay has yet to be understood. In this talk, we present ourformalisation of the Predict+Optimise problem and its challenges, discuss various approaches, and provide an experimental study.
The second part of the talk is devoted to the maximum Boolean satisfiability problem (MaxSAT), where the aim is to compute an assignment of variables that satisfy as many clauses as possible for a propositional logic formula. Many real-life problems can be formulated in propositional logic and thus developing algorithms for this problem is of high importance. Given that practical applications can lead to large formulas that need to be solved with tight time budgets, we focus our attention on methods that provide 'good' solutions 'quickly; We developed techniques for MaxSAT solving based on the exhaustive linear search algorithm and utilise techniques inspired by local search. The resulting algorithm proved to be highly effective, taking first place in the 300 seconds incomplete track of the MaxSAT Evaluation 2018. Moreover, we briefly discuss further improvements based on the integration of the algoithm with a core-guided approach, essentially merging lower and upper bounding techniques.
Dr Emir Demirovi? is an associate lecturer and postdoctoral researcher at the University of Melbourne in Australia, working closely with Professors Peter J. Stuckey, James Bailey, Rao Kotagiri, Christopher Leckie, and Dr Jeffrey Chan. His main expertise lies in solving combinatorial optimisation problems through the use of constraint/integer programming, metaheuristics, and the combination thereof, with special attention to timetabling and scheduling algorithms. After earning his Ph.D. in 2017 at TU Wien under Priv.-Doz. Dr. Nysret Musliu supervision, Dr Demirovi? worked as an optimisation expert in the industry prior to coming to Australia. Throughout his career, he maintained a strong collaboration with the National Institute of Informatics and the National Institute of Advanced Industrial Science and Technology in Tokyo, where he was invited several times. More information can be found on his personal website:www.emirdemirovic.com.