Contributions to Data-Driven Combinatorial Solvers

Discrete optimization problems appear in everyday life, with a wide range of applications including airline scheduling, telecommunications network design and healthcare. Modern solvers are intricately crafted to perform well on average across this wide range of applications. This generality is at odds with their emerging applications where the solver is rapidly queried with slightly modified versions of the same problem. Data-driven algorithm design provides a potential solution to this dilemma by tuning various aspects of the solver via machine learning to the desired distribution of a particular domain. Several attempts have been made towards this goal, yet many challenges lie ahead of its adoption in modern solvers. In this dissertation, we identify some of these challenges and propose methods to alleviate or circumvent them. First, we contribute the first ML-based exact model counter by improving the branching heuristic of a conventional solver in a data-driven manner. We show that the resulting solver takes fewer steps in solving unseen similarly distributed instances and can extrapolate to larger instances from the same problem family, sometimes leading to orders of magnitude speedups over the conventional solver. Second, we investigate the potential of contrastive learning in ML-based solvers. Given the NP-hard nature of these problems, the cost of acquiring labels is quite expensive. We show that, by using only 1% of the labelled data, contrastively-trained representations can achieve comparable test accuracy to fully-supervised representations. This positions contrastive learning as a formidable technique for data-driven solver design. Third, we propose a framework based on Monte Carlo tree search for efficient “backdoor” discovery in integer linear programming. The study of backdoors can reveal novel structural properties of these problems and provide insights into their hardness. Lastly, we show how ML can in turn benefit from the discrete mathematics domain. We show how a type of formal logic can be used to express multi-task, temporally extended instructions to reinforcement learning agents. We prove that the resulting agents have theoretical advantages over baseline methods. Particularly, we show that our agent does not suffer from myopia, where the individual subtasks are solved optimally but the combined solution is suboptimal.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.