北原 知就（きたはら ともなり） データ更新日：2019.09.10

キーワード：線形計画問題、アルゴリズム、単体法、
2018.04.

 1 Tomonari Kitahara and Noriyoshi Sukegawa, A simple projection algorithm for linear programming problems, Algorithmica, 10.1007/s00453-018-0436-3, 2018.03, Fujishige et al. propose the LP-Newton method, a new algorithm for linear programming problem (LP). They address LPs which have a lower and an upper bound for each variable, and reformulate the problem by introducing a related zonotope. The LP-Newton method repeats projections onto the zonotope by Wolfe’s algorithm. For the LP-Newton method, Fujishige et al. show that the algorithm terminates in a finite number of iterations. Furthermore, they show that if all the inputs are rational numbers, then the number of projections is bounded by a polynomial in L, where L is the input length of the problem. In this paper, we propose a modification to their algorithm using a binary search. In addition to its finiteness, if all the inputs are rational numbers and the optimal value is an integer, then the number of projections is bounded by L+1, that is, a linear bound.. 2 Tomonari Kitahara, Shinji Mizuno, and Jianming Shi, The LP-Newton method for standard form linear programming problems, Operations Research Letters, 41, 426-429, 2013.09. 3 Tomonari Kitahara and Takashi Tsuchiya, A simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm and its objective-function-free complexity, SIAM Journal on Optimization, 23, 1890-1903, 2013.09. 4 Tomonari Kitahara and Shinji Mizuno, A bound for the number of basic solutions generated by the simplex method, Mathematical Programming, 137, 579-586, 2013.02. 5 Tomonari Kitahara and Shinji Mizuno, On the number of solutions generated by the dual simplex method, Operations Research Letters, 40, 172-174, 2012.05.

2017.04～2020.03, 日本オペレーションズ・リサーチ学会　数理計画研究部会(RAMP), 幹事.

2016.08.06～2016.08.11, The Fifth International Conference on Continuous Optimization (ICCOPT Tokyo 2016), 実行委員.

2019年度～2022年度, 基盤研究(C), 代表, 線形計画問題に対する離散・連続融合アルゴリズムの開発.
2015年度～2017年度, 若手研究(B), 代表, 単体法は多項式アルゴリズムであるか ―未解決問題解決への布石―.
2011年度～2012年度, 若手研究(B), 代表, 日本の公的年金運用のための最適化手法の開発.
2015年度～2017年度, 基盤研究(B), 分担, 凸錐上の線形計画法の深化と数理モデリングの新展開.
2014年度～2018年度, 基盤研究(A), 分担, 新時代の最適化モデルに基づく意思決定支援プラットフォームの研究と開発.
2012年度～2014年度, 基盤研究(B), 分担, 凸最適化によるモデリングと計算推論の新展開.
2009年度～2012年度, 基盤研究(A), 分担, 情報化ネットワーク社会に向けた高度な専門的数理技術ライブラリの研究と開発.

### 九大関連コンテンツ

pure2017年10月2日から、「九州大学研究者情報」を補完するデータベースとして、Elsevier社の「Pure」による研究業績の公開を開始しました。