Refine
Year of publication
Document Type
- Article (41)
- ZIB-Report (38)
- In Proceedings (20)
- Book chapter (2)
- Software (2)
- In Collection (1)
- Proceedings (1)
Keywords
We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.
Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework
(2020)
Lattice-based cryptography has received attention as a next-generation encryption technique, because it is believed to be secure against attacks by classical and quantum computers. Its essential security depends on the hardness of solving the shortest vector problem (SVP). In the cryptography, to determine security levels, it is becoming significantly more important to estimate the hardness of the SVP by high-performance computing. In this study, we develop the world’s first distributed and asynchronous parallel SVP solver, the MAssively Parallel solver for SVP (MAP-SVP). It can parallelize algorithms for solving the SVP by applying the Ubiquity Generator framework, which is a generic framework for branch-and-bound algorithms. The MAP-SVP is suitable for massive-scale parallelization, owing to its small memory footprint, low communication overhead, and rapid checkpoint and restart mechanisms. We demonstrate its performance and scalability of the MAP-SVP by using up to 100,032 cores to solve instances of the Darmstadt SVP Challenge.
In designing energy supply systems, designers should heighten the robustness in performance criteria against the uncertainty in energy demands. In this paper, a robust optimal design method using a hierarchi- cal mixed-integer linear programming (MILP) method is proposed to maximize the robustness of energy sup- ply systems under uncertain energy demands based on a mixed-integer linear model. A robust optimal design problem is formulated as a three-level min-max-min MILP one by expressing uncertain energy demands by intervals, evaluating the robustness in a performance criterion based on the minimax regret cri- terion, and considering relationships among integer design variables, uncertain energy demands, and inte- ger and continuous operation variables. This problem is solved by evaluating upper and lower bounds for the minimum of the maximum regret of the performance criterion repeatedly outside, and evaluating lower and upper bounds for the maximum regret repeatedly inside. Since these different types of optimization problems are difficult to solve even using commercial MILP solvers, they are solved by applying a hierarchi- cal MILP method developed for ordinary optimal design problems with its modifications. In a case study, the proposed approach is applied to the robust optimal design of a cogeneration system. Through the study, its validity and effectiveness are ascertained, and some features of the obtained robust designs are clarified.
The mixed-integer linear programming (MILP) method has been applied widely to optimal design of energy supply systems. A hierarchical MILP method has been proposed to solve such optimal design problems effi- ciently. As one of the strategies to enhance the computation efficiency furthermore, a method of reducing model by time aggregation has been proposed to search design candidates accurately and efficiently in the relaxed optimal design problem at the upper level. In this paper, the hierarchical MILP method and model reduction by time aggregation are applied to the multiobjective optimal design. In applying the model reduc- tion, the methods of clustering periods by the order of time series, based on an operational strategy, and by the k-medoids method are applied. As a case study, the multiobjective optimal design of a gas turbine cogeneration system with a practical configuration is investigated by adopting the annual total cost and pri- mary energy consumption as the objective functions to be minimized simultaneously, and the clustering methods are compared with one another in terms of the computation efficiency. It turns out that the model reduction by any clustering method is effective to enhance the computation efficiency when importance is given to minimizing the first objective function. It also turns out that the model reduction only by the k- medoids method is effective very limitedly when importance is given to minimizing the second objective function.
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.
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.
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.
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.