Analysis on polytopal structure of mathematical programs

数学程序的多面结构分析

• 批准号: 20700006
• 负责人: MORIYAMA Sonoko
• 金额: $ 2.58万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20700006/
• 关键词: 離散構造; 数理計画問題; 多面体; 組合せ論; 幾何的実現

A mathematical program is to optimize a given objective function under some constraints. There have been various kinds of algorithms to solve mathematical programs rapidly. While the interior-point method solves them in polynomial time, pivoting algorithms are still promising for simplicity of the algorithms. In this research, we have studied properties of orientation of pivoting graphs by analyzing polytopal structure of mathematical programs, in order to propose more effective pivoting algorithms.

数学程序是在某些约束下优化给定的目标函数。已经有多种算法可以快速解决数学问题。虽然内点方法可以在多项式时间内解决它们，但旋转算法由于算法的简单性而仍然很有前途。在本研究中，我们通过分析数学程序的多面结构来研究旋转图的方向性质，以提出更有效的旋转算法。

项目成果

A family of polytopal digraphs that do not satisfy the shelling property

不满足脱壳性质的多面有向图族

• 发表时间: 2009
• 期刊: Proceedings of 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications 1
• 作者: David Avis;Hiroyuki Miyata;Sonoko Moriyama
• 通讯作者: Sonoko Moriyama

有向マトロイドの実現可能性問題における様々な展開

有向拟阵可行性问题的各种进展

• 发表时间: 2008
• 作者: Fukuoka S;Honda N;Ono K;Mimura T;Usui T;Amano S.;森山園子
• 通讯作者: 森山園子

A note on shellability and acyclic orientations

关于可剥壳性和非循环方向的注释

• 发表时间: 2008
• 期刊: Discrete Mathematics 308巻
• 作者: Masahiro Hachimori;Sonoko Moriyama
• 通讯作者: Sonoko Moriyama

A Note on the Upper Bound Derived by Semidefinite Programming for the Maximum Quantum Violation of Bell Inequalities

关于贝尔不等式最大量子破坏的半定规划推导上界的注解

• 发表时间: 2008
• 期刊: Proceedings of the 8th Asian Conference on Quantum Information Science, Poster Session A-9 Vol.1
• 作者: T. Toshiaki;S. Moriyama and H. Imai
• 通讯作者: S. Moriyama and H. Imai

ベル不等式の幾何構造

贝尔不等式的几何

• 发表时间: 2010
• 作者: Noma H;Funatsu H;Mimura T;Harino S;Sone T;Hori S.;森山園子
• 通讯作者: 森山園子