Boosting the feasibility pump. (English) Zbl 1323.65065
Summary: The feasibility pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between linear programming (LP) feasible but fractional solutions, and integer but LP infeasible solutions. The process attempts to minimize the distance between consecutive iterates, producing an integer feasible solution when closing the distance between them. We investigate the benefits of enhancing the rounding procedure with a clever integer line search that efficiently explores a large set of integer points. An extensive computational study on benchmark instances demonstrates the efficacy of the proposed approach.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C11 | Mixed integer programming |
| 90C05 | Linear programming |
Keywords:
algorithm; numerical example; feasibility pump; feasible solutions; mixed integer programming; linear programming; line searchReferences:
| [1] | Achterberg, T.: Constraint integer programming. Ph.D. thesis, TU Berlin (2007) · Zbl 1169.90414 |
| [2] | Achterberg, T., Berthold, T.: Improving the feasibility pump. Discrete Optim. 4(1), 77-86 (2007) · Zbl 1170.90443 · doi:10.1016/j.disopt.2006.10.004 |
| [3] | Baena, D., Castro, J.: Using the analytic center in the feasibility pump. Oper. Res. Lett. 39(5), 310-317 (2011) · Zbl 1235.90098 · doi:10.1016/j.orl.2011.07.005 |
| [4] | Balas, E., Martin, C.H.: Pivot and complement—a heuristic for 0-1 programming. Manage. Sci. 26(1), 86-96 (1980) · Zbl 0442.90060 · doi:10.1287/mnsc.26.1.86 |
| [5] | Balas, E., Schmieta, S., Wallace, C.: Pivot and shift—a mixed integer programming heuristic. Discrete Optim. 1(1), 3-12 (2004) · Zbl 1087.90052 · doi:10.1016/j.disopt.2004.03.001 |
| [6] | 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 · doi:10.1016/j.disopt.2006.10.001 |
| [7] | Bixby, R.E.: Solving real-world linear programs: a decade and more of progress. Oper. Res. 50(1), 3-15 (2002) · Zbl 1163.90643 · doi:10.1287/opre.50.1.3.17780 |
| [8] | Bixby, R.E., Rothberg, E.: Progress in computational mixed integer programming—a look back from the other side of the tipping point. Ann. Oper. Res. 149, 37-41 (2007) · Zbl 1213.90011 · doi:10.1007/s10479-006-0091-y |
| [9] | Danna, E., Rothberg, E., Le Pape, C.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102, 71-90 (2005) · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7 |
| [10] | De Santis, M., Lucidi, S., Rinaldi, F.: New concave penalty functions for improving the feasibility pump. Optimization Online (2010). http://www.optimization-online.org/DB_HTML/2010/07/2667.html. Last accessed 24 May 2011 · Zbl 1282.90099 |
| [11] | Eckstein, J., Nediak, M.: Pivot, cut, and dive: a heuristic for 0-1 mixed integer programming. J. Heurist. 13, 471-503 (2007) · doi:10.1007/s10732-007-9021-7 |
| [12] | Faaland, B.H., Hillier, F.S.: Interior path methods for heuristic integer programming procedures. Oper. Res. 27(6), 1069-1087 (1979) · Zbl 0442.90062 · doi:10.1287/opre.27.6.1069 |
| [13] | Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104, 91-104 (2005) · Zbl 1077.90039 · doi:10.1007/s10107-004-0570-3 |
| [14] | Fischetti, M., Lodi, A.: Local branching. Math. Program. 98, 23-47 (2003) · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5 |
| [15] | Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. Comput. 1, 201-222 (2009) · Zbl 1180.90208 · doi:10.1007/s12532-009-0007-3 |
| [16] | Glover, F., Laguna, M.: General purpose heuristics for integer programming. Part I. J. Heurist. 2, 343-358 (1997a) · Zbl 0887.90123 · doi:10.1007/BF00132504 |
| [17] | Glover, F., Laguna, M.: General purpose heuristics for integer programming. Part II. J. Heuristics 3, 161-179 (1997b) · Zbl 0898.90094 · doi:10.1023/A:1009631530787 |
| [18] | Halická, M.: Analyticity of the central path at the boundary point in semidefinite programming. Eur. J. Oper. Res. 143(2), 311-324 (2002) · Zbl 1058.90047 · doi:10.1016/S0377-2217(02)00276-X |
| [19] | Hanafi, S., Lazic, J., Mladenovic, N.: Variable neighbourhood pump heuristic for 0-1 mixed integer programming feasibility. Electron. Notes Discrete Math. 36, 759-766 (2010) · Zbl 1237.90161 · doi:10.1016/j.endm.2010.05.096 |
| [20] | Hillier, F.S.: Efficient heuristic procedures for integer linear programming with an interior. Oper. Res. 17(4), 600-637 (1969) · Zbl 0176.49902 · doi:10.1287/opre.17.4.600 |
| [21] | Jeroslow, R.G., Smith, T.H.C.: Experimental results on Hillier’s linear search. Math. Program. 9, 371-376 (1975) · Zbl 0314.90066 · doi:10.1007/BF01681357 |
| [22] | Lökketangen, A., Glover, F.: Solving zero-one mixed integer programming problems using tabu search. Eur. J. Oper. Res. 106(2-3), 624-658 (1998) · Zbl 0991.90091 · doi:10.1016/S0377-2217(97)00295-6 |
| [23] | Naoum-Sawaya, J., Elhedhli, S.: An interior point cutting plane heuristic for mixed integer programming. Comput. Oper. Res. 38(9), 1335-1341 (2011) · Zbl 1208.90121 · doi:10.1016/j.cor.2010.12.008 |
| [24] | Rossi, F., van Beek, P., Walsh, T.: Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science Inc., New York (2006) · Zbl 1175.90011 |
| [25] | Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. Inf. J. Comput. 6(4), 445-454 (1994) · Zbl 0814.90093 · doi:10.1287/ijoc.6.4.445 |
| [26] | Schulte, C.: Programming constraint services. Ph.D. thesis, Universität des Saarlandes, Naturwissenschaftlich-Technischen Fakultät I, Saarbrücken (2000) · Zbl 0994.68038 |
| [27] | Schulte, C., Stuckey, P.J.: Speeding up constraint propagation. In: Wallace, M. (ed.) Principles and Practice of Constraint Programming—CP 2004, 10th International Conference. Lecture Notes in Computer Science, pp. 619-633. Springer, Berlin (2004) · Zbl 1152.68583 |
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.
