Research on Integrated Techniques of Enumeration and Optimization Based on Discrete Structure Manipulation Systems

基于离散结构操纵系统的枚举与优化集成技术研究

• 批准号: 20H00605
• 负责人: 湊 真一
• 金额: $ 28.12万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (A)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20H00605/
• 关键词: アルゴリズム; 離散構造; 演算処理系; 列挙; 索引化

本年度の研究実績の概要は以下の通りである。(i) 列挙と最適化の統合的アルゴリズム技法の研究と体系化：グラフの最短路問題のように、組合せ問題のアイテムにコストが定義されているときに、コスト総和が所与の閾値以下となるような実行可能解を列挙することは、多くの実用的な応用を持つ汎用的で重要な問題である。このような一般的なコスト制約つき組合せ問題に対して、ZDDを用いて大量の解を高速に全列挙する「区間メモ化技法」を前年度に考案したが、これを実装し実験により有効性を確認した。本研究結果は研究代表者自らが筆頭著者として国内研究会および国際ワークショップで発表した。(ii) 離散構造処理系の基盤アルゴリズムの実装とソフトウェアの整備：BDD/ZDDをベースとする離散構造処理系のアルゴリズムは、原則として「BDDパッケージ」と呼ばれるソフトウェアライブラリとして公開されている。前年度からに開発している高速列挙アルゴリズムの実装もこのパッケージに追加されており、改良を進めている。(iii) 関連分野との連携および応用分野への発展：本研究が呼び水となり、学術変革(A)「アルゴリズム基盤」および学術変革(B)「組合せ遷移」が昨年度後半に相次いで採択され、理論計算機科学を中心とする研究者コミュニティの発展が期待される。学術変革(A)(B)および各分野の第一線で活躍する研究者と研究協力者として定期的に会合し連携を深めた。

An overview of this year's research achievements is as follows. (i) The research and systematization of the アルゴリズム technique that integrates optimization and optimization: グラフの极Short circuit problem, combination problem, definition of short circuit problem, combination problemときに, コスト総, and が are related to となるような実行 below the threshold value.することは、多くの実用な応用をhold つ大でimportantである.このようなGeneral なコストrestrictionつきcombinationせquestionに対して、ZDDを useいてa large number of solutionsをhigh-speedにfull series The effectiveness of the "Interval Modification Technique" of the previous year's examination has been confirmed, and the effectiveness of the "Interval Modification Technique" has been confirmed. The research results of this study are represented by the author of this study, Domestic Research Association and International Research Institute. (ii) Discrete Structure Processing System's Basic System: BDD/ZDD Discrete Structure Processing Systemのアルゴリズムは、principle として「BDDパッケージ」とCalling the public されている. The previous year's high-speed train was opened and installed.もこのパッケージにAdded されており, improved を进めている. (iii) Relevant field of study and cooperation with the field of study and research: This research study of water and academic reform (A) "Analysis base" academic reform ( B) 「Migration of combination」がにphase in the second half of last year, and the researcher of the Theoretical Computer Science Center, and the researcher, I am looking forward to the exhibition. Academic reform (A) (B) consists of active researchers and research collaborators on the front line of each field, and regular meetings and collaborations.

项目成果

解集合プログラミングを用いたハミルトン閉路遷移問題の解法

使用解集规划求解哈密顿循环转移问题

• 发表时间: 2023
• 作者: 平手貴大;番原睦則;井上克巳;盧暁南;鍋島英知;宋剛秀;田村直之
• 通讯作者: 田村直之

チャネリング制約を用いたalldifferent 制約の SAT 符号化

使用通道约束对所有不同约束进行 SAT 编码

• 发表时间: 2022
• 作者: 小菅脩司;宋剛秀;田村直之;番原睦則
• 通讯作者: 番原睦則

解集合プログラミングに基づく組合せ遷移ソルバーの実装方式に関する考察

基于解集规划的组合转移求解器实现方法的思考

• 发表时间: 2021
• 作者: 山田悠也;湊真一;番原睦則
• 通讯作者: 番原睦則

Algorithmic Enumeration of Surrounding Polygons

周围多边形的算法枚举

• 发表时间: 2018
• 作者: K. Yamanaka;T. Horiyama;Y. Okamoto;R. Uehara;T. Yamauchi
• 通讯作者: T. Yamauchi

Hypergraph characterization of split matroids

分裂拟阵的超图表征

• DOI: 10.1016/j.jcta.2022.105697
• 发表时间: 2023
• 期刊: Journal of Combinatorial Theory, Series A
• 作者: Kristof Berczi;Tamas Kiraly;Tamas Schwarcz;Yutaro Yamaguchi;Yu Yokoi
• 通讯作者: Yu Yokoi