×

zbMATH — the first resource for mathematics

Feasibility pump 2.0. (English) Zbl 1180.90208
Summary: Finding a feasible solution of a given mixed-integer programming (MIP) model is a very important \({\mathcal{NP}}\)-complete problem that can be extremely hard in practice. Feasibility Pump (FP) is a heuristic scheme for finding a feasible solution to general MIPs that can be viewed as a clever way to round a sequence of fractional solutions of the LP relaxation, until a feasible one is eventually found. In this paper we study the effect of replacing the original rounding function (which is fast and simple, but somehow blind) with more clever rounding heuristics. In particular, we investigate the use of a diving-like procedure based on rounding and constraint propagation-a basic tool in Constraint Programming. Extensive computational results on binary and general integer MIPs from the literature show that the new approach produces a substantial improvement of the FP success rate, without slowing-down the method and with a significantly better quality of the feasible solutions found.

MSC:
90C11 Mixed integer programming
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.: Constraint integer programming. PhD thesis, Technische Universität Berlin, (2007) · Zbl 1169.90414
[2] Achterberg T., Berthold T.: Improving the feasibility pump. Discrete Optim. 4, 77–86 (2007) · Zbl 1170.90443 · doi:10.1016/j.disopt.2006.10.004
[3] Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett., 34:361–372. Problems available at http://miplib.zib.de (2006)
[4] Balas E., Ceria S., Dawande M., Margot F., Pataki G.: OCTANE: A new heuristic for pure 0–1 programs. Oper. Res. 49, 207–225 (2001) · Zbl 1163.90654 · doi:10.1287/opre.49.2.207.13535
[5] Balas E., Martin C.: Pivot-and-complement: A heuristic for 0-1 programming. Manage. Sci. 26, 86–96 (1980) · Zbl 0442.90060 · doi:10.1287/mnsc.26.1.86
[6] Balas E., Schmieta S., Wallace C.: Pivot and shift–a mixed integer programming heuristic. Discrete Optim. 1, 3–12 (2004) · Zbl 1087.90052 · doi:10.1016/j.disopt.2004.03.001
[7] Bertacco, L.: Feasibility pump. Source code available at http://www.or.deis.unibo.it/research_pages/ORcodes/FP-gen.html · Zbl 1169.90415
[8] Bertacco L., Fischetti M., Lodi A.: A feasibility pump heuristic for general mixed-integer problems. Discrete Optim. 4, 63–76 (2007) · Zbl 1169.90415 · doi:10.1016/j.disopt.2006.10.001
[9] Danna E., Rothberg E., Pape C.L.: 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] Eckstein J., Nediak M.: Pivot, cut, and dive: a heuristic for 0–1 mixed integer programming. J. Heuristics 13, 471–503 (2007) · doi:10.1007/s10732-007-9021-7
[11] 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
[12] Fischetti M., Lodi A.: Local branching. Math. Program. 98(1–3), 23–47 (2003) · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[13] Fischetti M., Polo C., Scantamburlo M.: A local branching heuristic for mixed-integer programs with 2-level variables, with an application to a telecommunication network design problem. Networks 44, 61–72 (2004) · Zbl 1055.90054 · doi:10.1002/net.20017
[14] Gecode Team: Gecode: Generic constraint development environment, 2008. Available at http://www.gecode.org (2008)
[15] Glover F., Laguna M.: General purpose heuristics for integer programming–part I. J. Heuristics 2, 343–358 (1997) · Zbl 0887.90123 · doi:10.1007/BF00132504
[16] Glover F., Laguna M.: General purpose heuristics for integer programming–part II. J. Heuristics 3, 161–179 (1997) · Zbl 0898.90094 · doi:10.1023/A:1009631530787
[17] Glover F., Laguna M.: Tabu Search. Kluwer, Dordrecht (1997) · Zbl 0930.90083
[18] Gondzio J.: Presolve analysis of linear programs prior to applying an interior point method. INFORMS J. Comput. 9, 73–91 (1997) · Zbl 0890.90143 · doi:10.1287/ijoc.9.1.73
[19] Hansen P., Mladenović N., Urosevic D.: Variable neighborhood search and local branching. Comput. Oper. Res. 33, 3034–3045 (2006) · Zbl 1086.90042 · doi:10.1016/j.cor.2005.02.033
[20] Hillier F.: Efficient heuristic procedures for integer linear programming with an interior. Oper. Res. 17, 600–637 (1969) · Zbl 0176.49902 · doi:10.1287/opre.17.4.600
[21] Hooker J.N.: Integrated Methods for Optimization. Springer, New York (2006) · Zbl 1103.68811
[22] Ibaraki T., Ohashi T., Mine F.: A heuristic algorithm for mixed-integer programming problems. Math. Program. Study 2, 115–136 (1974) · Zbl 0353.90061
[23] ILOG. CPLEX 11.0 User’s manual (2008)
[24] Lagerkvist M.Z., Schulte C.: Advisors for incremental propagation. In: Bessière C. (ed.) Thirteenth international conference on principles and practice of constraint programming. Lecture notes in computer science, vol. 4741, pp. 409–422. Springer-Verlag, New York (2007)
[25] Løkketangen A.: Heuristics for 0–1 mixed-integer programming. In: Pardalos, P., Garey, M.R. (eds) Handbook of Applied Optimization, pp. 474–477. Oxford University Press, Oxford (2002)
[26] Løkketangen A., Glover F.: Solving zero/one mixed integer programming problems using tabu search. Eur. J. Oper. Res. 106, 624–658 (1998) · Zbl 0991.90091 · doi:10.1016/S0377-2217(97)00295-6
[27] Maros I.: Computational Techniques of the Simplex Method. Kluwer, Dordrecht (2002) · Zbl 1140.90033
[28] Mittelmann, H.D.: Benchmarks for optimization software: Testcases. Problems available at http://plato.asu.edu/sub/testcases.html
[29] Rossi, F., van Beek, P., Walsh, T. (eds.): Computational Techniques of the Simplex Method. Elsevier, Amsterdam (2006) · Zbl 1175.90011
[30] Savelsbergh M.W.P.: Preprocessing and probing for mixed integer programming problems. ORSA J. Comput. 6, 445–454 (1994) · Zbl 0814.90093
[31] Schulte, C.: Programming constraint services. PhD thesis, Universität des Saarlandes, Naturwissenschaftlich-Technische Fakultät I, Fachrichtung Informatik, Saarbrücken, Germany (2000)
[32] 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, vol. 3258, pp. 619–633. Springer (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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.