@misc{HosodaMaherShinanoetal.2023, author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji and Villumsen, Jonas Christoffer}, title = {A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89700}, year = {2023}, abstract = {Consolidation of commodities and coordination of vehicle routes are fundamental features of supply chain management problems. While locations for consolidation and coordination are typically known a priori, in adaptive transportation networks this is not the case. The identification of such consolidation locations forms part of the decision making process. Supply chain management problems integrating the designation of consolidation locations with the coordination of long haul and local vehicle routing is not only challenging to solve, but also very difficult to formulate mathematically. In this paper, the first mathematical model integrating location clustering with long haul and local vehicle routing is proposed. This mathematical formulation is used to develop algorithms to find high quality solutions. A novel parallel framework is developed that combines exact and heuristic methods to improve the search for high quality solutions and provide valid bounds. The results demonstrate that using exact methods to guide heuristic search is an effective approach to find high quality solutions for difficult supply chain management problems.}, language = {en} } @misc{GamrathAndersonBestuzhevaetal.2020, author = {Gamrath, Gerald and Anderson, Daniel and Bestuzheva, Ksenia and Chen, Wei-Kun and Eifler, Leon and Gasse, Maxime and Gemander, Patrick and Gleixner, Ambros and Gottwald, Leona and Halbig, Katrin and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and Le Bodic, Pierre and Maher, Stephen J. and Matter, Frederic and Miltenberger, Matthias and M{\"u}hmer, Erik and M{\"u}ller, Benjamin and Pfetsch, Marc and Schl{\"o}sser, Franziska and Serrano, Felipe and Shinano, Yuji and Tawfik, Christine and Vigerske, Stefan and Wegscheider, Fabian and Weninger, Dieter and Witzig, Jakob}, title = {The SCIP Optimization Suite 7.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-78023}, year = {2020}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders' decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders' decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @article{HosodaMaherShinanoetal.2024, author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji and Villumsen, Jonas Christoffer}, title = {A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network}, volume = {165}, journal = {Computers \& Operations Research}, publisher = {Elsevier BV}, issn = {0305-0548}, doi = {10.1016/j.cor.2024.106570}, year = {2024}, abstract = {Consolidation of commodities and coordination of vehicle routes are fundamental features of supply chain management problems. While locations for consolidation and coordination are typically known a priori, in adaptive transportation networks this is not the case. The identification of such consolidation locations forms part of the decision making process. Supply chain management problems integrating the designation of consolidation locations with the coordination of long haul and local vehicle routing is not only challenging to solve, but also very difficult to formulate mathematically. In this paper, the first mathematical model integrating location clustering with long haul and local vehicle routing is proposed. This mathematical formulation is used to develop algorithms to find high quality solutions. A novel parallel framework is developed that combines exact and heuristic methods to improve the search for high quality solutions and provide valid bounds. The results demonstrate that using exact methods to guide heuristic search is an effective approach to find high quality solutions for difficult supply chain management problems.}, language = {en} } @misc{HosodaMaherShinanoetal.2021, author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji and Villumsen, Jonas Christoffer}, title = {Location, transshipment and routing: An adaptive transportation network integrating long-haul and local vehicle routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83438}, year = {2021}, abstract = {The routing of commodities is a tactical problem in supply chain management that aims to synchronise transportation services connecting a network of warehouses and consolidation locations. This paper considers the routing of commodities in a transportation network that is flexible in response to demand through changes to regional warehouse clustering and the designation of consolidation locations. Traditionally, warehouse clustering and consolidation locations are determined as part of strategic planning that is performed months to years in advance of operations---limiting the flexibility in transportation networks to respond to changes in demand. A mathematical programming-based algorithmic framework is proposed to integrate the strategic decisions of location planning with tactical decisions of vehicle routing and synchronisation. A multi-armed bandit problem is developed to explore warehouse clustering decisions and exploit those that lead to small transportation costs. An extensive computational study will show that the proposed algorithmic framework effectively integrates strategic and tactical planning decisions to reduce the overall transportation costs.}, language = {en} } @misc{MaherRalphsShinano2019, author = {Maher, Stephen J. and Ralphs, Ted and Shinano, Yuji}, title = {Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74702}, year = {2019}, abstract = {Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous work has been focused on classical sequential algorithms. Since parallel computation has become increasingly mainstream, it is necessary to re-examine and modernize these practices. In this paper, we propose a framework for assessment based on the notion that resource consumption is at the heart of what we generally refer to as the "effectiveness" of an implementation. The proposed framework carefully distinguishes between an implementation's baseline efficiency, the efficacy with which it utilizes a fixed allocation of resources, and its scalability, a measure of how the efficiency changes as resources (typically additional computing cores) are added or removed. Efficiency is typically applied to sequential implementations, whereas scalability is applied to parallel implementations. Efficiency and scalability are both important contributors in determining the overall effectiveness of a given parallel implementation, but the goal of improved efficiency is often at odds with the goal of improved scalability. Within the proposed framework, we review the challenges to effective evaluation and discuss the strengths and weaknesses of existing methods of assessment.}, language = {en} } @misc{GleixnerMaherMuelleretal.2017, author = {Gleixner, Ambros and Maher, Stephen J. and M{\"u}ller, Benjamin and Pedroso, Jo{\~a}o Pedro}, title = {Exact Methods for Recursive Circle Packing}, doi = {10.1007/s10479-018-3115-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62039}, year = {2017}, abstract = {Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig-Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.}, language = {en} } @misc{HosodaMaherShinano2024, author = {Hosoda, Junko and Maher, Stephen J. and Shinano, Yuji}, title = {Combining Benders' decomposition and parallelisation to solve large-scale adaptive network supply chain management problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98744}, year = {2024}, abstract = {Integrated supply chain network design—combining warehouse clustering with inter- and intra-cluster vehicle routing—is a fundamental feature of supply chain management problems. In this paper, a Benders' decomposition-based parallel heuristic approach for the integrated long-haul and local vehicle routing problem is proposed. The proposed algorithm comprises lower- and upper-bound search algorithms running in parallel to find high-quality solutions for challenging supply chain management problems. A novel Benders' decomposition approach is proposed to aid the improvement in the lower bound for large-scale problems. The results demonstrate that the Benders' decomposition approach is effective in finding strong lower bounds and is beneficial for obtaining high-quality solutions.}, language = {en} } @misc{GleixnerBastubbeEifleretal.2018, author = {Gleixner, Ambros and Bastubbe, Michael and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Schubert, Christoph and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Walter, Matthias and Wegscheider, Fabian and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 6.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69361}, year = {2018}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders' decomposition in a generic framework. GCG's detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders' framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @misc{MaherFischerGallyetal.2017, author = {Maher, Stephen J. and Fischer, Tobias and Gally, Tristan and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Robert Lion and Hendel, Gregor and Koch, Thorsten and L{\"u}bbecke, Marco and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Weninger, Dieter and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 4.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62170}, year = {2017}, abstract = {The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences.}, language = {en} } @misc{GamrathFischerGallyetal.2016, author = {Gamrath, Gerald and Fischer, Tobias and Gally, Tristan and Gleixner, Ambros and Hendel, Gregor and Koch, Thorsten and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Vigerske, Stefan and Weninger, Dieter and Winkler, Michael and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 3.2}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57675}, year = {2016}, abstract = {The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.}, language = {en} }