| 講演名 | 2023-07-06 集合対間配線問題に対する高速整数線形計画法 髙島 康裕(北九州市大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では，集合対間配線問題に対する整数線形計画法の高速化を提案する．従来研究においては，最適解を得る保証の無い高速な発見的手法か，最適性を保証する反面実用的な計算時間では収束しない厳密解法のいずれかしか存在しなかった．本稿では，最適性を保証した厳密解法でありながら，実用的な時間で収束する高速線形計画法による解法を提案する．そして，実用的な時間で，最適解か，もしくはこれまでの知られた中での最良解が求解可能であることを実験により確認し，提案手法の有効性を確認した． |
| 抄録(英) | This paper proposes a fast method of integer linear programming for Set-pair routing problem. The previous works are fast heuristics which may not output the optimum solution or exact methods which may not finish within practical processing time. In this paper, we propose a fast integer programming method whose processing time is practical enough. We confirm the efficiency of the proposed method empirically, where it outputs the optimum solutions or the best solutions which has been obtained. |
| キーワード(和) | 集合対間配線問題 / 高速整数線形計画法 / 到達可能点集合 |
| キーワード(英) | Set-pair routing problem / fast integer linear programming / reachable vertex set |
| 資料番号 | CAS2023-6,VLD2023-6,SIP2023-22,MSS2023-6 |
| 発行日 | 2023-06-29 (CAS, VLD, SIP, MSS) |
| 研究会情報 | |
| 研究会 | MSS / CAS / SIP / VLD |
|---|---|
| 開催期間 | 2023/7/6(から2日開催) |
| 開催地（和） | 小樽商科大学 3号館 102教室 |
| 開催地（英） | |
| テーマ（和） | システムと信号処理および一般 |
| テーマ（英） | |
| 委員長氏名（和） | 山口 真悟(山口大) / 相原 康敏(オムニビジョン) / 仲地 孝之(琉球大) / 中武 繁寿(北九州市大) |
| 委員長氏名（英） | Shingo Yamaguchi(Yamaguchi Univ.) / Yasutoshi Aibara(OmniVision) / Takayuki Nakachi(Ryukyu Univ.) / Shigetoshi Nakatake(Univ. of Kitakyushu) |
| 副委員長氏名（和） | 宮本 俊幸(阪工大) / 篠宮 紀彦(創価大) / 市毛 弘一(横浜国大) / 西川 清史(都立大) / 桜井 祐市(日立) |
| 副委員長氏名（英） | Toshiyuki Miyamoto(Osaka Inst. of Tech.) / Norihiko Shinomiya(Soka Univ.) / Koichi Ichige(Yokohama National Univ.) / Kiyoshi Nishikawa(okyo Metropolitan Univ.) / Yuichi Sakurai(Hitachi) |
| 幹事氏名（和） | 林 直樹(阪大) / 劉 健全(NEC) / 笠松 大佑(創価大) / 鈴木 寛人(ルネサスエレクトロニクス) / 今泉 祥子(千葉大) / 京地 清介(工学院大) / 笹川 幸宏(ソシオネクスト) / 今井 雅(弘前大) |
| 幹事氏名（英） | Naoki Hayashi(Osaka Univ.) / Jianquan Liui(NEC) / Daisuke Kasamatsu(Soka Univ.) / Hiroto Suzuki(Renesas Electronics) / Shoko Imaizumi(Chiba Univ.) / Seisuke Kyochi(Kogakuin Univ.) / Yukihiro Sasagawa(Socionext) / Masashi Imai(Hirosaki Univ.) |
| 幹事補佐氏名（和） | 白井 匡人(島根大) / 伊藤 尚(富山高専) / 山口 基(テクノプロ) / 下田 真二(ソニーセミコンダクタソリューションズ) / 越田 俊介(八戸工大) / 吉田 太一(電通大) / 塩田 さやか(都立大) / 西元 琢真(日立) |
| 幹事補佐氏名（英） | Masato Shirai(Shimane Univ.) / Nao Ito(NIT, Toyama college) / Motoi Yamaguchi(TECHNOPRO) / Shinji Shimoda(Sony Semiconductor Solutions) / Shunsuke Koshita(Hachinohe Inst. of Tech.) / Taichi Yoshida(UEC) / Sayaka Shiota(Tokyo Metropolitan Univ.) / Takuma Nishimoto(Hitachi) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Mathematical Systems Science and its Applications / Technical Committee on Circuits and Systems / Technical Committee on Signal Processing / Technical Committee on VLSI Design Technologies |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 集合対間配線問題に対する高速整数線形計画法 |
| サブタイトル（和） | |
| タイトル（英） | Fast Method of Integer Linear Programming for Set-Pair Routing Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 集合対間配線問題 / Set-pair routing problem |
| キーワード(2)（和/英） | 高速整数線形計画法 / fast integer linear programming |
| キーワード(3)（和/英） | 到達可能点集合 / reachable vertex set |
| 第 1 著者 氏名（和/英） | 髙島 康裕 / Yasuhiro Takashima |
| 第 1 著者 所属（和/英） | 北九州市立大学(略称：北九州市大) University of Kitakyushu(略称：Univ. of Kitakyushu) |
| 発表年月日 | 2023-07-06 |
| 資料番号 | CAS2023-6,VLD2023-6,SIP2023-22,MSS2023-6 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | CAS-97,VLD-98,SIP-99,MSS-100 |
| ページ範囲 | pp.28-33(CAS), pp.28-33(VLD), pp.28-33(SIP), pp.28-33(MSS), |
| ページ数 | 6 |
| 発行日 | 2023-06-29 (CAS, VLD, SIP, MSS) |