Gespeichert in:
| Hauptverfasser: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2508.18742 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908806698500096 |
|---|---|
| author | Li, Jiajun Li, Yixuan Hou, Ran Ding, Yu Guan, Shisi Duan, Jiahui Han, Xiongwei Zhong, Tao Chau, Vincent Wu, Weiwei Wang, Wanyuan |
| author_facet | Li, Jiajun Li, Yixuan Hou, Ran Ding, Yu Guan, Shisi Duan, Jiahui Han, Xiongwei Zhong, Tao Chau, Vincent Wu, Weiwei Wang, Wanyuan |
| contents | Model reduction, which aims to learn a simpler model of the original mixed integer linear programming (MILP), can solve large-scale MILP problems much faster. Most existing model reduction methods are based on variable reduction, which predicts a solution value for a subset of variables. From a dual perspective, constraint reduction that transforms a subset of inequality constraints into equalities can also reduce the complexity of MILP, but has been largely ignored. Therefore, this paper proposes a novel constraint-based model reduction approach for the MILP. Constraint-based MILP reduction has two challenges: 1) which inequality constraints are critical such that reducing them can accelerate MILP solving while preserving feasibility, and 2) how to predict these critical constraints efficiently. To identify critical constraints, we first label these tight-constraints at the optimal solution as potential critical constraints and design a heuristic rule to select a subset of critical tight-constraints. To learn the critical tight-constraints, we propose a multi-modal representation technique that leverages information from both instance-level and abstract-level MILP formulations. The experimental results show that, compared to the state-of-the-art methods, our method improves the quality of the solution by over 50\% and reduces the computation time by 17.47\%. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18742 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming Li, Jiajun Li, Yixuan Hou, Ran Ding, Yu Guan, Shisi Duan, Jiahui Han, Xiongwei Zhong, Tao Chau, Vincent Wu, Weiwei Wang, Wanyuan Machine Learning Model reduction, which aims to learn a simpler model of the original mixed integer linear programming (MILP), can solve large-scale MILP problems much faster. Most existing model reduction methods are based on variable reduction, which predicts a solution value for a subset of variables. From a dual perspective, constraint reduction that transforms a subset of inequality constraints into equalities can also reduce the complexity of MILP, but has been largely ignored. Therefore, this paper proposes a novel constraint-based model reduction approach for the MILP. Constraint-based MILP reduction has two challenges: 1) which inequality constraints are critical such that reducing them can accelerate MILP solving while preserving feasibility, and 2) how to predict these critical constraints efficiently. To identify critical constraints, we first label these tight-constraints at the optimal solution as potential critical constraints and design a heuristic rule to select a subset of critical tight-constraints. To learn the critical tight-constraints, we propose a multi-modal representation technique that leverages information from both instance-level and abstract-level MILP formulations. The experimental results show that, compared to the state-of-the-art methods, our method improves the quality of the solution by over 50\% and reduces the computation time by 17.47\%. |
| title | Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2508.18742 |