<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>8130</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-01-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Challenging Large Scale QAPs</title>
    <abstract language="eng">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.&#13;
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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-81303</identifier>
    <identifier type="doi">10.12752/8130</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Koichi Fujii</author>
    <submitter>Yuji Shinano</submitter>
    <author>Naoki Ito</author>
    <author>Sunyoung Kim</author>
    <author>Masakazu Kojima</author>
    <author>Yuji Shinano</author>
    <author>Kim-Chuan Toh</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-02</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>QAP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Parallel Branch-and-Bound</value>
    </subject>
    <collection role="ccs" number="I.">Computing Methodologies</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="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="HPO-NAVI">HPO-NAVI</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8130/ZIB-Report-21-02.pdf</file>
  </doc>
  <doc>
    <id>8677</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>jpn</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2022-05-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="jpn">大規模二次割当問題への挑戦</title>
    <abstract language="jpn">二次割当問題は線形緩和が弱いことが知られ，強化のため多様な緩和手法が考案されているが，その一つである二重非負値計画緩和（ DNN 緩和）及びその解法として近年研究が進んでいるニュートン・ブラケット法を紹介し，それらに基づく分枝限定法の実装及び数値実験結果について報告する．</abstract>
    <parentTitle language="jpn">統計数理研究所共同研究リポート 453&#13;
最適化：モデリングとアルゴリズム３３　２０２２年３月&#13;
「大規模二次割当問題への挑戦」 p.84-p.92</parentTitle>
    <additionalTitle language="eng">Solving Large Scale QAPs with DNN-based Branch-and-bound : a progress report</additionalTitle>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-86779</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Koichi Fujii</author>
    <submitter>Yuji Shinano</submitter>
    <author>Naoki Ito</author>
    <author>Sunyoung Kim</author>
    <author>Masakazu Kojima</author>
    <author>Yuji Shinano</author>
    <author>Kim-Chuan Toh</author>
    <series>
      <title>ZIB-Report</title>
      <number>22-11</number>
    </series>
    <collection role="ccs" number="G.">Mathematics of Computing</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="HPO-NAVI">HPO-NAVI</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisPublisher>Zuse Institute Berlin (ZIB)</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-zib/files/8677/ZIB-Report_22-11.pdf</file>
  </doc>
</export-example>
