数理計画問題に内在する大域的性質に基づく多項式時間アルゴリズムの構築

基于数学规划问题固有的全局属性构建多项式时间算法

基本信息

批准号：
18K11173
负责人：
森山園子
金额：
$ 2.75万
依托单位：
Nihon University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2018
资助国家：
日本
起止时间：
2018-04-01 至 2024-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K11173/
关键词：
数理計画多面体マトロイド数理計画問題

项目摘要

数理計画問題の解法として単体法[Dantzig(1947)]を起源とするピボットアルゴリズムがある。多項式時間を達成するピボットアルゴリズムの存在解明は数理計画問題における重要な未解決事項である。線形計画問題の一部を多項式回数の反復で解くアルゴリズムの達成[Gaertner(2002)]を機に，研究代表者はこの成功の核となった数理計画問題に内在する大域的性質に着目し，従来のピボットアルゴリズムが注視する数理計画問題の局所構造からは得られない大域的性質の重要性を明らかにしてきた。本研究では「(A)数理計画問題の大域的性質に基づく多項式時間ピボットアルゴリズムの構築」を目指して進めてきたが，そのアプローチの1つと想定していた「(B)離散勾配流によるピボットアルゴリズムの高速化の実現」について当初の想定より難しいことが判明した。また，22年度は私事により研究代表者の研究時間の確保が難しかったことから，最終年度の23年度（延長）に向けて研究計画の見直しをする必要が生じた。そこで，(A)を達成するうえで数理計画問題の多面体的構造の把握が重要であることと，もう1つの目標として「(C)マトロイドとその表現可能性からみた多面体の離散構造」があることから，23年度に向けて多面体の離散構造の把握に集中することにした。22年度は，20年度後半より開始した多面体とその計算に関する本の執筆を終え，現在校正段階である。本著を執筆する過程で多面体に関する書籍が少ないことを改めて認識し，本著より更に平易な内容を含む多面体の離散構造に関する別の書籍の執筆を開始した。

有一种主元算法源自单纯形法 [Datzig (1947)]，作为解决数学规划问题的方法。实现多项式时间的主元算法的存在是数学规划问题中一个重要的未解决问题。利用使用多项式迭代解决部分线性规划问题的算法 [Gaertner (2002)] 的成果，首席研究员专注于数学规划问题固有的全局属性，这是这一成功的核心我们阐明了传统枢轴算法关注的数学规划问题的局部结构无法获得的全局属性的重要性。在这项研究中，我们的目标是“(A) 基于数学规划问题的全局属性构建多项式时间主元算法”，我们假设的方法之一是“(B) 基于离散的主元算法”梯度流。”事实证明，实现更快的速度比最初预期的更加困难。此外，2012年，由于主要研究者个人原因，难以确保研究时间，因此有必要重新审视2023年最后一年（延期）的研究计划。因此，为了实现（A），理解数学规划问题的多面体结构很重要，另一个目标是“（C）拟阵视角下的多面体的离散结构及其可表达性”。，我们决定2023年重点了解多面体的离散结构。 2012年，我写完了一本关于多面体及其计算的书，2020年下半年开始写，目前正在校对阶段。在写这本书的过程中，我再次意识到关于多面体的书很少，所以我开始写另一本关于多面体离散结构的书，内容比这本书更简单。