Generation of feasible integer solutions on a massively parallel computer using the feasibility pump. (English) Zbl 1409.90117
Summary: We present an approach to parallelize generation of feasible mixed integer solutions of mixed integer linear programs in distributed memory high performance computing environments. This approach combines a parallel framework with feasibility pump (FP) as the rounding heuristic. It runs multiple FP instances with different starting solutions concurrently, while allowing them to share information. Our computational results suggest that the improvement resulting from parallelization using our approach is statistically significant.
MSC:
| 90C11 | Mixed integer programming |
| 65K05 | Numerical mathematical programming methods |
| 65Y05 | Parallel numerical computation |
References:
| [1] | Achterberg, T.; Berthold, T., Improving the feasibility pump, Discrete Optim., 4, 1, 77-86 (2007) · Zbl 1170.90443 |
| [2] | Achterberg, T.; Koch, T.; Martin, A., MIPLIB 2003, Oper. Res. Lett., 34, 4, 361-372 (2006) · Zbl 1133.90300 |
| [3] | Baena, D.; Castro, J., Using the analytic center in the feasibility pump, Oper. Res. Lett., 39, 5, 310-317 (2011) · Zbl 1235.90098 |
| [4] | Balas, E.; Ceria, S.; Dawande, M.; Margot, F.; Pataki, G., Octane: A new heuristic for pure 0-1 programs, Oper. Res., 49, 2, 207-225 (2001) · Zbl 1163.90654 |
| [5] | Balas, E.; Martin, C. H., Pivot-and-complement: A Heuristic for 0-1 Programming, Manage. Sci., 26, 1, 8696 (1980) · Zbl 0442.90060 |
| [6] | Balas, E.; Schmieta, S.; Wallace, C., Pivot and shift - a mixed integer programming heuristic, Discrete Optim., 1, 1, 3-12 (2004) · Zbl 1087.90052 |
| [7] | Bertacco, L.; Fischetti, M.; Lodi, A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optim., 4, 1, 63-76 (2007) · Zbl 1169.90415 |
| [8] | http://coral.ie.lehigh.edu/mip-instances/; http://coral.ie.lehigh.edu/mip-instances/ |
| [9] | Danna, E.; Rothberg, E.; Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, 1, 71-90 (2005) · Zbl 1131.90036 |
| [10] | Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Math. Program., 104, 1, 91-104 (2005) · Zbl 1077.90039 |
| [11] | Fischetti, M.; Lodi, A., Local branching, Math. Program., 98, 1, 23-47 (2003) · Zbl 1060.90056 |
| [12] | M. Fischetti, A. Lodi, M. Monaci, D. Salvagnin, A. Tramontani, Improving branch-and-cut performance by random sampling, Math. Program. Comput. (2016) 113-132. http://dx.doi.org/10.1007/s12532-015-0096-0; M. Fischetti, A. Lodi, M. Monaci, D. Salvagnin, A. Tramontani, Improving branch-and-cut performance by random sampling, Math. Program. Comput. (2016) 113-132. http://dx.doi.org/10.1007/s12532-015-0096-0 · Zbl 1334.90079 |
| [13] | Fischetti, M.; Salvagnin, D., Feasibility pump 2.0, Math. Program. Comput., 1, 201-222 (2009) · Zbl 1180.90208 |
| [14] | Huang, K.-L.; Mehrotra, S., An empirical evaluation of walk-and-round heuristics for mixed integer linear programs, Comput. Optim. Appl., 55, 3, 545-570 (2013) · Zbl 1275.90045 |
| [15] | Huang, K.-L.; Mehrotra, S., An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs, Comput. Optim. Appl., 60, 3, 559-585 (2015) · Zbl 1326.90055 |
| [16] | Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, R. E.; Danna, E.; Gamrath, G.; Gleixner, A. M.; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, D. E.; Wolter, K., MIPLIB 2010, Math. Program. Comput., 3, 2, 103-163 (2011) |
| [17] | Koch, T.; Ralphs, T.; Shinano, Y., Could we use a million cores to solve an integer program?, Math. Methods Oper. Res., 76, 1, 67-93 (2012) · Zbl 1262.90106 |
| [18] | Lodi, A., Mixed integer programming computation, (Jnger, M.; Liebling, T. M.; Naddef, D.; Nemhauser, G. L.; Pulleyblank, W. R.; Reinelt, G.; Rinaldi, G.; Wolsey, L. A., 50 Years of Integer Programming 1958-2008 (2010), Springer Berlin Heidelberg), 619-645 · Zbl 1187.90206 |
| [19] | Munguia, L.-M.; Ahmed, S.; Bader, D. A.; Nemhauser, G. L.; Shao, Y., Alternating criteria Search : A parallel large neighborhood search algorithm for mixed integer programs, Opt. Online, 1-20 (2016) · Zbl 1392.90085 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
