Numerically Safe Lower Bounds for the Capacitated Vehicle Routing Problem

References

• Applegate D, Bixby RE, Chvátal V, Cook WJ (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Applegate D, Cook WJ, Dash S, Espinoza D (2007) Exact solutions to linear programming problems. Oper. Res. Lett. 35(6):693–699.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Chvátal V, Cook W, Espinoza D (2013) Local cuts for mixed-integer programming. Math. Programming Comput. 5(2):171–200.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, Cham, Switzerland).Crossref, Google Scholar
• Contardo C, Martinelli R (2014) A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optim. 12:129–146.Crossref, Google Scholar
• Cook W, Dash S, Fukasawa R, Goycoolea M (2009) Numerically safe Gomory mixed-integer cuts. INFORMS J. Comput. 21(4):641–649.Link, Google Scholar
• Cook WJ, Koch T, Steffy D, Wolter K (2011) An exact rational mixed-integer programming solver. Günlük O, Woeginger G, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 6655 (Springer, Berlin), 104–116.Crossref, Google Scholar
• Cook WJ, Koch T, Steffy D, Wolter K (2013) A hybrid branch-and-bound approach for exact rational mixed-integer programming. Math. Programming Comput. 5(3):305–344.Crossref, Google Scholar
• Cornuéjols G, Margot F, Nannicini G (2013) On the safety of gomory cut generators. Math. Programming Comput. 5(4):345–395.Crossref, Google Scholar
• CVRPLIB (2014) Capacitated vehicle routing problem library. Accessed April 4, 2017, http://vrp.atd-lab.inf.puc-rio.br.Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Espinoza DG (2006) On linear programming, integer programming and cutting planes. Unpublished doctoral dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta.Google Scholar
• Fischetti M, Lodi A (2003) Local branching. Math. Programming 98(1–3):23–47.Crossref, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, de Aragão MP, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• GCC Bugzilla (2006) Optimization breaks floating point exception flag reading. Accessed April 15, 2015, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=29186.Google Scholar
• GCC Bugzilla (2008) Optimization generates incorrect code with -frounding-math option. Accessed April 15, 2015, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=34678.Google Scholar
• Goldberg D (1991) What every computer scientist should know about floating-point arithmetic. ACM Comput. Surveys (CSUR) 23(1):5–48.Crossref, Google Scholar
• Held S, Cook WJ, Sewell EC (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• IEEE (1985) Standard 754–1985. IEEE Standard for Binary Floating-Point Arithmetic (Institute of Electrical and Electronics Engineers, New York).Google Scholar
• ILOG I (2013) CPLEX 12.6. Accessed April 4, 2017, https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html.Google Scholar
• Irnich S, Villeneuve D (2006) The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J. Comput. 18(3):391–406.Link, Google Scholar
• ISO/IEC (1999) Programming languages—C. International Organization for Standardization. Standard ISO/IEC 9899:1999. Accessed April 4, 2017, https://www.iso.org/standard/29237.html.Google Scholar
• Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna Eet al. (2011) MIPLIB 2010. Math. Programming Comput. 3(2):103–163.Crossref, Google Scholar
• Letchford A, Eglese R, Lysgaard J (2002) Multistars, partial multistars and the capacitated vehicle routing problem. Math. Programming 94(1):21–40.Crossref, Google Scholar
• LLVM Bugzilla (2010) Clang/LLVM don’t support C99 FP rounding mode pragmas. Accessed May 24, 2015, https://llvm.org/bugs/show_bug.cgi?id=8100.Google Scholar
• Lysgaard J, Letchford A, Eglese R (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Neumaier A, Shcherbina O (2004) Safe bounds in linear and mixed-integer linear programming. Math. Programming 99(2):283–296.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2014) Improved branch-cut-and-price for capacitated vehicle routing. Lee J, Vygen J, eds. Integer Programming and Combinatorial Optimization (Springer, Cham, Switzerland), 393–403.Crossref, Google Scholar
• Steffy DE (2011) Topics in exact precision mathematical programming. Unpublished doctoral dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta.Google Scholar
• Steffy DE, Wolter K (2013) Valid linear programming bounds for exact mixed-integer programming. INFORMS J. Comput. 25(2):271–284.Link, Google Scholar