学会ニュース

第 4 回 ｢近藤賞｣ 決定 !!（速報）
ご承知のように，近藤賞は OR 学会創立 50 周年記念事業の一つとして企画・創設され，約 2年に一度授賞しており，今回は第 4 回目となります．本年 7 月末まで公募し，その後，選考委員会審議・理事会承認を経て，藤重 悟氏（京都大学数理解析研究所特任教授）ヘの授賞が決定致しました．氏のこれまでの業績・選考理由等は機関誌 2013 年 2 月号にその詳細を掲載します．
また，受賞記念講演を 2013 年春季研究発表会（東京大学）で予定しておりますので，会員の皆様ご期待ください．
第 4 回近藤賞選考委員会

日本 OR 学会賞
平成 24 年度学会賞のうち，研究賞，研究賞奨励賞，論文賞，事例研究賞について，表彰委員会がそれぞれの候補を選考のうえ，理事会で以下のとおり決定されました．
各賞は平成 24 年 9 月 12 日の秋季研究発表会にて贈呈されました．

OR 学会

第 2 回研究賞● 塩浦昭義氏（東北大学）［選考理由］
塩浦昭義氏は離散凸解析全般において多大な研究業績を挙げてきた．同氏の最近 5年間の研究業績は，代表的なものだけでも次のものがある．
1.

“Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra,” SIAM Journal on Discrete Mathematics 26, 114–144 (2012).

2.

“M-convex Function Minimization by Continuous Relaxation Approach: Proximity Theorem and Algorithm,” SIAM Journal on Optimization 21, 633–668(2011).（共著者 S. Moriguchi, N. Tsuchimura）

3.

“Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints,” Proceedings of the 19th Annual European Symposium on Algorithms, 1–12 (ESA 2011)4.

“New Algorithms for Convex Cost Tension Problem with Application to Computer Vision,” Discrete Optimization 6, 378–393 (2009).（共著者 V. Kolmogorov）

5.

“Polynomial-time Algorithms for Linear and Convex Optimization on Jump Systems,” SIAM Journal on
Discrete Mathematics 21, 504–522 (2007).（共著者 K. Tanaka）
同氏の研究の概要を要約すると次のとおりである．

1.

離散凸解析における基本的な概念の一般化

2.

離散凸解析の各種問題に対するアルゴリズムの構築

3.

OR およびその他の分野への応用
離散凸解析については，基本的な概念である離散凸関数を，離散関数としての観点，実数関数としての観点の2012 年 11 月号（49）643

それぞれにおいて，大きく拡張して，より普遍な概念を提唱した．また，離散凸関数最小化アルゴリズムの開発を通じて，OR 周辺分野の既存研究との関連を明確にした．特に，資源配分問題のアルゴリズムへの貢献は著しい．さらに，これらの成果をスケジューリングやコンピュータビジョンに応用するなど，多様な分野への応用において成果をあげた．
以上の理由により，本年度の研究賞を塩浦昭義氏に贈ることに決定した．
［略歴］
1970 年 5 月 15 日生まれ（博士（理学））1998 年

東京工業大学大学院情報理工学研究科 数理 ･ 計算科学

博士（理学）取得

2001 年

東北大学大学院情報科学研究科システム情報科学専攻准教授［著者等］
学術論文 34 本，発表多数＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
塩浦昭義先生の OR 学会研究賞受賞に寄せて塩浦昭義先生のこの度の研究賞受賞の報に誠に喜ばしく，心よりお祝い申し上げます．
塩浦先生が 1997 年に上智大学機械工学科に着任された頃，私は学部学生で，それ以来お世話になっています．
私にとって先生であり，東工大・小島政和研究室の先輩であり，今回の受賞対象で先生が中心に研究されている離散凸解析の研究において『兄弟子』である，という存在です．このようなご縁で，僭越ながら，私の知る先生のお人柄を紹介したいと思います．
今回の受賞は，先生の日頃からの研究に対する「厳密さ」の賜物と推察いたします．「厳密」と言えば，先生は出張時の現地情報に対する事前情報収集や旅程のスケジューリングに関しても非常に厳密です．鉄道にも精通されており，ドイツ・ベルリンの S バーン（近郊電車）の広報誌にご子息と共に取り上げられた華麗な経歴もお持ちとか．…周りにいる人間にとって，いつもとても頼りになります！
2001 年から東北大学にお勤めの塩浦先生は，昨年の 3 月 11 日，東日本大震災の際，ご家族と共に仙台市におられました．ご存知のとおりの未曽有の大被害で，直後は通信手段もままならず，先生とご家族が心配でなりませんでした．翌日の 12 日にはご無事とのメールを受け，安心することができました．ご自宅近くの小学校での避難所生活の中，自宅でなんとか無事だったノートパソコンから状況を知らせて下さったメールには，ノートパソコンの頑丈さに感心されていることが触れられていました．そんなメールに，大変な状況におられるにもかかわらず，心配させまいとの気遣いを垣間見ることができました．また，不自由な生活が続いたでしょうに，研究活動への復旧の速さには，頭が下がりました．共著の論文の校正に，被害にあっていない私より迅速に対応して下さったりしたときは申し訳なかったです．今回の受賞は，身近な私たちは存じ上げていた，先生が早期に研究を復旧され，研究への情熱とご努力で研究の質，量ともすぐに回復されたという事実を示していると思います．
今後もさらなるご活躍を祈念しております．
森口聡子（産業技術大学院大学情報アーキテクチャ専攻）＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

OR 学会

第 2 回研究賞奨励賞● 岡本吉央氏（電気通信大学）［選考理由］
岡本吉央氏は，最適化理論の視点から多様な対象に取り組んだ研究を進めてきた．特に，厳密アルゴリズムの設計に関して理論的保証のある解法を多く提案している．同氏の最近 3 年間の代表的な研究成果は次のとおりである．
1.

“The Geodesic Diameter of Polygonal Domains,” Lecture Notes in Computer Science 6346, 500–511 (2010).
（共著者 S. W. Bae, M. Korman）

644（50）オペレーションズ・リサーチ

2.

“A Polynomial-time-delay Polynomial-space Algorithm for Enumeration Problems in Multi-criteria Optimization,” European Journal of Operational Research 210, 48–56 (2011).（共著者 T. Uno）

3.

“Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem,”
Journal of Graph Algorithms and Applications 15, 727–751 (2011).（共 著 者 Y. Otachi, R. Uehara, T.
Uno）
論文 1 は，単純多角形の内部に多角形の障害物が配置された多角形領域の直径を求める問題に対する多項式時間アルゴリズムの提案で，20 年間未解決であった問題に対する肯定的な解決である．
論文 2 は，縮退のない線形計画問題に対して端点パレート解を列挙するアルゴリズムで，多項式時間性と多項式領域性を共に満たすものを提案している．これは，多目的線形計画法に対する効率性保証のある初めてのアルゴリズムである．
論文 3 は，ネットワークの全域木混雑度に対する厳密アルゴリズムを提案している．これは NP 困難問題に対する厳密アルゴリズムであるが，理論保証を持つ指数関数的アルゴリズムに関する研究の先駆けとなる優れた研究である．
このように，同氏は最適化，ゲーム理論，計算量理論等の幅広い分野において優れた研究業績を挙げており，今後の成果が期待される．
以上の理由により，岡本吉央氏に研究賞奨励賞を贈ることに決定した．
● 小林佑輔氏（東京大学）［選考理由］
小林佑輔氏は，グラフ上の点素パス問題（整数多品種流問題と等価）と，それに関連する最適化問題に対する効率的なアルゴリズムを提案してきた．同氏の最近 3 年間の代表的な研究成果は次のとおりである．
1.

“On Shortest Disjoint Paths in Planar Graphs,” Discrete Optimization 7, 234–245. (2010).（共著者 C.
Sommer）

2.

“An Improved Algorithm for the Half-disjoint Paths Problem,” SIAM Journal on Discrete Mathematics
25, 1322–1330. (2011).（共著者 K. Kawarabayashi）

3.

“Breaking O(n1/2)-approximation Algorithms for the Edge-disjoint Paths Problem with Congestion Two,”
Proceedings of the 43rd ACM Symposium on Theory of Computing, 81–88. (2011).（共 著 者 K. Kawarabayashi）
論文 1 は，総長最小の点素パスを見出す問題の数学的な性質を考察し，効率的アルゴリズムと計算複雑度を示している．
論文 2 と論文 3 は，半整数性を要請した点素・辺素パス問題についての研究で，重要な成果を述べている．
同氏は海外研究者を含む多くの研究者と共同研究を行っており，この積極性とバイタリティは，今後の離散最適化分野を牽引していくことを期待させる．
以上の理由により，小林佑輔氏に研究賞奨励賞を贈ることに決定した．
● 北原知就氏（東京工業大学）［選考理由］
北原知就氏は，数理計画問題に対するアルゴリズムに関して優れた業績を挙げている．同氏の最近 3 年間の代表的な研究成果は次のとおりである．
1.

“A Bound for the Number of Different Basic Solutions Generated by the Simplex Method,” MathematicalProgramming（Online 版は 2011 年 8 月 3 日に公開），（共著者 S. Mizuno）

2. “Klee-Mintyʼs LP and Upper Bounds for Dantzigʼs Simplex Method,” Operations Research Letters 39, 88–91 (2011).（共著者 S. Mizuno）
3. “Proximity of Weighted and Layered Least Squares Solutions,” SIAM Journal Matrix Analysis and Ap2012 年 11 月号（51）645

plications 31, 1172–1186 (2009).（共著者 T. Tsuchiya）
論文 1 と論文 2 は，線形計画問題に対する基本的アルゴリズムである単体法の計算量に関するものである．これらの論文において，計算回数の上界を求めており，それがきわめてタイトなものであることを示している．この研究は独創的なものである，その成果はきわめて画期的で，インパクトを与えるものである．
一方，論文 3 は，線形計画問題のもう一つの有力なアルゴリズムである内点法に関するものである．
上記の論文以外にも，OR の応用に関する研究を進めており，例えば，機械学習に関しても論文を発表するな
ど，同氏の研究の範囲は広く，今後の一層の成果が期待される．
以上の理由により，北原知就氏に研究賞奨励賞を贈ることに決定した．
● 宮代隆平氏（東京農工大学）［選考理由］
宮代隆平氏は，スポーツスケジューリングの研究において優れた業績を挙げている．同氏の最近 3 年間の代表的な研究成果は次のとおりである．
1. “An Approximation Algorithm for the Traveling Tournament Problem,” Annals of Operations Research
194, 317–324 (2012).（共著者 T. Matsui, S. Imahori）
2.

“An Improved Approximation Algorithm for the Traveling Tournament Problem,” Algorithmica 61, 1077–1091 (2011).（共著者 D. Yamaguchi, S. Imahori, T. Matsui）

3.

“An Approximation Algorithm for the Unconstrained Traveling Tournament Problem,” Proceedings of the8th International Conference on the Practice and Theory of Automated Timetabling, 508–512 (2010).（共著者 S. Imahori, T. Matsui).
これらの研究は巡回トーナメント問題に対する近似解法（近似度と呼ばれる数値によって，最適解までの近さが保証された解法）に関するものである．
論文 1 は，世界初の近似解法を提案している．論文 2 は，ホームアウェイの連続に関する論文 1 の制限を緩和した一般的な問題に対する近似解法を提案し，かつ，近似率も改善している．巡回トーナメント問題に対する従来の研究の流れは，厳密解法と発見的解法の 2 つに分離していたが，これら 2 本の論文によって近似解法という新たな流れが出現した．
論文 3 は，ホームアウェイの連続に関する論文 1 の制限を完全に撤廃した問題に対する近似解法を提案している．
同氏の研究は，既存の研究の改良ではなく，新しい方向性を提案し，かつ優れた成果を出すというもので，若手研究者の模範と言える．
以上の理由により，宮代隆平氏に研究賞奨励賞を贈ることに決定した．

OR 学会

第 2 回論文賞● 田中健一氏（電気通信大学）［授賞論文］ “Maximum Flow-covering Location and Service Start Time Problem and Its Application to Tokyo Metropolitan Railway Network, ” Journal of the Operations Research Society of Japan 54,
237–258 (2011).
［選考理由］
本論文は，施設におけるサービス提供を時空間領域で決定する，最大カバー型の最適配置問題を提案し，首都圏鉄道網上の配置分析を行っている．ここで，サービス利用可能者とは，就業後に施設に立ち寄り一定時間サービスを受け，所定の時刻までに帰宅可能な就業者と定義する．本論文では，実際にサービスを受けるサービス利用可能者の数を最大化する各施設の位置とサービス開始時刻を決定する問題を論じている．サービス開始時刻が，各施設で独立に設定可能な場合（独立開始モデル）と，すべての施設で共通の場合（同時開始モデル）の 2 種類646（52）オペレーションズ・リサーチ

のモデルを扱っている．これら 2 つのモデルを整数計画問題として定式化し，発見的解法を提案している．その上で，大都市交通センサスデータをもとに作成したフローデータを用い，首都圏鉄道網上に，一施設を各駅・各開始時刻に配置する状況と，提案解法による複数施設の配置結果を分析している．独立開始モデルでは，異なる時刻にサービスを開始する複数の施設が都心部に配置され，同時開始モデルでは，都心と郊外の大規模駅に分散して配置されるという結果が得られた．
論文の書き方は平易かつ明快である．また，実データを用いた検証に大きなスペースを割り当てるなど，ORの論文として模範的である．
以上の理由により，本年度の論文賞を田中健一氏に贈ることに決定した．

OR 学会

第 32 回事例研究賞● 田中健一氏（電気通信大学）
古田壮宏氏（東京理科大学）［対象研究］「複数回の捕捉を考慮したフロー捕捉型配置問題と鉄道流動データへの適用―京王線と山手線を事例として―」オペレーションズ・リサーチ Vol. 56, No. 3, 166–174［選考理由］
鉄道における乗客の流れに着目し，路線上の駅に施設（コンビニエンスストア，ATM, 広告，等々）を配置するフロー捕捉型配置問題に関する事例研究である．本研究で用いているフロー捕捉型配置問題は，本来のモデルと，複数の施設から同時に捕捉される状況を考慮したモデルの 2 種類である．取り上げた鉄道は，乗客の流動パターンが著しく異なる京王線と山手線で，この違いが最適配置結果に与える影響を分析している．
実際の駅間移動データを用いて，上記 2 種類のモデルに対する最適配置を求めている．特に，山手線に対する複数回捕捉モデルによる最適配置結果は，実際の大型家電量販店の店舗の位置ときわめてよく一致しているなど，興味深い結果が得られた．
本研究は，モデルの設定，研究方法，用いたデータなど，多くの点において OR の事例研究として優れたものである．
以上の理由により，田中健一氏と古田壮宏氏に事例研究賞を贈ることに決定した．
● 勝又壮太郎氏（長崎大学）
阿部誠氏（東京大学）［対象研究］「学習による内部化のモデル―選択肢の絞り込み過程をどう組み込むか―」データ解析コンペティション
2011 年 7 月［選考理由］
本研究は，多数のブランドが存在して繰返し購買が観測される消費財市場における消費者のブランド選択行動を解明することを目的とした研究である．
一般に，消費者は，市場において，すべてのブランドを評価し合理的な意思決定によってブランドを選択しているわけではない．しかし，消費者のブランド選択のモデルを POS データなどの行動データから構築することは容易ではない．本研究では，行動データのみを用いて，代替案の絞り込み過程を組み込んだブランド選択モデルを構築している．
このモデルの構築には OR のさまざまな手法が用いられている．このモデルにより，行動データ分析の理論的枠組みができた．さらに，このモデルは予測能力が高く，拡張可能性が高いなど，優れたものである．
以上の理由により，勝又壮太郎氏と阿部誠氏に事例研究賞を贈ることに決定した．

2012 年 11 月号（53）647

〔平成 24 年度表彰委員〕
中森眞理雄（委員長・東京農工大学），河合一（鳥取大学），栗田治（慶應義塾大学），関谷和之（静岡大学），滝根哲哉（大阪大学），半田恵一（（株）東芝），松井知己（中央大学），村松正和（電気通信大学），山下英明（首都大学東京），吉瀬章子（筑波大学）

648（54）

オペレーションズ・リサーチ