Previous Articles     Next Articles

TACKLING INDUSTRIAL-SCALE SUPPLY CHAIN PROBLEMS BY MIXED-INTEGER PROGRAMMING

Gerald Gamrath1, Ambros Gleixner1, Thorsten Koch1, Matthias Miltenberger1, Dimitri Kniasew2, Dominik Schlögel2, Alexander Martin3, Dieter Weninger3   

  1. 1 Zuse Institute Berlin, Department Optimization;
    2 SAP SE, SAP Optimization;
    3 Friedrich-Alexander-Universität Erlangen-Nürnberg, Department Mathematics
  • Received:2019-02-26 Revised:2019-05-05 Online:2019-12-15 Published:2019-12-15

Gerald Gamrath, Ambros Gleixner, Thorsten Koch, Matthias Miltenberger, Dimitri Kniasew, Dominik Schlögel, Alexander Martin, Dieter Weninger. TACKLING INDUSTRIAL-SCALE SUPPLY CHAIN PROBLEMS BY MIXED-INTEGER PROGRAMMING[J]. Journal of Computational Mathematics, 2019, 37(6): 866-888.

The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP.

CLC Number: 

[1] H. Stadtler, B. Fleischmann, M. Grunow, H. Meyr and C. Sürie, Advanced Planning in Supply Chains, Management for Professionals, Springer-Verlag Berlin Heidelberg, 2012.

[2] T. Achterberg, SCIP:Solving Constraint Integer Programs Mathematical Programming Computation, 1:1(2009), 1-41.

[3] E. Klotz, Identification, assessment, and correction of ill-conditioning and numerical instability in linear and integer programs, A. Newman and J. Leung, editors, Bridging Data and Decisions, TutORials in Operations Research, pages 54-108, 2014.

[4] R. Bixby and E. Rothberg, Progress in computational mixed integer programming-a look back from the other side of the tipping point, Annals of Operations Research, 149(2007), 37-41.

[5] T. Achterberg and R. Wunderling, Mixed integer programming:Analyzing 12 years of progress, M. Jünger and G. Reinelt, editors, Facets of Combinatorial Optimization, pages 449-481, Springer Berlin Heidelberg, 2013.

[6] G. Gamrath, T. Koch, A. Martin, M. Miltenberger and D. Weninger, Progress in presolving for mixed integer programming, Mathematical Programming Computation, 7:4(2015), 367-398.

[7] T. Berthold and G. Hendel, Shift-and-propagate, Journal of Heuristics, 21:1(2014), 73-106.

[8] M.W.P. Savelsbergh, Preprocessing and probing techniques for mixed integer programming problems, ORSA Journal on Computing, 6(1994), 445-454.

[9] E.L. Johnson and M.W. Padberg, Degree-two inequalities, clique facets, and biperfect graphs, North-Holland Mathematics Studies, 66(1982), 169-187.

[10] H. Marchand and L.A. Wolsey, Aggregation and mixed integer rounding to solve MIPs, Operations Research, 49:3(2001), 363-371.

[11] G. Gamrath, T. Berthold, S. Heinz and M. Winkler, Structure-based primal heuristics for mixed integer programming, Optimization in the Real World, volume 13, pages 37-53, 2015.

[12] C. Wallace, ZI round, a MIP rounding heuristic, Journal of Heuristics, 16:5(2010), 715-722.

[13] M. Fischetti and M. Monaci, Proximity search for 0-1 mixed-integer convex programming, Journal of Heuristics, 20:6(2014), 709-731.

[14] T. Koch, T. Achterberg, E. Andersen, O. Bastert, T. Berthold, R.E. Bixby, E. Danna, G. Gamrath, A.M. Gleixner, S. Heinz, A. Lodi, H. Mittelmann, T. Ralphs, D. Salvagnin, D.E. Steffy and K. Wolter, MIPLIB 2010, Mathematical Programming Computation, 3:2(2011), 103-163.

[15] J.A.J. Hall and K.I.M. McKinnon, Hyper-sparsity in the revised simplex method and how to exploit it, Comp. Opt. and Appl., 32:3(2005), 259-283.

[16] R. Wunderling, Paralleler und objektorientierter Simplex-Algorithmus, PhD thesis, Technische Universität Berlin, 1996.

[17] E. Kostina, The long step rule in the bounded-variable dual simplex method:Numerical experiments, Mathematical Methods of Operations Research, 55:3(2002), 413-429.

[18] J.J. Forrest and D. Goldfarb, Steepest-edge simplex algorithms for linear programming, Mathematical Programming, 57:1(1992), 341-374.

[19] T. Berthold, Measuring the impact of primal heuristics, Operations Research Letters, 41:6(2013), 611-614.
[1] Begoña Cano, Adolfo González-Pachón. PLANE WAVES NUMERICAL STABILITY OF SOME EXPLICIT EXPONENTIAL METHODS FOR CUBIC SCHRÖDINGER EQUATION [J]. Journal of Computational Mathematics, 2016, 34(4): 385-406.
[2] Weihua Deng, Minghua Chen. EFFICIENT NUMERICAL ALGORITHMS FOR THREE-DIMENSIONAL FRACTIONAL PARTIAL DIFFERENTIAL EQUATIONS [J]. Journal of Computational Mathematics, 2014, 32(4): 371-391.
[3] Xin Leng, De-gui Liu, Xiao-qiu Song, Li-rong Chen. A Class of Two-step Continuity Runge-kutta Methods for Solving Singular Delay Differential Equations and Its Stability Analysis [J]. Journal of Computational Mathematics, 2005, 23(6): 647-656.
[4] Yue-xin Yu, Shou-fu Li. Stability Analysis of Runge-Kutta Methods for Nonlinear Systems of Pantograph Equations [J]. Journal of Computational Mathematics, 2005, 23(4): 351-356.
[5] Si-qing Gan, Wei-min Zheng . STABILITY OF GENERAL LINEAR METHODS FOR SYSTEMS OF FUNCTIONAL-DIFFERENTIAL AND FUNCTIONAL EQUATIONS [J]. Journal of Computational Mathematics, 2005, 23(1): 37-128.
[6] Hong Jiong TIAN,Jiao Xun KUANG,Lin QIU. THE STABILITY OF LINEAR MULTISTEP METHODS FOR LINEAR SYSTEMS OF NEUTRAL DIFFERENTIAL EQUATIONS [J]. Journal of Computational Mathematics, 2001, 19(2): 125-130.
[7] Lin QIU, Taketomo Mitsui,Jiao Xun KUANG. The numerical stability of the θ-method for delay differential equations with many variable delays [J]. Journal of Computational Mathematics, 1999, 17(5): 523-532.
Viewed
Full text


Abstract