A multi-agent learning framework for mixed-integer linear programming

Mixed integer linear programming (MILP) is an important problem in the combinatorial optimization domain, which has wide applications in practical optimization scenarios. Given that most MILP problems fall into the NP-hard category, which the traditional methods may fail to solve, recent research has tried to derive MILP solutions using machine learning techniques. The whole MILP-solving procedure involves lots of modules, such as pre-solving, cut selection, node section, etc., and these modules are closely related and influence each other. However, the previous machine learning-based approaches neglect the connections between these modules, and focus on single-module learning techniques. To address this, we propose an initial step towards a more comprehensive multi-agent learning framework that allows different modules to interact and collaborate. Specifically, our current implementation involves two key modules: HEM for cut selection applied at the root node and GCNN for variable selection. By employing HEM to influence the training of GCNN, these two agents thus work in unison. Through extensive experiments on four MILP datasets in diverse scenarios, we observe significant improvements in solving time and PD integral metrics compared with the state-of-the-art learning-based MILP solving methods. This work lays the groundwork for future development of a fully integrated multi-agent framework.