Multi-task Representation Learning for Mixed Integer Linear Programming

• URL: http://arxiv.org/abs/2412.14409v1
• Date: Wed, 18 Dec 2024 23:33:32 GMT
• Title: Multi-task Representation Learning for Mixed Integer Linear Programming
• Authors: Junyang Cai, Taoan Huang, Bistra Dilkina,
• Abstract summary: This paper introduces the first multi-task learning framework for ML-guided MILP solving. We demonstrate that our multi-task learning model performs similarly to specialized models within the same distribution. It significantly outperforms them in generalization across problem sizes and tasks.
• Score: 13.106799330951842
• License:
• Abstract: 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.

Related papers

• Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction [24.3088703166792]
  This paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. We introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks.
  arXiv  Detail & Related papers  (2024-12-31T06:50:42Z)
• MALT: Improving Reasoning with Multi-Agent LLM Training [64.13803241218886]
  We present a first step toward "Multi-agent LLM training" (MALT) on reasoning problems. Our approach employs a sequential multi-agent setup with heterogeneous LLMs assigned specialized roles. We evaluate our approach across MATH, GSM8k, and CQA, where MALT on Llama 3.1 8B models achieves relative improvements of 14.14%, 7.12%, and 9.40% respectively.
  arXiv  Detail & Related papers  (2024-12-02T19:30:36Z)
• Towards Foundation Models for Mixed Integer Linear Programming [15.064109397239086]
  Current deep learning approaches for MILP focus on specific problem classes and do not generalize to unseen classes. We introduce MILP-Evolve, a novel evolutionary framework that is capable of generating a large set of diverse MILP classes. Our empirical results show that models trained on the data generated by MILP-Evolve achieve significant improvements on unseen problems.
  arXiv  Detail & Related papers  (2024-10-10T18:20:44Z)
• Hybrid Training for Enhanced Multi-task Generalization in Multi-agent Reinforcement Learning [7.6201940008534175]
  HyGen is a novel hybrid MARL framework, which integrates online and offline learning to ensure both multi-task generalization and training efficiency. We empirically demonstrate that our framework effectively extracts and refines general skills, yielding impressive generalization to unseen tasks.
  arXiv  Detail & Related papers  (2024-08-24T12:37:03Z)
• Towards Efficient Pareto Set Approximation via Mixture of Experts Based Model Fusion [53.33473557562837]
  Solving multi-objective optimization problems for large deep neural networks is a challenging task due to the complexity of the loss landscape and the expensive computational cost. We propose a practical and scalable approach to solve this problem via mixture of experts (MoE) based model fusion. By ensembling the weights of specialized single-task models, the MoE module can effectively capture the trade-offs between multiple objectives.
  arXiv  Detail & Related papers  (2024-06-14T07:16:18Z)
• Small LLMs Are Weak Tool Learners: A Multi-LLM Agent [73.54562551341454]
  Large Language Model (LLM) agents significantly extend the capabilities of standalone LLMs. We propose a novel approach that decomposes the aforementioned capabilities into a planner, caller, and summarizer. This modular framework facilitates individual updates and the potential use of smaller LLMs for building each capability.
  arXiv  Detail & Related papers  (2024-01-14T16:17:07Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  We present a comprehensive study on the integration of machine learning (ML) techniques into Huawei Cloud's OptVerse AI solver. We showcase our methods for generating complex SAT and MILP instances utilizing generative models that mirror multifaceted structures of real-world problem. We detail the incorporation of state-of-the-art parameter tuning algorithms which markedly elevate solver performance.
  arXiv  Detail & Related papers  (2024-01-11T15:02:15Z)
• Multi-Task Cooperative Learning via Searching for Flat Minima [8.835287696319641]
  We propose to formulate MTL as a multi/bi-level optimization problem, and therefore force features to learn from each task in a cooperative approach. Specifically, we update the sub-model for each task alternatively taking advantage of the learned sub-models of the other tasks. To alleviate the negative transfer problem during the optimization, we search for flat minima for the current objective function.
  arXiv  Detail & Related papers  (2023-09-21T14:00:11Z)
• Low-Rank Multitask Learning based on Tensorized SVMs and LSSVMs [65.42104819071444]
  Multitask learning (MTL) leverages task-relatedness to enhance performance. We employ high-order tensors, with each mode corresponding to a task index, to naturally represent tasks referenced by multiple indices. We propose a general framework of low-rank MTL methods with tensorized support vector machines (SVMs) and least square support vector machines (LSSVMs)
  arXiv  Detail & Related papers  (2023-08-30T14:28:26Z)
• Multi-task twin support vector machine with Universum data [0.0]
  This study looks at the challenge of multi-task learning using Universum data to employ non-target task data. It proposes a multi-task twin support vector machine with Universum data (UMTSVM) and provides two approaches to its solution. Numerical experiments on several popular multi-task data sets and medical data sets demonstrate the efficiency of the proposed methods.
  arXiv  Detail & Related papers  (2022-06-22T11:05:58Z)
• MALib: A Parallel Framework for Population-based Multi-agent Reinforcement Learning [61.28547338576706]
  Population-based multi-agent reinforcement learning (PB-MARL) refers to the series of methods nested with reinforcement learning (RL) algorithms. We present MALib, a scalable and efficient computing framework for PB-MARL.
  arXiv  Detail & Related papers  (2021-06-05T03:27:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.