A generic Branch-and-Cut algorithm for bi-objective binary linear programs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929537965621248 |
|---|---|
| author | Fouilhoux, Pierre Létocart, Lucas Zhang, Yue |
| author_facet | Fouilhoux, Pierre Létocart, Lucas Zhang, Yue |
| contents | This paper presents the first generic bi-objective binary linear branch-and-cut algorithm. Studying the impact of valid inequalities in solution and objective spaces, two cutting frameworks are proposed. The multi-point separation problem is introduced together with a cutting algorithm to efficiently generate valid inequalities violating multiple points simultaneously. The other main idea is to invoke state-of-the-art integer linear programming solver's internal advanced techniques such as cut separators. Aggregation techniques are proposed to use these frameworks with a trade-off among efficient cut separations, tight lower and upper bound sets and advanced branching strategies. Experiments on various types of instances in the literature exhibit the promising efficiency of the algorithm that solves instances with up to 2800 binary variables in less than one hour of CPU time. Our algorithms are easy to extend for more than two objectives and integer variables. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08722 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A generic Branch-and-Cut algorithm for bi-objective binary linear programs Fouilhoux, Pierre Létocart, Lucas Zhang, Yue Discrete Mathematics Optimization and Control This paper presents the first generic bi-objective binary linear branch-and-cut algorithm. Studying the impact of valid inequalities in solution and objective spaces, two cutting frameworks are proposed. The multi-point separation problem is introduced together with a cutting algorithm to efficiently generate valid inequalities violating multiple points simultaneously. The other main idea is to invoke state-of-the-art integer linear programming solver's internal advanced techniques such as cut separators. Aggregation techniques are proposed to use these frameworks with a trade-off among efficient cut separations, tight lower and upper bound sets and advanced branching strategies. Experiments on various types of instances in the literature exhibit the promising efficiency of the algorithm that solves instances with up to 2800 binary variables in less than one hour of CPU time. Our algorithms are easy to extend for more than two objectives and integer variables. |
| title | A generic Branch-and-Cut algorithm for bi-objective binary linear programs |
| topic | Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2410.08722 |