Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.22838 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913014538567680 |
|---|---|
| author | Bonami, Pierre Dash, Sanjeeb Derkach, Anton Lodi, Andrea |
| author_facet | Bonami, Pierre Dash, Sanjeeb Derkach, Anton Lodi, Andrea |
| contents | We consider integer programming problems with bounded general-integer variables belonging to the general class of network flow problems. For those, we computationally investigate the effect on mixed-integer linear programming (MIP) solvers of the different ways of producing extended formulations that replace a bounded general integer variable by a linear combination of a set of auxiliary binary variables linked by additional linear constraints. We show that MILP solvers perform very differently depending on which extended formulations is used and we interpret that different performance through the lens of cutting planes generation. Finally, we discuss a simple family of mixed-integer rounding inequalities that especially benefit from the reformulation, and we show its benefit within different MIP solvers. This provides methodological and practical guidelines for the use of those extended formulations in MIP and, to the best of our knowledge, this is the first extensive computational analysis of the topic. All our data and tables are publicly available at https://github.com/anton-derkach1/binarizations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22838 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cutting Planes for Binarized Network Flow Problems Bonami, Pierre Dash, Sanjeeb Derkach, Anton Lodi, Andrea Optimization and Control We consider integer programming problems with bounded general-integer variables belonging to the general class of network flow problems. For those, we computationally investigate the effect on mixed-integer linear programming (MIP) solvers of the different ways of producing extended formulations that replace a bounded general integer variable by a linear combination of a set of auxiliary binary variables linked by additional linear constraints. We show that MILP solvers perform very differently depending on which extended formulations is used and we interpret that different performance through the lens of cutting planes generation. Finally, we discuss a simple family of mixed-integer rounding inequalities that especially benefit from the reformulation, and we show its benefit within different MIP solvers. This provides methodological and practical guidelines for the use of those extended formulations in MIP and, to the best of our knowledge, this is the first extensive computational analysis of the topic. All our data and tables are publicly available at https://github.com/anton-derkach1/binarizations. |
| title | Cutting Planes for Binarized Network Flow Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.22838 |