Binary integer programming problems are ubiquitous in many practical applications, including the MaxCut and cheeger cut problem, the MIMO detection and MaxSAT, etc. They are NP-hard due to the combinatorial structure. In this talk, we present a policy gradient method using deep Monte Carlo local search to ensure sufficient exploration in discrete spaces. The local search method is proved to improve the quality of integer solutions and the policy gradient descent converges to stationary points in expectation. Numerical results show that this framework provides near-optimal solutions efficiently for quite a few binary optimization problems.

Mixed-integer linear programs (MILPs) find widespread application in modeling practical problems such as planning and scheduling. A prominent method for solving those MILPs is large neighborhood search (LNS), which iteratively searches for improved solutions within particular neighborhoods of interest. Recent advancements have explored the integration of machine learning techniques into LNS for judiciously guiding users to construct neighborhoods. However, a computational bottleneck still exists in the search step, as it relies on off-the-shelf solvers to optimize auxiliary MILPs of relatively large sizes. In this study, we propose a two-layer LNS (TLNS) approach that leverages LNS to effectively address both the original MILP and its auxiliary MILPs, requiring the optimization of only small-sized MILPs via off-the-shelf solvers.Furthermore, we utilize trained graph neural networks to inform the neighborhood design. We conduct extensive computational experiments using public benchmarks. The results indicate that our TLNS approach achieves remarkable performance gains--up to 76\% and 97\% over LNS and state-of-the-art MILP solvers, respectively.

Despite the rich works on machine learning (ML) for combinatorial optimization (CO), there lacks a principled framework. We develop a unified modular framework for CO incorporating existing major techniques in both learning and search to understand the effects of techniques, which is embodied on the Travelling Salesman Problem (TSP). We show that principles like joint probability estimation, symmetry accommodation, online optimization are desirable for ML4CO, which also guide the development of new method designs within our framework. By extensive evaluation, we also show the advantages of nonautoregressive methods over autoregressive ones, as well as the superiority of supervised paradigms over unsupervised ones. The strategic decoupling and organic recompositions within the framework yield a factory of new solvers, among which some achieve SOTA performance in learningbased solvers of optimality drops of 0.000\% for TSP-50 and 100, and 0.109\% for TSP-500.

It has become popular in recent years to research on learning to optimize due to the advancement of deep learning and the rising of the AI for Science research paradigm. In this talk, I will present some of our recent works on learning to optimize for discrete optimization problems. In the first part, a learning to optimize algorithm for integer programming within the branch and bound framework is illustrated. A learning to optimize algorithm for multi-objective optimization problems is then presented. Finally, I will present an application to the MIMO signal detection problem in wireless communication.