<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>8520</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-12-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Massively parallel sharing lattice basis reduction</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-85209</identifier>
    <note>under review</note>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <author>Nariaki Tateiwa</author>
    <submitter>Yuji Shinano</submitter>
    <author>Yuji Shinano</author>
    <author>Masaya Yasuda</author>
    <author>Shizuo Kaji</author>
    <author>Keiichiro Yamamura</author>
    <author>Katsuki Fujisawa</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Discrete optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lattice problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lattice-based cryptography</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Shortest vector problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Parallel algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Ubiquity Generator Framework</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="pacs" number="00.00.00">GENERAL</collection>
    <collection role="msc" number="00-XX">GENERAL</collection>
    <collection role="msc" number="06-XX">ORDER, LATTICES, ORDERED ALGEBRAIC STRUCTURES [See also 18B35]</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="HPO-NAVI">HPO-NAVI</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8520/ZIB-Report-21-38.pdf</file>
  </doc>
  <doc>
    <id>10190</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2025-10-26</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Smoothie: Mixing the strongest MIP solvers to solve hard MIP instances on supercomputers - Phase I development</title>
    <abstract language="eng">Mixed-Integer Linear Programming (MIP) is applicable to such a wide range of real-world decision problems that the competition for the best code to solve such problems has lead to tremendous progress over the last decades. While current solvers can solve some of the problems that seemed completely out-of-reach just 10 years ago, there are always relevant MIP problems that currently cannot be solved. With the Smoothie solver we intend to solve extremely hard MIP problems by building on the many years that went into the development of several state-of-the-art MIP solvers and by utilizing some of the largest computing resources available. The high-level task parallelization framework UG (Ubiquity Generator) is used and extended by Smoothie to build a solver that uses large-scale parallelization to distribute the solution of a single MIP on a shared- or distributed-memory computing infrastructure, thereby employing several established MIP solvers simultaneously. For the first development phase, which is the topic of this report, both FICO Xpress and Gurobi are used in concurrent mode on a single machine, while information on incumbent solutions and explored branch-and-bound subtrees is exchanged. A dynamic restarting mechanism ensures that solver configurations are selected that promise most suitable for the MIP to be solved. We report on initial findings using this early version of Smoothie on unsolved problems from MIPLIB 2017.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-101906</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Yuji Shinano</author>
    <submitter>Yuji Shinano</submitter>
    <author>Stefan Vigerske</author>
    <series>
      <title>ZIB-Report</title>
      <number>25-18</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIPLIB, MIP, UG, Parallelization</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="pacs" number="00.00.00">GENERAL</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/10190/Smoothie-ZIB-Report.pdf</file>
  </doc>
  <doc>
    <id>7839</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2020-05-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Previously Unsolved MIP Instances with ParaSCIP on Supercomputers by using up to 80,000 Cores</title>
    <abstract language="deu">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-78393</identifier>
    <author>Yuji Shinano</author>
    <submitter>Yuji Shinano</submitter>
    <author>Tobias Achterberg</author>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-16</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP,  Ubiquity Generator Framework, MIPLIB</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="persons" number="michael.winkler">Winkler, Michael</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7839/ZIB-Report_20-16.pdf</file>
  </doc>
</export-example>
