線形相補性問題の整数性に関する研究

线性互补问题的整数性质研究

• 批准号: 14J10346
• 负责人: 澄田 範奈
• 金额: $ 1.09万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2014
• 资助国家: 日本
• 起止时间: 2014-04-25 至 2016-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14J10346/
• 关键词: 線形相補性問題; 整数性; 双対性

数理計画法の分野では，制約，条件を満たす解を求める手法が研究されている．本研究では，数理計画法において基礎的かつ理論的にも実用上も重要な，線形相補性問題と呼ばれる問題を扱う．この問題は，行列とベクトルが与えられたとき，条件を満たすベクトルを求める問題である．線形相補性問題は，線形計画問題や凸二次計画問題，双行列ゲームといった基本的な問題を含み，経済学や力学といった周辺分野にも応用をもつ．本研究では，線形相補性問題の解ベクトルの中でも特に，整数ベクトルの解（整数解）が存在するための十分条件に着目した．応用によっては，整数解を得ることが必要な状況があるためである．線形相補性問題の整数解に関する先行研究では，入力行列が主単模と呼ばれる性質をもつならば，基底解が整数となることを示している．一方，線形相補性問題の特殊ケースである線形計画問題（線形制約を満たす中で線形関数を最大にするベクトルを求める問題）では，入力行列の完全単模性や，その拡張である線形制約の完全双対整数性が，整数最適解の存在を保証する性質として知られている．また，主単模行列は完全単模行列のひとつの拡張であり，先行研究で線形計画問題の結果の拡張に対応する結果が知られている．本研究の成果は，線形相補性問題の完全双対整数性を提案し，線形計画問題で知られている結果に対応する線形相補性問題の結果を得たことである．本研究のような研究がなされていなかったのは，線形相補性問題の「双対性」に関する研究が少なかったことがひとつの理由である．本研究では，新たに「方向つき線形相補性問題」を導入し，これを用いて線形相補性問題の双対性を提案した．本研究の成果は現在論文誌に投稿中であり，国内学会で発表を行った．

在数学编程领域，正在研究找到满足约束和条件的解决方案的方法。这项研究涉及一个称为线性互补性问题的问题，从根本上讲，这是理论上的，在数学编程中实际上很重要。这个问题是给出矩阵和向量的问题，找到满足条件的向量。线性互补性问题包括基本问题，例如线性编程问题，凸面二次编程问题和媒介游戏，并且还应用于外围场，例如经济学和机械。在这项研究中，我们专注于线性互补问题的解决方案向量之间存在整数矢量解（整数溶液）的足够条件。这是因为在某些应用中有必要获得整数解决方案。先前关于线性互补问题整数解决方案的研究表明，如果输入矩阵具有称为主要Uni-MAP的属性，则基求解将成为整数。另一方面，在线性编程问题中，这是线性互补性问题的一种特殊情况（找到最大化线性功能的矢量同时满足线性约束的问题），输入矩阵的完美单匹配和线性约束的完美双重直觉，这是扩展的范围，可以保证属性的属性。此外，主要的单一方法是完美单一方法的扩展，并且先前的研究已知结果对应于线性编程问题结果的扩展。这项研究的结果是，我们提出了线性互补问题的完美双整数，并获得了与线性编程问题中已知的结果相对应的线性互补问题的结果。这项研究中未进行此类研究的原因之一是，关于线性互补问题的“双重性”的研究很少。在这项研究中，我们引入了一个新的“定向线性互补问题”，并用它提出了线性互补问题的双重性。这项研究的结果目前已提交给该期刊，并在日本会议上介绍。

项目成果

線形相補性問題の完全双対整数性

线性互补问题的完全对偶性

• 发表时间: 2014
• 作者: Nakajima;R.;Yamamoto;H.;Kawagucci;S.;Takaya;Y.;Nozaki;T.;Chen;C.;Fujikura;K.;Miwa;T. and Takai;K.;高谷雄太郎，平出隆志，藤永公一郎，中村謙太郎，加藤泰浩;鈴木真弥;Maya Suzuki;澄田範奈，垣村尚徳，牧野和久;澄田範奈，垣村尚徳，牧野和久
• 通讯作者: 澄田範奈，垣村尚徳，牧野和久

方向つき線形相補性問題の計算複雑度

有向线性互补问题的计算复杂度

• 发表时间: 2014
• 作者: Nakajima;R.;Yamamoto;H.;Kawagucci;S.;Takaya;Y.;Nozaki;T.;Chen;C.;Fujikura;K.;Miwa;T. and Takai;K.;高谷雄太郎，平出隆志，藤永公一郎，中村謙太郎，加藤泰浩;鈴木真弥;Maya Suzuki;澄田範奈，垣村尚徳，牧野和久
• 通讯作者: 澄田範奈，垣村尚徳，牧野和久