Multi-task Representation Learning for Mixed Integer Linear Programming
This work addresses a domain-specific problem for researchers and practitioners in combinatorial optimization by providing a more scalable and adaptable method for MILP solving, though it is incremental as it builds on existing ML-guided approaches.
The paper tackles the scalability and adaptability limitations of machine learning-guided approaches for solving Mixed Integer Linear Programs (MILPs) by introducing the first multi-task learning framework, which performs similarly to specialized models within the same distribution and significantly outperforms them in generalization across problem sizes and tasks.
Mixed Integer Linear Programs (MILPs) are highly flexible and powerful tools for modeling and solving complex real-world combinatorial optimization problems. Recently, machine learning (ML)-guided approaches have demonstrated significant potential in improving MILP-solving efficiency. However, these methods typically rely on separate offline data collection and training processes, which limits their scalability and adaptability. This paper introduces the first multi-task learning framework for ML-guided MILP solving. The proposed framework provides MILP embeddings helpful in guiding MILP solving across solvers (e.g., Gurobi and SCIP) and across tasks (e.g., Branching and Solver configuration). Through extensive experiments on three widely used MILP benchmarks, we demonstrate that our multi-task learning model performs similarly to specialized models within the same distribution. Moreover, it significantly outperforms them in generalization across problem sizes and tasks.