8280
eng
reportzib
1
--
2021-07-08
--
CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems
Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.
1438-0064
urn:nbn:de:0297-zib-82802
Revised version is accepted to HiPC 2021
publish
Nariaki Tateiwa
Yuji Shinano
Yuji Shinano
Keiichiro Yamamura
Akihiro Yoshida
Shizuo Kaji
Masaya Yasuda
Katsuki Fujisawa
ZIB-Report
21-16
eng
uncontrolled
Discrete optimization
eng
uncontrolled
Lattice problem
eng
uncontrolled
Lattice-based cryptography
eng
uncontrolled
Shortest vector problem
eng
uncontrolled
Parallel algorithms
eng
uncontrolled
Ubiquity Generator Framework
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Shinano, Yuji
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
https://opus4.kobv.de/opus4-zib/files/8280/ZIB-Report-21-16.pdf
7059
eng
reportzib
1
--
2018-09-27
--
Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria
The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds.
1438-0064
urn:nbn:de:0297-zib-70591
Satoshi Ito
Yuji Shinano
Yuji Shinano
ZIB-Report
18-51
eng
uncontrolled
Sports league
eng
uncontrolled
Round-robin tournament
eng
uncontrolled
Tiebreaking criteria
eng
uncontrolled
Clinch number
eng
uncontrolled
Elimination number
eng
uncontrolled
Combinatorial optimization
eng
uncontrolled
Integer programming
Computing Methodologies
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Shinano, Yuji
MODAL-SynLab
MODAL-Gesamt
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/7059/ZIB-Report-18-51.pdf
7839
eng
reportzib
1
--
2020-05-28
--
Solving Previously Unsolved MIP Instances with ParaSCIP on Supercomputers by using up to 80,000 Cores
Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved MIP instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper, we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.
1438-0064
urn:nbn:de:0297-zib-78393
Yuji Shinano
Yuji Shinano
Tobias Achterberg
Timo Berthold
Stefan Heinz
Thorsten Koch
Michael Winkler
ZIB-Report
20-16
eng
uncontrolled
Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP, Ubiquity Generator Framework, MIPLIB
Software
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Mathematical Optimization
Achterberg, Tobias
Berthold, Timo
Heinz, Stefan
Koch, Thorsten
Shinano, Yuji
Winkler, Michael
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/7839/ZIB-Report_20-16.pdf
8130
eng
reportzib
1
--
2021-01-23
--
Solving Challenging Large Scale QAPs
We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method efficiently implemented on a powerful computer system using the Ubiquity Generator(UG) framework that can utilize more than 100,000 cores. Lower bounding procedures incorporated in the branch-and-bound method play a crucial role in solving the problems. For a strong lower bounding procedure, we employ the Lagrangian doubly nonnegative (DNN) relaxation and the Newton-bracketing method developed by the authors’ group. In this report, we describe some basic tools used in the project including the lower bounding procedure and branching rules, and present some preliminary numerical results.
Our next target problem is QAPs with dimension at least 50, as we have succeeded to solve tai30a and sko42 from QAPLIB for the first time.
1438-0064
urn:nbn:de:0297-zib-81303
10.12752/8130
publish
Koichi Fujii
Yuji Shinano
Naoki Ito
Sunyoung Kim
Masakazu Kojima
Yuji Shinano
Kim-Chuan Toh
ZIB-Report
21-02
eng
uncontrolled
QAP
eng
uncontrolled
Parallel Branch-and-Bound
Computing Methodologies
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Shinano, Yuji
HPO-NAVI
Applied Algorithmic Intelligence Methods
https://opus4.kobv.de/opus4-zib/files/8130/ZIB-Report-21-02.pdf
8677
jpn
reportzib
1
--
2022-05-13
--
大規模二次割当問題への挑戦
二次割当問題は線形緩和が弱いことが知られ,強化のため多様な緩和手法が考案されているが,その一つである二重非負値計画緩和( DNN 緩和)及びその解法として近年研究が進んでいるニュートン・ブラケット法を紹介し,それらに基づく分枝限定法の実装及び数値実験結果について報告する.
統計数理研究所共同研究リポート 453
最適化:モデリングとアルゴリズム33 2022年3月
「大規模二次割当問題への挑戦」 p.84-p.92
Solving Large Scale QAPs with DNN-based Branch-and-bound : a progress report
1438-0064
urn:nbn:de:0297-zib-86779
publish
Koichi Fujii
Yuji Shinano
Naoki Ito
Sunyoung Kim
Masakazu Kojima
Yuji Shinano
Kim-Chuan Toh
ZIB-Report
22-11
Mathematics of Computing
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Shinano, Yuji
HPO-NAVI
Applied Algorithmic Intelligence Methods
Zuse Institute Berlin (ZIB)
https://opus4.kobv.de/opus4-zib/files/8677/ZIB-Report_22-11.pdf
8970
eng
reportzib
1
--
2023-01-28
--
A parallel branch-and-bound heuristic for the integrated long-haul and local vehicle routing problem on an adaptive transportation network
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.
1438-0064
urn:nbn:de:0297-zib-89700
publish
Junko Hosoda
Yuji Shinano
Stephen J. Maher
Yuji Shinano
Jonas Christoffer Villumsen
ZIB-Report
23-02
Computing Methodologies
GENERAL
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Shinano, Yuji
HPO-NAVI
Applied Algorithmic Intelligence Methods
https://opus4.kobv.de/opus4-zib/files/8970/ZIB-report-23-02.pdf
8520
eng
reportzib
1
--
2021-12-08
--
Massively parallel sharing lattice basis reduction
For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments.
1438-0064
urn:nbn:de:0297-zib-85209
under review
publish
under review
Nariaki Tateiwa
Yuji Shinano
Yuji Shinano
Masaya Yasuda
Shizuo Kaji
Keiichiro Yamamura
Katsuki Fujisawa
ZIB-Report
21-38
eng
uncontrolled
Discrete optimization
eng
uncontrolled
Lattice problem
eng
uncontrolled
Lattice-based cryptography
eng
uncontrolled
Shortest vector problem
eng
uncontrolled
Parallel algorithms
eng
uncontrolled
Ubiquity Generator Framework
Software
Mathematics of Computing
Computer Applications
GENERAL
GENERAL
ORDER, LATTICES, ORDERED ALGEBRAIC STRUCTURES [See also 18B35]
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Shinano, Yuji
HPO-NAVI
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
https://opus4.kobv.de/opus4-zib/files/8520/ZIB-Report-21-38.pdf
9307
eng
reportzib
1
--
2023-12-20
--
An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c
Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult.
1438-0064
urn:nbn:de:0297-zib-93072
publish
Koichi Fujii
Yuji Shinano
Sunyoung Kim
Masakazu Kojima
Hans D. Mittelmann
Yuji Shinano
ZIB-Report
23-27
Mathematics of Computing
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Shinano, Yuji
HPO-NAVI
Applied Algorithmic Intelligence Methods
MODAL-EnergyLab
https://opus4.kobv.de/opus4-zib/files/9307/ZIB-Report-23-27.pdf