Could we use a million cores to solve an integer program?

• Aardal K, Weismantel R, Wolsey LA (2002) Non-standard approaches to integer programming. Discret Appl Math 123: 5–74

  Article  MathSciNet  MATH  Google Scholar 

• Achterberg T (2009) SCIP: solving constraint integer programs. Math Program Comput 1(1): 1–41

  Article  MathSciNet  MATH  Google Scholar 

• Achterberg T, Berthold T (2009) Hybrid branching. In: Van Hoeve W-J, Hooker J (eds) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, vol 5547 of lecture notes in computer science. Springer, Heidelberg, pp 309–311

  Chapter  Google Scholar 

• Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper Res Lett 33: 42–54

  Article  MathSciNet  MATH  Google Scholar 

• Achterberg T, Koch T, Martin A (2006) MIPLIB 2003. Oper Res Lett 34(4): 361–372

  Article  MathSciNet  MATH  Google Scholar 

• Applegate DL, Bixby RE, Chvatal V, Cook WJ (2007) The traveling salesman problem: a computational study. Princeton University Press, Princeton

  Google Scholar 

• Barahona F, Anbil R (2000) The volume algorithm: producing primal solutions with a subgradient method. Math Program 87: 385–399

  Article  MathSciNet  MATH  Google Scholar 

• Benson H, Shanno D (2007) An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming. Comput Optim Appl 38: 371–399

  Article  MathSciNet  MATH  Google Scholar 

• Berthold T, Pfetsch ME (2009) Detecting orbitopal symmetries. In: Fleischmann B, Borgwardt KH, Klein R, Tuma A (eds) Operations research proceedings 2008. Springer, Berlin, pp 433–438

  Chapter  Google Scholar 

• Bienstock D (2001) Approximation algorithms for linear programming: theory and practice. CORE lecture series, Core, UCL, Belgium

• Bixby R, Martin A (2000) Parallelizing the dual simplex method. INFORMS J Comput 12: 45–56

  Article  MathSciNet  MATH  Google Scholar 

• Bixby RE (2002) Solving real-world linear programs: a decade and more of progress. Oper Res 50(1): 3–15

  Article  MathSciNet  MATH  Google Scholar 

• Bixby RE (2009) Lectures about LP and MIP solving at combinatorial optimization at work II

• Bixby RE, Saltzman MJ (1994) Recovering an optimal basis from an interior point solution. Oper Res Lett 15: 169–178

  Article  MathSciNet  MATH  Google Scholar 

• Borndörfer R, Löbel A, Weider S (2008) A bundle method for integrated multi-depot vehicle and duty scheduling in public transit. In: Hickman M, Mirchandani P, Voß S (eds) Computer-aided systems in public transport, vol 600 of lecture notes in economics and mathematical systems. Springer, Berlin, pp 3–24

  Chapter  Google Scholar 

• Coleman TF, Czyzyk J, Sun C, Wagner M, Wright SJ (1997) ppcx: parallel software for linear programming. In: Proceedings of the eighth SIAM conference on parallel processing in scientific computing. SIAM. http://www.cs.cornell.edu/Info/People/mwagner/pPCx/paper.ps

• Cook W, Koch T, Steffy D, Wolter K (2011) An exact rational mixed integer programming solver. In: Proceedings of the 15th conference on integer programming and combinatorial optimization. Springer, Beriin, pp 104–116

  Google Scholar 

• Cook W, Rutherford T, Scarf HE, Shallcross D (1993) An implementation of the generalized basis reduction algorithm for integer programming. ORSA J Comput 5(2): 206–212

  Article  MathSciNet  MATH  Google Scholar 

• Cornùejols G, Karamanov M, Li Y (2006) Early estimates of the size of branch-and-bound trees. INFORMS J Comput 18(1): 86–96

  Article  MathSciNet  MATH  Google Scholar 

• Curtis FE, Schenk O, Wächter A (2010) An interior-point algorithm for large-scale nonlinear optimization with inexact step computations. SIAM J Sci Comput 32(6): 3447–3475

  Article  MathSciNet  MATH  Google Scholar 

• Fisher ML (2004) The lagrangian relaxation method for solving integer programming problems. Manag Sci 50(12): 1861–1871

  Article  Google Scholar 

• Gamrath G, Lübbecke M (2010) Experiments with a generic Dantzig-Wolfe decomposition for integer programs. In: Festa P (ed) Experimental algorithms, vol 6049 of lecture notes in computer science. Springer, Berlin, pp 239–252

  Google Scholar 

• Gondzio J (1998) Warm start of the primal-dual method applied in the cutting-plane scheme. Math Program 83: 125–143

  MathSciNet  MATH  Google Scholar 

• Grötschel M, Jünger M, Reinelt G (1984) A cutting plane algorithm for the linear ordering problem. Oper Res 32(6): 1195–1220

  Article  MathSciNet  MATH  Google Scholar 

• Gupta A, Kumar V (1994) A scalable parallel algorithm for sparse cholesky factorization. In: Proceedings of the 1994 conference on supercomputing, supercomputing ’94, IEEE Computer Society Press, Los Alamitos, CA, USA, pp 793–802

• Hall J (2010) Towards a practical parallelisation of the simplex method. Comput Manag Sci 7: 139–170

  Article  MathSciNet  MATH  Google Scholar 

• Helmberg C, Kiwiel K (2002) A spectral bundle method with bounds. Math Program 93: 173–194

  Article  MathSciNet  MATH  Google Scholar 

• Ivanov ID, de Klerk E (2007) Parallel implementation of a semidefinite programming solver based on CSDP in a distributed memory cluster. Technical Report CentER Discussion Paper 2007-20. Tilburg University, The Netherlands

• John E, Yildirim EA (2008) Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension. Comput Optim Appl 41: 151–183

  Article  MathSciNet  MATH  Google Scholar 

• Klabjan D, Johnson EL, Nemhauser GL (2000) A parallel primal-dual simplex algorithm. Oper Res Lett 27(2): 47–55

  Article  MathSciNet  MATH  Google Scholar 

• Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna E, Gamrath G, Gleixner AM, Heinz S, Lodi A, Mittelmann H, Ralphs T, Salvagnin D, Steffy DE, Wolter K (2011) MIPLIB 2010. Math Program Comput 3: 103–163

  Article  MathSciNet  Google Scholar 

• Kumar V, Rao VN (1987) Parallel depth-first search, part II: analysis. Int J Parallel Program 16: 501–519

  Article  MathSciNet  MATH  Google Scholar 

• Levinthal D (2009) Performance analysis guide for Intel core i7 processor and Intel Xeon 5500 processors

• Mahajan A, Ralphs TK (2009) Experiments with branching using general disjunctions. In: Proceedings of the leventh INFORMS Computing Society Meeting, pp 101–118

• Mahajan A, Ralphs TK (2010) On the Complexity of selecting disjunctions in integer programming. SIAM J Optim 20(5): 2181–2198

  Article  MathSciNet  MATH  Google Scholar 

• Margot F (2010) Symmetry in integer linear programming. In: Jünger M, Liebling T, Naddef D, Nemhauser G, Pulleyblank W, Reinelt G, Rinaldi G, Wolsey L (eds) Fifty years of integer programming: 1958–2008. Springer, Berlin, pp 647–686

  Chapter  Google Scholar 

• Megiddo N (1991) On finding primal—and dual-optimal bases. ORSA J Comput 3(1): 63–65

  Article  MathSciNet  MATH  Google Scholar 

• Olszewski M, Ansel J, Amarasinghe S (2009) Kendo: efficient deterministic multithreading in software. SIGPLAN Not 44: 97–108

  Article  Google Scholar 

• Özaltin OY, Hunsaker B, Schaefer AJ (2011) Predicting the solution time of branch-and-bound algorithms for mixed-integer programs. INFORMS J Comput 23(3): 392–403

  Article  MathSciNet  Google Scholar 

• Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev 33: 60–100

  Article  MathSciNet  MATH  Google Scholar 

• Paper W (2010) SGI Altix global shared memory performance and productivity breakthroughs for the SGI Altix UV. http://www.sgi.com/pdfs/4250.pdf

• Phillips C, Eckstein J, Hart W (2006) Massively parallel mixed-integer programming: algorithms and applications. In: Heroux M, Raghavan P, Simon H (eds) Parallel processing for scientific computing. SIAM Books, Philadelphia, pp 323–340

  Chapter  Google Scholar 

• Rothberg E (2010) Barrier is from mars, simplex is from venus. Talk given at What a pivot–workshop honouring the 65th birthday of Bob Bixby in Erlangen, Germany

• Schroeder B, Pinheiro E, Weber W-D (2009) DRAM errors in the wild: a large-scale field study. In: Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems, SIGMETRICS ’09, ACM, pp 193–204

• Shinano Y, Achterberg T, Berthold T, Heinz S, Koch T (2012) ParaSCIP—a parallel extension of SCIP. In: Bischof C, Hegering H-G, Nagel WE, Wittum G (eds) Competence in high performance computing 2010. Springer, Berlin, pp 135–148

  Google Scholar 

• Wolsey LA (1998) Integer programming. Wiley-Interscience, New York

  MATH  Google Scholar 

• Wulf WA, McKee SA (1995) Hitting the memory wall: implications of the obvious. SIGARCH Comput Archit News 23: 20–24

  Article  Google Scholar 

• Wunderling R (1996) Paralleler und objektorientierter Simplex-Algorithmus. PhD thesis, Technische Universität, Berlin

• Xu Y, Ralphs TK, Ladányi L, Saltzman MJ (2009) Computational experience with a software framework for parallel integer programming. INFORMS J Comput 21: 383–397

  Article  MathSciNet  Google Scholar 

• Yamashita M, Fujisawa K (2010) Efficient parallel software for large-scale semidefinite programs. In: Proceedings of the 2010 IEEE multi-conference on systems and control

• Yamashita M, Fujisawa K, Kojima M (2003) SDPARA : semidefinite programming algorithm parallel version. Parallel Comput 29: 1053–1067

  Article  MathSciNet  Google Scholar 

• Yildirim A, Stephen, Wright S (2000) Warm-start strategies in interior-point methods for linear programming. SIAM J Optim 12: 782–810

  Article  Google Scholar 

Download references