Shift-and-Propagate

详细信息    查看全文

• 作者：Timo Berthold (1)
  Gregor Hendel (2)
  
  1. Fair Isaac Europe Ltd ; c/o Zuse Institute Berlin ; Takustr.聽7 ; 14195 ; Berlin ; Germany
  2. Department of Optimization ; Zuse Institute Berlin ; Takustr.聽7 ; 14195 ; Berlin ; Germany
  
• 关键词：Primal heuristic ; Mixed integer programming ; Domain propagation ; Rounding ; 90C10 ; 90C11 ; 90C59
• 刊名：Journal of Heuristics
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：21
• 期：1
• 页码：73-106
• 全文大小：614 KB
• 参考文献：1. Achterberg, T.: SCIP鈥攁 framework to integrate constraint and mixed integer programming. Tech. Rep. 04鈥?9, Zuse Institute Berlin (2004). http://www.zib.de/Publications/abstracts/ZR-04-19/
  2. Achterberg, T.: Constraint integer programming. Ph.D. thesis, TU Berlin (2007)
  3. Achterberg, T., Berthold, T.: Improving the feasibility pump. Discret. Optim. Spec. Issue 4(1), 77鈥?6 (2007) CrossRef
  4. Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 1鈥?2 (2006) CrossRef
  5. Achterberg, T., Berthold, T., Hendel, G.: Rounding and propagation heuristics for mixed integer programming. In: Klatte, D., L眉thi, H.J., Schmedders, K. (eds.) Operations Research Proceedings 2011, pp. 71鈥?6. Springer, Berlin (2012) 3-642-29210-1_12" target="_blank" title="It opens in new window">CrossRef
  6. Andersen, E., Andersen, K.: Presolving in linear programming. Math. Program. 71, 221鈥?45 (1995)
  7. Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G.: OCTANE: a new heuristic for pure 0鈥? programs. Oper. Res. 49(2), 207鈥?25 (2001) 3535" target="_blank" title="It opens in new window">CrossRef
  8. Balas, E., Schmieta, S., Wallace, C.: Pivot and shift鈥攁 mixed integer programming heuristic. Discret. Optim. 1(1), 3鈥?2 (2004) 3.001" target="_blank" title="It opens in new window">CrossRef
  9. Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discret. Optim. Spec. Issue 4(1), 63鈥?6 (2007) CrossRef
  10. Berthold, T.: Primal heuristics for mixed integer programs. Diploma thesis, Technische Universit盲t Berlin (2006)
  11. Berthold, T.: Heuristics of the branch-cut-and-price-framework SCIP. In: Kalcsics, J., Nickel, S. (eds.) Operations Research Proceedings 2007, pp. 31鈥?6. Springer, Berlin (2008) 3-540-77903-2_5" target="_blank" title="It opens in new window">CrossRef
  12. Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611鈥?14 (2013) 3.08.007" target="_blank" title="It opens in new window">CrossRef
  13. Berthold, T., Feydy, T., Stuckey, P.J.: Rapid learning for binary programs. In: Lodi, A., Milano, M., Toth, P. (eds.) Proceedings of the CPAIOR 2010. LNCS, vol. 6140, pp. 51鈥?5. Springer, Berlin (2010)
  14. Bessiere, C.: Constraint propagation. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming. Chap. 3, pp. 29鈥?3. Elsevier, Amsterdam (2006) CrossRef
  15. Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.: An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12鈥?5 (1998)
  16. Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: MIP: theory and practice鈥攃losing the gap. In: Powell, M., Scholtes, S. (eds.) Systems Modelling and Optimization: Methods, Theory, and Applications, pp. 19鈥?9. Kluwer Academic Publisher, Dordrecht (2000) 387-35514-6_2" target="_blank" title="It opens in new window">CrossRef
  17. Brearley, A., Mitra, G., Williams, H.: Analysis of mathematical programming problems prior to applying the simplex algorithm. Math. Program. 8, 54鈥?3 (1975) CrossRef
  18. COIN-OR branch-and-cut MIP solver. https://projects.coin-or.org/Cbc. Accessed 15 Dec 2014
  19. Danna, E., Rothberg, E., Pape, C.L.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. A 102(1), 71鈥?0 (2004) CrossRef
  20. FICO Xpress-Optimizer. http://www.fico.com/en/Products/DMTools/xpress-overview/Pages/Xpress-Optimizer.aspx. Accessed 15 Dec 2014
  21. Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. C 1, 201鈥?22 (2009) 32-009-0007-3" target="_blank" title="It opens in new window">CrossRef
  22. Fischetti, M., Lodi, A.: Heuristics in mixed integer programming. In: Cochran, J.J., Cox, L.A., Keskinocak, P., Kharoufeh, J.P., Smith, J.C. (eds.) Wiley Encyclopedia of Operations Research and Management Science. Wiley, New York (2010). Online publication.
  23. Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104(1), 91鈥?04 (2005) 3" target="_blank" title="It opens in new window">CrossRef
  24. Ghosh, S.: DINS, a MIP improvement heuristic. In: Fischetti, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization (IPCO 2007). LNCS, vol. 4513, pp. 310鈥?23. Springer, Heidelberg (2007) 3-540-72792-7_24" target="_blank" title="It opens in new window">CrossRef
  25. Glover, F., Laguna, M.: General purpose heuristics for integer programming - part I. J. Heuristics 2(4), 343鈥?58 (1997a) 32504" target="_blank" title="It opens in new window">CrossRef
  26. Glover, F., Laguna, M.: General purpose heuristics for integer programming鈥攑art II. J. Heuristics 3(2), 161鈥?79 (1997b) 3/A:1009631530787" target="_blank" title="It opens in new window">CrossRef
  27. Glover, F., L酶kketangen, A., Woodruff, D.L.: Scatter search to generate diverse MIP solutions. In: Laguna, M., Gonz谩lez-Velarde, J.L. (eds.) Computing Tools for Modeling, Optimization and Simulation. Operations Research/Computer Science Interfaces Series, vol. 12, pp. 299鈥?17. Springer US (2000)
  28. GUROBI Optimizer. http://www.gurobi.com/products/gurobi-optimizer/gurobi-overview. Accessed 15 Dec 2014
  29. Hansen, P., Mladenovi膰, N., Uro拧evi膰, D.: Variable neighborhood search and local branching. Comput. Oper. Res. 33(10), 3034鈥?045 (2006) 33" target="_blank" title="It opens in new window">CrossRef
  30. Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. Int. Jt. Conf. Artif. Intell. 14, 607鈥?15 (1995)
  31. Hendel, G.: New rounding and propagation heuristics for mixed integer programming. Bachelor鈥檚 thesis, TU Berlin (2011)
  32. Ibm, ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. Accessed 15 Dec 2014
  33. Jussien, N., Lhomme, O.: Local search with constraint propagation and conflict-based heuristics. Artif. Intell. 139(1), 21鈥?5 (2002) 3702(02)00221-7" target="_blank" title="It opens in new window">CrossRef
  34. 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鈥?63 (2011) 32-011-0025-9" target="_blank" title="It opens in new window">CrossRef
  35. Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the travelling-salesman problem. Oper. Res. 21, 498鈥?16 (1973) CrossRef
  36. Lodi, A.: The heuristic (dark) side of MIP solvers. In: Talbi, E.G. (ed.) Hybrid Metaheuristics, Studies in Computational Intelligence, vol. 434, pp. 273鈥?84. Springer, Berlin (2013). doi:10.1007/978-3-642-30671-6_10
  37. L酶kketangen, A.: Heuristics for 0鈥? mixed integer programming. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimization. Oxford University Press (2002)
  38. L酶kketangen, A., Glover, F.: Solving zero/one mixed integer programming problems using Tabu search. Eur. J. Oper. Res. 106, 624鈥?58 (1998) 377-2217(97)00295-6" target="_blank" title="It opens in new window">CrossRef
  39. Mare膷ek, J.: Exploiting structure in integer programs. Ph.D. thesis, University of Nottingham (2011)
  40. Minton, S., Johnston, M.D., Philips, A.B., Laird, P.: Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. In: Proceedings of the eighth National conference on Artificial intelligence, pp. 17鈥?4. AAAI Press (1990)
  41. Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient SAT solver. In: Annual ACM IEEE Design Automation Conference, pp. 530鈥?35. ACM (2001)
  42. Pesant, G., Quimper, C.G., Zanarini, A.: Counting-based search: branching heuristics for constraint satisfaction problems. J. Artif. Intell. Res. 43(1), 173鈥?10 (2012)
  43. Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19(4), 534鈥?41 (2007) CrossRef
  44. Rothberg, E.: Personal communication (2013)
  45. Ruml, W.: Incomplete tree search using adaptive probing. In: International Joint Conference on Artificial Intelligence, pp. 235鈥?41 (2001)
  46. Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6, 445鈥?54 (1994) CrossRef
  47. SCIP. Solving Constraint Integer Programs. http://scip.zib.de/. Accessed 15 Dec 2014
  48. Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), AAAI 鈥?4, pp. 337鈥?43. American Association for Artificial Intelligence (1994)
  49. SoPlex. An open source LP solver implementing the revised simplex algorithm. http://soplex.zib.de/. Accessed 15 Dec 2014
  50. SYMPHONY. development home page. https://projects.coin-or.org/SYMPHONY. Accessed 15 Dec 2014
  51. Wallace, C.: ZI round, a MIP rounding heuristic. J. Heuristics 16(5), 715鈥?22 (2010) 32-009-9114-6" target="_blank" title="It opens in new window">CrossRef
  52. Walser, J.P.: Integer Optimization by Local Search, Lecture Notes in Computer Science, vol. 1637. Springer, Berlin (1999) 3-540-48369-1" target="_blank" title="It opens in new window">CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Artificial Intelligence and Robotics
  Calculus of Variations and Optimal Control
  
• 出版者：Springer Netherlands
• ISSN：1572-9397

文摘

In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics.