Serial and Parallel Two-Column Probing for Mixed-Integer Programming
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911256407965696 |
|---|---|
| author | Dai, Yongzheng Chen, Chen |
| author_facet | Dai, Yongzheng Chen, Chen |
| contents | Probing in mixed-integer programming (MIP) is a technique of temporarily fixing variables to discover implications that are useful to branch-and-cut solvers. Such fixing is typically performed one variable at a time -- this paper develops instead a two-column probing scheme that instead fixes a pair of variables per iteration. Although the scheme involves more work per iteration compared to the one-column approach, stronger implied bounds as well as more conflicts identified may compensate. Indeed, our prototype implementation was awarded first prize at the MIP Workshop 2024 Computational Competition on novel presolving approaches. This paper presents the aforementioned (serial) prototype and additionally develops an efficient parallelization, leveraging hardware acceleration to further improve overall solve times. Compared to serial two-column probing, our parallel version sacrifices some strength per-pair probed in exchange for greatly increasing the total number of such probings; computational experiments demonstrate its promise. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16927 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Serial and Parallel Two-Column Probing for Mixed-Integer Programming Dai, Yongzheng Chen, Chen Optimization and Control 90C10 Probing in mixed-integer programming (MIP) is a technique of temporarily fixing variables to discover implications that are useful to branch-and-cut solvers. Such fixing is typically performed one variable at a time -- this paper develops instead a two-column probing scheme that instead fixes a pair of variables per iteration. Although the scheme involves more work per iteration compared to the one-column approach, stronger implied bounds as well as more conflicts identified may compensate. Indeed, our prototype implementation was awarded first prize at the MIP Workshop 2024 Computational Competition on novel presolving approaches. This paper presents the aforementioned (serial) prototype and additionally develops an efficient parallelization, leveraging hardware acceleration to further improve overall solve times. Compared to serial two-column probing, our parallel version sacrifices some strength per-pair probed in exchange for greatly increasing the total number of such probings; computational experiments demonstrate its promise. |
| title | Serial and Parallel Two-Column Probing for Mixed-Integer Programming |
| topic | Optimization and Control 90C10 |
| url | https://arxiv.org/abs/2408.16927 |