大域的最適化問題の列挙解法の構築

全局优化问题的枚举解的构建

• 批准号: 09780404
• 负责人: 松井 知巳
• 金额: $ 1.41万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-09780404/
• 关键词: 組合せ最適化; 大域的最適化; 列挙算法; 列挙; グラフ

本研究では、下記の結果を得た。(1) スポーツのスケジューリングにおいて、公平な2重総当たりリーグ戦を作成する算法について研究を行った。通常の定式化では非常に大きな整数計画問題になるところを、問題の部分解を高速に列挙した後、その部分解の組合せ方を整数計画で定式化するという方法により、従来の結果より非常に高速に、良い解を得ることが出来た。この結果は現在発表予定である。(2) 過飽和実験計画法に対し、列挙法を用いてデザインの生成を行った。同時にデザインの良さ対する尺度の提案を行っている。この結果については論文を現在投稿中である。(3) 協力ゲームの一つである、重み付き多数決ゲームのシャプレー=シュービックインデックス、バンザフインデックス、ディーガン=パックルインデックスを求める列挙法の提案を行った。この結果は、すでに日本OR学会のRAMPシンポジウムで発表を行い、現在論文を投稿中である。

The results of this study are summarized below. (1)The research on the algorithm for the establishment of the multi-level network is carried out. Generally, the formulation of the problem is very large, and the partial solution of the problem is very high speed, and the combination of the partial solution is very high speed, and the result is very high speed. The result is now determined. (2)Oversaturation program method is used to generate data. At the same time, the proposal of the standard of good quality and good quality shall be carried out. The results of this paper are now submitted. (3)Cooperate with each other to determine the number of items in the list. The results of this paper are presented in the RAMP table of Japan OR Society.

项目成果

宮本裕一郎・松井知巳: "チャネル割当問題の解法" 数理モデル化と応用. 掲載予定.

Yuichiro Miyamoto和Tomomi Matsui：“信道分配问题的解决方案”数学建模和应用计划出版。

S.Iwata,T.Matsui,T.McConnic: "A Fast Bipartite Network Flow Algorithm for Selective Assembly" Operations Research Letters. 22. 137-143 (1998)

S.Iwata、T.Matsui、T.McConnic：“用于选择性组装的快速二分网络流算法”运筹学快报。

Tomomi Matsui: "A flexible algorithm for gererating all the spamming tiees in urdirected graphs" Algorithmica. 18・2. 530-544 (1997)

Tomomi Matsui：“一种在有向图中生成所有垃圾邮件联系的灵活算法”Algorithmica 18・2 (1997)。