ＩＳＳＮ1880−2818
数理解析研究所講究録 1629
21 世紀の数理計画：
最適化モデルとアルゴリズム
京都大学数理解析研究所
2009 年 2 月
RIMS K6kyOroku I629
Mathematical Programming in the 2Zst Centu7rv.”
0ptimization Modeling and Aigorithms
27ebruary, 2009
Research Institute for Mathematical Sciences
1¡yoto Unzversity, K)2oto, lapan
This is a report of research done at the Research Institute fbr Mathematical
Sciences, Kyoto University The papers contamed herein are in final fbrm
and will not be submitted for publication elsewhere
21世紀の数理計画 最適化モデルとアルゴリズム
Ｍａｔｈｅｍａｔｌｃａｌ Ｐｒｏｇｒａｍｍｌｎｇ ｌｎ ｔｈｅ21ｓｔ Ｃｅｎｔｕｒｙ Ｏｐｔ1血ｚａｔｌｏｌｎ Ｍｏｄｅｌｌｎｇ ａｎｄ Ａｌｇｏｒｌｔｈｍｓ ＲＩＭＳ研究集会報告集
2008年7月23日〜7月25日
研究代表者 久野 誉人（Ｔａｋａｈｌｔｏ Ｋｕｎｏ）
目 次
1 題材分類による献立作成の提案 阪大・情報科学（Ｏｓａｋａ Ｕ）
11
2内向木による有向グラフの被覆 京大・工学（Ｋｙｏｔｏ Ｕ）
3
4
5 6 7
1
8
加島 智子（Ｔｏｍｏｋｏ Ｋａｓｈｌｍａ）
石井 博昭（Ｈｌｒｏａｋｌ Ｉｓｈ11）
一一一コ口働墨画・ 一 ● 髄融一のの。一8
神山 直之（Ｎａｏｙｕｋｉ Ｋａｍｌｙａｍａ）
加藤 直樹（Ｎａｏｋｌ Ｋａｔｏｈ）
Ａｎ Ａｌｇｏｎｔｈｍ ｆｏｒ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｏｆ Ｍａｔｎｘ ｃｅ Ａｌｇｅｂｒａｓ Ｇｅｎｅｒａｔｅｄ ｂｙ
Ｓｙｍｍｅｔｎｃ Ｍａｔｎｃｅｓ 一一 一 一一一一 一一一一 一一一 一 一一 ・一一一一一 一一一一一 一 一 一 一 15
東大・情報理工学系（ＵＴｏｋｙｏ） 室田 一雄（Ｋａｚｕｏ Ｍｕｒｏｔａ）
〃 寒野 善博（Ｙｏｓｈｌｈｌｒｏ Ｋａmmｏ）
東工大 情報理工学（Ｔｏｋｙｏ Ｉｎｓｔ Ｔｅｃｈ） 小島 政和（Ｍａｓａｋａｚｕ ＫｏＪｌｍａ）
〃 小島 定吉（Ｓａｄａｙｏｓｈ1 ＫｏＪｌｍａ）
多目的順序メディアン立地問題 ...一.ｅｅ.一.一一一.、一一27
筑波大・システム情報工学（ＵＴｓｕｋｕｂａ） 大澤 義明（Ｙｏｓｈｌａｋ 1 Ｏｈｓａｗａ）
鉄道総合技術研（Ｒａｌｌｗａｙ Ｔｅｃｈ Ｒｅｓ Ｉｎｓｔ） 尾崎 尚也（Ｎａｏｙａ Ｏｚａｋｉ）
Ｖｒｌｊｅ Ｕ Ｂｒｕｓｓｅｌ Ｆｒａｎｋ Ｐｌａｓｔｒｉａ
鉄道総合技術研（Ｒａｌｌｗａｙ Ｔｅｃｈ Ｒｅｓ Ｉｎｓｔ） 田村 一網（Ｋａｚｕｋｌ Ｔａｍｕｒａ）
凸幾何上のマトロイドと貧欲アルゴリズムー…一一…一… 一一.一一…一37
京大 数理研（Ｋｙｏｔｏ Ｕ） 佐野 良夫（Ｙｏｓｈｌｏ Ｓａｎｏ）
密輸量決定戦略のある密輸取締ゲーム ｅｅ一一ｅ一一一ｅ一一一・・。一一・一一一…・一・・、。一・、・一一45
防衛大学校（Ｎａｔ Ｄｅｆｅｎｓｅ・Ａｃａｄ） 宝崎 隆祐（Ｒｙｕｓｕｋｅ Ｈｏｈｚａｋ 1 ）
スタノフスケジューリングにおける修正しやすさを考慮した解の分析一一一 一一56総合研究大学院大（Ｇｒａｄｕａｔｅ Ｕ Ａｄｖａｎｃｅｄ Ｓｔｕｄｌｅｓ）
久保 琢磨（Ｔａkmｍａ Ｋｕｂｏ）
国立情報学研（Ｎａｔ Ｉｎｓｔ Ｉｎｆｏ） 宇野 毅明（Ｔａ：ｋｅａｋｌ Ｕｎｏ）
2次錐相補性問題に対するＦｌｓｃｈｅｒ−Ｂｕｍｅｌｓｔｅｒ関数を用いた
平滑化ニューートン法について 一一・一一一 一一…一・・。一一一一ｅ・一.一.一一・一・…一一59
東京理大・理（Ｔｏｋｙｏ Ｕ Ｓｃ 1 ） 成島 康史（Ｙａｓｕｓｈ 1 Ｎａｒｕｓｈｌｍａ）
愛知大・経営総合科学研（Ａｌｃｈｌ Ｕ） 相良 信子（Ｎｏｂｕｋｏ Ｓａｇａｒａ）
東京理大 理（Ｔｏｋｙｏ Ｕ Ｓｃ 1） 小笠原 英穂（Ｈｌｄｅｈｏ Ｏｇａｓａｗａｒａ）
一1一・
9Ａｎ ｅｘｔｅｎｓｉｏｎ ｏｆ ｔｈｅ ｅｘｉｓｔｅｎｃｅ ｔｈｅｏｒｅｍ ｏｆ ａ ｐｕｒｅ−ｓｔｒａｔｅｇｙ Ｎａｓｈ ｅｑｕｉｌｉｂｎｕｍ 一一一一一一一一一一一一一67
九大・数理学（Ｋｙｕｓｈｕ Ｕ） 佐藤 潤一（Ｊｕｎ−
1ｃｈｉ Ｓａｔｏ）
〃 川崎 英文（ＨｌｄｅｆＵｍ1 Ｋａｗａｓａｋ1） 1Ｏ Ａ Ｓｔｒｕｃｔｕｒｅ Ｔｈｅｏｒｙ ｆｏｒ ｔｈｅ Ｐａｒａｍｅｔｎｃ Ｓｕｂｍｏｄｕｌａｒ ｌｎｔｅｒｓｅｃｔｉｏｎ Ｐｒｏｂｌｅｍ 一一一一一一一一一一一一一一一76
京大・数理研（Ｋｙｏｔｏ Ｕ） 藤重 悟（Ｓａｔｏｒｕ ＦｕＪｉｓｈｉｇｅ）
東工大・情報理工学（Ｔｏｋｙｏ Ｉｎｓｔ Ｔｅｃｈ） 永野 清仁（Ｋｌｙｏｈｌｔｏ Ｎａｇａｎｏ）
1 1ｌｎｔｅｇｅｒ Ｐｒｏｇｒａｍｍｉｎｇ ｆｏｒ ａ Ｐｈｒａｓｅ Ａｈｇｎｍｅｎｔ Ｐｒｏｂｌｅｍ
Ｏｎ ＳｔａｔｌＳｔｌＣａｌ Ｍａｃｈｍｅ ＴｒａｎＳｌａｔｌＯｎ 一 一一ｅｅｅ 一一一 ｅ 一 一一一一一一一一一ｅｅ一一一一一一一一一一一一一一一一一一一一一一一一一一一一87
12
13
14 15
16
17
18
筑波大・システム情報工学（Ｕ・Ｔｓｕｋｕｂａ）
阪大・情報科学（Ｏｓａｋａ Ｕ）
筑波大・システム情報工学（Ｕ・Ｔｓｕｋｕｂａ）
中央大・理工（Ｃｈｕｏ Ｕ）
山本 幹雄（Ｍｌｋｌｏ Ｙａｍａｍｏｔｏ）
梅谷 俊治（ＳｈｕｎＪｉ Ｕｍｅｔａｎ1） 越川 満（Ｍｉｔｓｕｒｕ Ｋｏｓｈｉｋａｗａ）
松井 知己（Ｔｏｍｏｍｉ Ｍａｔｓｕ1）
印刷工程における段取り回数最小のモデル化・一………一ｅ一一ｄ一一一一ｐ・一。一・・一…一一一・一一一一一一94
大分工業高専（Ｏｎａ Ｎａｔ Ｃｏｌｌ Ｔｅｃｈ） 松本慎平（Ｓｈｌｍｐｅｉ Ｍａｔｓｕｍｏｔｏ）
県立広島大・経営情報（Ｐｒｅｆ Ｈｌｒｏｓｈｌｍａ Ｕ） 上野 信行（Ｎｏｂｕｙｕｋ1Ｕｅｎｏ）
阪大・情報科学（Ｏｓａｋａ Ｕ） 奥原 浩之（ＫｏＪ1Ｏｋｕｈａｒａ）
〃 石井 博昭（Ｈｌｒｏａｋ1 ｌｓｈｉ1）
電気回路の混合解析における微分代数方程式の指数最小化ｔｅ・一一一。一一一一一一一一一一104 京大 数理研（Ｋｙｏｔｏ Ｕ） 岩田 覚（Ｓａｔｏｒｕ Ｉｗａｔａ）
東大 情報理工学系（ＵＴｏｋｙｏ） 高松 瑞代（Ｍｌｚｕｙｏ Ｔａｋａｍａｔｓｕ）
Ａｎ ａｐｐｒｏａｃｈ ｔｏ ｒｏｂｕｓｔ ｍｍｉｍａｘ ｒｅｃｅｄｍｇ ｈｏｎｚｏｎ ｃｏｎｔｒｏｌ ｐｒｏｂｌｅｍｓ 一一一一一一一一一一一一一一一一 一 一一115
筑波大・システム情報工学（ＵＴｓｕｋｕｂａ） 島辺 徹（Ｔｏｉｍ Ｋａｗａｂｅ）
資源制約付きプロジェクト・スケンユーリング問題に関する基礎的研究一ｅ一.一ｅｅ−125 阪大・情報科学（Ｏｓａｋａ Ｕ） 藤原 稔久（Ｔｏｓｈｌｈｌｓａ ＦｕＪｉｗａｒａ）
摂南大・工（Ｓｅｔｓｕｎａｎ Ｕ） 諏訪 晴彦（Ｈａｒｕｈｌｋｏ Ｓｕｗａ）
阪大 情報科学（Ｏｓａｋａ Ｕ） 森田 浩（Ｈｉｒｏｓｈｉ Ｍｏｎｔａ）
ＤＳＭ通信に対するＦＤＭＡ最適性とそれに基づいた解法一一一一一一一一一・一一。…一131 京大 情報学（Ｋｙｏｔｏ Ｕ） 林 俊介（Ｓｈｕｎｓｕｋｅ Ｈａｙａｓｈ1） ＵＭｕｍｅｓｏｔａ Ｚｈｉ−Ｑｕａｎ Ｌｕｏ
マルチスタート単体法による多峰関数の最適化 ・一一・一 142
筑波大・システム情報工学（ＵＴｓｕｋｕｂａ） 外崎 真造（Ｓｈｌｎｚｏ Ｔｏｎｏｓａｋ
1）〃 久野 誉人（Ｔａｋａｈｌｔｏ Ｋｕｎｏ）
Ａ ｔｗｏ ｓｔａｇｅ ａｐｐｒｏａｃｈ ｆｏｒ Ｒｕｓｓｅｌｌ ｍｅａｓｕｒｅ ｌｎ ＤＥＡ 一 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一152 静岡大 工（Ｓｈｌｚｕｏｋａ Ｕ） 関谷 和之（Ｋａｚｕｙｕｋｌ Ｓｅｋｌｔａｎ1）
一11岬
19
20
21 22
23
24 25
26
27
Ｍｅｔｎｃ−Ｐｒｅｓｅｒｖｍｇ Ｒｅｄｕｃｔｉｏｎ ｏｆ Ｅａｒｔｈ Ｍｏｖｅｒ ｓ Ｄｉｓｔａｎｃｅ 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一164
筑波大・システム情報工学（ＵＴｓｕｋｕｂａ） 高野 祐一（Ｙｕｌｃｈｌ Ｔａｋａｎｏ）
〃 山本 芳嗣（Ｙｏｓｈｌｔｓｕｇｕ Ｙａｍａｍｏｔｏ）
非負行列分解による画像の構成部品抽出。。一一一…一一…一一一一ｔ・一一一一一…一一一一一一174
筑波大・システム情報工学（ＵＴｓｕｋｕｂａ） 小川 直哉（Ｎａｏｙａ Ｏｇａｗａ）
〃 高野 祐一（Ｙｕｌｃｈｌ Ｔａｋａｎｏ）
〃 山本 芳油（Ｙｏｓｈｌｔｓｕｇｕ Ｙａｍａｍｏｔｏ）
ｉｉ Ａｎｔｏｍ Ｗｉｂｏｗｏ
ｖ−Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｍｅ ａｓ Ｃｏｎｄｉｔｉｏｎａｌ Ｖａｌｕｅ−ａｔ−Ｒｉｓｋ Ｍｍｉｍｉｚａｔｉｏｎ 一一一一一一一一一一一一一一一一一183
慶雁大・理工（Ｋｅｌｏ Ｕ） 武田 朗子（Ａｋｌｋｏ Ｔａｋｅｄａ）
多項式記憶量による非線形大域的最適化一一ｅ一一一一一一一一一一一一一一一一一一一一一一一…194
筑波大・システム情報工学（ＵＴｓｕ km ｂａ） 対馬 伊織（Ｉｏｒｌ Ｔｓｕｓｈｌｍａ）
久野 誉人（Ｔａｋａｈｌｔｏ Ｋｕｎｏ）
ロハストＮａｓｈ均衡問題に対する解の一意存在性について一・一一一・・一…一一一一一一一203
京大・情報学（Ｋｙｏｔｏ Ｕ） 西村 亮一（Ｒｙｏｌｃｈｉ Ｎｉｓｈｉｍｕｒａ）
〃 林俊介（Ｓｈｕｎｓｕｋｅ Ｈａｙａｓｈ1）
〃 福島 雅夫（Ｍａｓａｏ Ｆｕｋｕｓｈｌｍａ）
セル複体に付随するグラフの向き付けとその最適解一・ｂ一・ｅ−ｅ一一…一一一…一…一・・一・・一・一。一.214
筑波大・システム情報工学（ＵＴｓｕｋｕｂａ） 八森 正泰（Ｍａｓａｈｉｒｏ Ｈａｃｈｌｍｏｎ）
マルチコア・マルチプロセノサ環境向け分枝限定アルゴリズムの研究一…一225
筑波大・システム情報工学（ＵＴｓｕｋｕｂａ） 木幡 周治（Ｓｈ叩Ｋｏｈａｔａ）
〃 久野 誉人（Ｔａｋａｈｌｔｏ Ｋｕｎｏ）
制約無し最小化問題に対するｌｎｅｘａｃｔ Ｃｕｂｉｃ Ｒｅｇｕｌａｒｉｚｅｄ Ｎｅｗｔｏｎ法一一一一一一一一一 234 京大・情報学（Ｋｙｏｔｏ Ｕ） 上田 三面（ＫｅｎＪｉ Ｕｅｄａ）
〃 山下 信雄（Ｎｏｂｕｏ Ｙａｍａｓｈｌｔａ）
Ｏｎ Ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｔｈｅ Ｓｉｍｐｌｉｃｉａｌ Ｂｒａｎｃｈ−ａｎｄ−Ｂｏｕｎｄ Ａｌｇｏｎｔｈｍ 一一一一一一一一一一一一一一一一一一一一一一一一一一244
筑波大・システム情報工学（ＵＴｓｕ km ｂａ） 久野 誉人（Ｔａｋａｈｉｔｏ Ｋｕｎｏ）
一 Ｕｌ
