Analysis on history-based pivot rules of linear programming

线性规划历史枢轴规则分析

• 批准号: 23700004
• 负责人: MORIYAMA Sonoko
• 金额: $ 2.58万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23700004/
• 关键词: 線形計画問題; 単体法; 多面体理論; LPグラフ; 有向マトロイド; マトロイド; 組合せ論

The simplex method is one of various approaches to solve a linear program. The simplex method was developed by Dantzig in 1947. It is well known whether there exist pivoting algorithms to solve a linear program in polynomial time. This problem has been considered for years. In this research, we focused on history-based pivoting rules developed by Zadeh to attack the open problem.(1) Construction of a method to enumerate LP digraphs, which describes a behavior of pivoting algorithms; (2) Analysis of history-based pivoting rules on the LP digraphs; (3) Verification of some conjectures on the number of applying pivoting rules

单纯形法是求解线性规划的多种方法之一。单纯形法由 Dantzig 于 1947 年开发。众所周知是否存在枢轴算法来求解多项式时间内的线性规划。这个问题已经被考虑了很多年。在本研究中，我们重点关注Zadeh开发的基于历史的旋转规则来解决开放问题。（1）构造一种枚举LP有向图的方法，它描述了旋转算法的行为； (2) LP有向图上基于历史的枢转规则分析； （3）关于适用枢轴规则的数量的一些猜想的验证

项目成果

Orientable excluded minors of rank 3 for realizable matroids

可定向排除可实现拟阵的 3 级未成年人

• 发表时间: 2013
• 期刊: the 16th Japan Conference on Discrete and Computational Geometry and Graphs
• 作者: Ninoniya Y;Yasumatsu K;Yoshida R;Hidefumi Hiraishi and Sonoko Moriyama
• 通讯作者: Hidefumi Hiraishi and Sonoko Moriyama

On the Existence of Hamiltonian Paths for History Based Pivot Rules on Acyclic Unique Sink Orientations of Hypercubes

超立方体非循环唯一汇方向上基于历史枢轴规则的哈密顿路径的存在性

• 发表时间: 2012
• 期刊: Discrete Applied Mathematics, accepted for publication
• 作者: Y. Aoshima;D. Avis;T. Deering;Y. Matsumoto and S. Moriyama
• 通讯作者: Y. Matsumoto and S. Moriyama

線形計画向きづけをシェリング性で特徴付けられる多面体クラスについて

关于一类线性规划方向以谢林性质为特征的多面体

• 作者: Akira Suzuki;Kei Uchizawa and Xiao Zhou;青島良一，宮田洋行，森山園子
• 通讯作者: 青島良一，宮田洋行，森山園子

Complete enumeration of small realizable oriented matroids

小型可实现定向拟阵的完整枚举

• 发表时间: 2010
• 期刊: Proceedings of the 22nd Canadian Conference on Computational Geometry
• 作者: Hiroyuki Miyata;Sonoko Moriyama;Komei Fukuda
• 通讯作者: Komei Fukuda

Families of polytopal digraphs that do not satisfy the shelling property

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

• DOI: 10.1016/j.comgeo.2012.10.005
• 发表时间: 2013
• 期刊: Comput. Geom.
• 作者: David Avis;Hiroyuki Miyata;Sonoko Moriyama
• 通讯作者: Sonoko Moriyama