Library

Description: In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.

Description: To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function to be minimized are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified.

Description: Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.

Description: PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.

Description: The Ubiquity Generator (UG) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. In this paper, we present ParaXpress, a distributed memory parallelization of the powerful commercial MIP solver FICO Xpress. Besides sheer performance, an important feature of Xpress is that it provides an internal parallelization for shared memory systems. When aiming for a best possible performance of ParaXpress on a supercomputer, the question arises how to balance the internal Xpress parallelization and the external parallelization by UG against each other. We provide computational experiments to address this question and we show computational results for running ParaXpress on a Top500 supercomputer, using up to 43,344 cores in parallel.

Description: In designing energy supply systems, designers are requested to rationally determine equipment types, capacities, and numbers in consideration of equipment operational strategies corresponding to seasonal and hourly variations in energy demands. However, energy demands have some uncertainty at the design stage, and the energy demands which become certain at the operation stage may differ from those estimated at the design stage. Therefore, designers should consider that energy demands have some uncertainty, evaluate the performance robustness against the uncertainty, and design the systems to heighten the robustness. Especially, this issue is important for cogeneration plants, because their performances depend significantly on both heat and power demands. Although robust optimal design methods of energy supply systems under uncertain energy demands were developed, all of them are based on linear models for energy supply systems. However, it is still a hard challenge to develop a robust optimal design method even based on a mixed-integer linear model. At the first step for this challenge, in this paper, a method of evaluating the performance robustness of energy supply systems under uncertain energy demands is proposed based on a mixed-integer linear model. This problem is formulated as a bilevel mixed-integer linear programming one, and a sequential solution method is applied to solve it approximately by discretizing uncertain energy demands within their intervals. In addition, a hierarchical optimization method in consideration of the hierarchical relationship between design and operation variables is applied to solve large scale problems efficiently. Through a case study on a gas turbine cogeneration plant for district energy supply, the validity and effectiveness of the proposed method and features of the performance robustness of the plant are clarified.

Description: PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.

Description: Branch-and-bound (B&B) is an algorithmic framework for solving NP-hard combinatorial optimization problems. Although several well-designed software frameworks for parallel B&B have been developed over the last two decades, there is very few literature about successfully solving previously intractable combinatorial optimization problem instances to optimality by using such frameworks.The main reason for this limited impact of parallel solvers is that the algorithmic improvements for specific problem types are significantly greater than performance gains obtained by parallelization in general. Therefore, in order to solve hard problem instances for the first time, one needs to accelerate state-of-the-art algorithm implementations. In this paper, we present a computational study for solving Steiner tree problems and mixed integer semidefinite programs in parallel. These state-of-the-art algorithm implementations are based on SCIP and were parallelized via the ug[SCIP-*,*]-libraries---by adding less than 200 lines of glue code. Despite the ease of their parallelization, these solvers have the potential to solve previously intractable instances. In this paper, we demonstrate the convenience of such a parallelization and present results for previously unsolvable instances from the well-known PUC benchmark set, widely regarded as the most difficult Steiner tree test set in the literature.

Description: In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.