Progress in Presolving for Mixed Integer Programming
Please always quote using this URN: urn:nbn:de:0297-zib-42530
- Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.
Download full text files
Additional Services
| Author: | Gerald GamrathORCiD, Thorsten KochORCiD, Alexander Martin, Matthias MiltenbergerORCiD, Dieter Weninger |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | mixed-integer programming; preprocessing; presolving |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-04 Explicit machine computation and programs (not the theory of computation or programming) |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods | |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming | |
| CCS-Classification: | G. Mathematics of Computing / G.4 MATHEMATICAL SOFTWARE |
| Date of first Publication: | 2013/09/23 |
| Series (Serial Number): | ZIB-Report (13-48) |
| ISSN: | 1438-0064 |
| Published in: | Appeared in: Mathematical Programming Computation, vol. 7 iss. 4 (2015), pp. 367-398 |
| Preprint: | urn:nbn:de:0297-zib-42530 |
| DOI: | https://doi.org/10.1007/s12532-015-0083-5 |
