付値マトロイド理論の離散最適化問題への応用

定价拟阵理论在离散优化问题中的应用

基本信息

批准号：
11740074
负责人：
塩浦昭義
金额：
$ 1.02万
依托单位：
Sophia University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-11740074/
关键词：
凸集合凸関数凸性マトロイド付値離散最適化組合せ最適化

项目摘要

本年度は,前年度の研究結果に基づき,離散最適化問題に対するアルゴリズムの枠組みを提案するとともに,これまでの研究結果を論文誌や学会にて発表した.1.平成11年度の計画のうち,予定通りに終了しなかった部分については継続して研究を進めた.2.前年度の結果を踏まえて,付値マトロイドの理論に基づいた,離散最適化問題に対する解法の枠組みを提示した.さらに,その手法を現実の大規模な問題に適用するために必要なアルゴリズムを開発した.特に,スケーリングという技法を用いた効率的な算法を提案した.3.上記で得られたアルゴリズムをプログラム化し,その特徴を得るために実験により解析を行った.さらに,その結果を元にして,理論的な解析へ繋げようと試みている.4.以上の成果を専門分野の研究者に紹介し,討論を通じてその意義を明かにし,学術論文として学術論文誌に投稿した.いくつかの結果についてはDiscrete Applied Mathematics,Advances in Applied Mathematicsなどの論文誌に掲載されており,その他の論文については現在審査中である.また,2000年8月の国際数理計画シンポジウム,2000年11月の京都大学数理解析研究所の研究集会など,国内外の学会にて研究結果を発表するとともに,他の研究者と有意義な討論を行った.2001年2月には研究のまとめを行うために,カナダ・ブリティッシュコロンビア大学のMcCormick教授を訪問し,数多くの議論を行った.

今年，我们在前一年研究成果的基础上，提出了离散优化问题的算法框架，并在期刊和学术会议上展示了迄今为止的研究成果。 1． 2. 基于前一年的成果，我们提出了一个基于估值矩阵理论的解决离散优化问题的框架，该框架适用于大规模问题。特别是，我们提出了一种使用称为缩放的技术的有效算法。3.我们对上面获得的算法进行了编程，并通过实验对其进行了分析，以获得其特征。此外，根据结果，我们试图将它们与理论分析联系起来4。我们将把上述成果介绍给专业领域的研究人员，通过讨论阐明其意义，并将部分成果作为学术论文提交到学术期刊上。应用数学、应用进展已在Mathematics等期刊发表，其他论文正在审稿中。此外，2000年8月国际数学规划研讨会、2000年11月京都大学数学分析研究所研究会等。国内外国际的除了在学术会议上展示我们的研究成果外，我们还与其他研究人员进行了有意义的讨论。2001年2月，我们拜访了加拿大不列颠哥伦比亚大学的McCormick教授，对我们的研究进行了总结。