セッション１: 組合せ最適化と離散アルゴリズム (Combinatorial Optimization and Discrete Algorithms)

オーガナイザー： 牧野 和久 （東京大学）

本セッションでは，組合せ最適化と離散アルゴリズム分野において世界的にご活躍されている３名の研究者を迎えて，最新の研究動向をお話を頂く．具体的には，組合せ最適化分野から，グラフ・ネットワーク上の最適化問題として古くから盛んに研究されている「ネットワーク構成問題」と組合せ最適化分野で中心的な役割を果たす「劣モジュラ最小化問題」について解説していただく．また，離散アルゴリズム分野からは，ゲノムやデータマイニングなどにおいて巨大なデータを扱う際に必要な「圧縮データ構造」について解説していただく．

定兼 邦彦 (Kunihiko Sadakane)

九州大学 (Kyushu University, Department of Computer Science and Communication Engineering)
タイトル： 圧縮データ構造とその最新動向
The Latest Trend of Compressed Data Structures
概要：大量のデータを扱う場合の問題点として記憶領域の大きさがある．その解決のために近年圧縮データ構造が盛んに研究されている．これは従来のデータ構造のサイズを圧縮し，かつ問合せの計算量も増えないというものである．これらのデータ構造の基本と，最近の結果について解説する．

石井 利昌 (Toshimasa Ishii)

小樽商科大学 (Otaru University of Commerce, Department of Information and Management Science)
タイトル：連結度要求を持つネットワーク構成問題
Network Design Problem with Connectivity Requirements
概要：グラフ理論における連結度の概念は, 種々のネットワークの制御・設計において，耐故障性に関する基本的な評価尺度として用いられる. 所望の連結度を保証するネットワークを最適構成する問題として，連結度増大問題と供給点配置問題を取り上げる．近年，これらの問題に対し，効率的なアルゴリズムの研究が盛んに行われており，また劣モジュラ関数を用いて一般化された離散最適化問題の研究もされてきている．本発表では，これらの問題に対する最近の研究結果を紹介する．

岩田 覚 （Satoru Iwata)

京都大学数理解析研究所 (Research Institute for Mathematical Sciences, Kyoto University)
タイトル：劣モジュラ最適化の最近の進展
Recent Progress in Submodular Optimization
概要：劣モジュラ関数は，行列の階数，ネットワークのカット容量，多元情報源のエントロピー関数など，応用数学の広範な分野で現れる集合関数であり，凸関数の離散版として認識されている．数理計画法においては, 1970年に J. Edmonds によって重要性が指摘されて以来，効率的に解くことのできる離散最適化問題に共通の構造として注目されてきた．本講演では，劣モジュラ関数の最小化を中心に，劣モジュラ最適化の最近の進展を紹介する．

セッション２: ロジスティクスにおける最適化 (optimization in logistics)

オーガナイザー： 柳浦 睦憲 （名古屋大学）

ロジスティクスにおける最適化は，生産・流通・在庫管理などを含む大きなシステムの効率化に欠かせないものであり，その重要性が近年強く認識されるようになったことと問題の多様性から，理論と応用の両面において活発に研究活動が行われている．本セッションでは，学術的な方面で活躍されている方と実務において多大な貢献をなさっている方を取り混ぜて3名の講師をお招きし，最近の話題をお話いただく予定である．

M. Grazia Speranza (University of Brescia)

タイトル： The split delivery vehicle routing problem
概要：In the vehicle routing problem (VRP) the objective is to construct a minimum cost set of routes serving all customers where the demand of each customer is less than or equal to the vehicle capacity and where each customer is visited once. In the split delivery vehicle routing problem (SDVRP) the restriction that each customer is visited once is removed. Moreover, the demand of each customer can be greater than the capacity of the vehicles. The SDVRP is NP-hard, even under restricted conditions on the costs, when all vehicles have a capacity greater than two, while it is solvable in polynomial time when the vehicles have a maximum capacity of two.

We show that the cost savings that can be reached by allowing split deliveries is at most 50%. The variant of the VRP in which the demand of a customer may be larger than the vehicle capacity, but where each customer has to be visited a minimum number of times, is also considered. We show that the cost savings that can be reached by allowing more than the minimum number of required visits is again at most 50%. Furthermore, we analyze the performance of simple heuristics that handle customers with demands larger than the vehicle capacity by employing full load out-and-back trips to these customers until the demands become less than or equal to the vehicle capacity. Computational results are also shown to estimate the average savings that can be obtained with split deliveries.

A simple and effective tabu search algorithm is compared with a sophisticated heuristic that, starting from the solution obtained by the tabu search algorithm and using the information collected during the tabu search, builds promising routes and solves MILP models to decide which routes to use and how to serve the customers through those routes. Computational experiments are reported for a set of benchmark problems.

久保 幹雄 （東京海洋大学）

タイトル：サプライ・チェイン最適化システムと事例
概要：ロジスティクスの理論と実務には，未だ大きなギャップがある．これを埋めるために，私たち研究者側からできるとこは，旧来の理論的な研究対象であった古典モデルを実務に直結するように拡張すること，拡張されたモデルに対してアルゴリズムを導き出すこと，さらは，これらのアルゴリズムを組み込んだ意思決定支援システムを構築することである。本稿では，筆者らが開発してきたロジスティクス最適化のための 意思決定支援システムである在庫方策最適化，安全在庫配置，配送計画，ロジスティクス・ネットワーク設計，ロットサイズ決定，スケジューリング，収益管理について，その理論的背景を解説するとともに，幾つかの事例を紹介する．

岡野 裕之 （日本アイ・ビー・エム東京基礎研究所）

タイトル：時間制約付き混載輸送ネットワーク設計問題
概要：全国規模の物流サービスを実現する輸送ネットワークの設計問題を取り上げる。この問題では、全国に配置された拠点に荷物を集約し、目的拠点の異なる荷物を混載することで輸送効率を高める物流形態を扱う。すべての出発拠点と目的拠点のペアごとに最大到達時間が規定されており、その時間制約の範囲で荷物の輸送経路とキャリアの運行スケジュールを決定する。この問題に対し、荷物のルーティングとキャリア割当の二つの問題に分割するアプローチを提案し、その有効性を議論する。

セッション３: 計算幾何と最適化 (Computational Geometry and Optimization)

オーガナイザー： 平田 富夫 （名古屋大学）

計算幾何学はその誕生から30年ほどの間に目覚しい発展をとげ、現在も活発な研究がなされている。計算幾何学と最適化技法とは親密な関係にあり、計算幾何学の問題に対し最適化手法が応用されたり、逆に、最適化技法の中に計算幾何学の手法を持ち込むことで計算効率を大きく改善したりすることがある。本セッションでは計算幾何学の分野で活躍しておられる4名の研究者にご講演いただく。

岡本 吉央 （豊橋技術科学大学）

Yoshio Okamoto (Department of Information and Computer Sciences, Toyohashi University of Technology)
タイトル： 凸多面体グラフの向き付け：数理とアルゴリズム
Polytopal Digraphs: Mathematics and Algorithms
概要：線型計画問題，線型相補性問題，双行列ゲームなどに対して，ピボット操作に 基づくアルゴリズムが古くから提案されているが，それらを抽象化することで 凸多面体グラフの向き付けが得られる．本講演では，そのような向き付けに対 して知られていることや考えられている問題を紹介する．

徳山 豪 （東北大学）

Takeshi Tokuyama (Graduate School of Information Sciences, Tohoku University)
タイトル：風変わりなボロノイ図と計算可能性
Non-standard variations of Voronoi diagrams and related computability problems
概要：ボロノイ図は計算幾何学では基本的なテーマであり、入力点集合の垂直二等分線たちを用いて平面もしくは空間を勢力域に分割する。さまざまなバリエーションが知られているが、本講演では、点集合が敵対関係と協力関係を混合して持ち、中立地帯も有する場合の新しいモデルを不動点定理と関連して紹介を行い、組み合わせ的性質や計算可能性についての議論を行う。浅野哲夫氏とJ. Matousek氏との共同研究をベースにしたものである。

浅野 哲夫 （北陸先端科学技術大学院大学）

Tetsuo Asano (School of Information Science, JAIST (Japan Advanced Institute of Science and Technology))
タイトル：最小２乗法の一般化
On generalization of a least-squared fitting
概要：最小２乗法というと，実験データの直線当てはめが思い浮かぶが，本講演ではその一般化と，同様の手法の別の問題への応用について述べる． ２次元平面上の点列

$(x_1, y_1), (x_2, y_2)< \ldots, x_n, y_n)$

として指定される実験データを最も良く近似する直線$y=ax + b$は，この直線との垂直方向距離の差の２乗和$\sum_{i=1}^n ax_i + b – y_i)^2$を最小にする定数$a, b$によって定まる．そのような２つの定数を求めるには，２乗和の式を$a$と$b$を変数と見なして，それぞれで偏微分して$0$と置いて得られる連立方程式を解けばよい．しかし，基準を垂直方向の距離の差（絶対値）の和に変更すると，一般的な偏微分が取れなくなって問題が難しくなる．しかし，計算量的には同じ線形時間で最適な直線が求まることが既に知られている． 本講演では，別の意味での一般化を考える．すなわち，１本の直線で近似するのではなく，任意に与えられた整数$k$に対して，最適な$k$回折れ曲がりの線分列を求めるのである．1回折れ曲がりだけであっても問題は難しいが，多項式時間で解けることを示す．しかも，差の２乗和でも差の絶対値和でも同様に解けることを示す．また，一般の$k$の値に対しては，近似比を幾らでも小さくできる近似アルゴリズムも示す． 直線当てはめ以外の問題にも同じ手法を用いることができる．たとえば，平面上に多数の点が配置されているとして，それぞれの点への距離を指定して，なるべくその距離になるように新たな点を挿入するという問題を考える．実際に配置したときの距離と最初に与えられていた距離との差の（２乗，絶対値）和を最小にするという問題を考えたとき，計算幾何学におけるアレンジメントの概念と併用すると，同じ手法で解けることを示す．

加藤 直樹 （京都大学）

Naoki Katou (Kyoto University)
タイトル：三角形分割とラーマングラフ：建築への応用
Triangulation and Laman Graph: Application to Architecture
概要：部材がジョイントでつながっているトラス構造物はグラフ構造で表現される。トラス構造物が安定であるための必要最低限の部材から成る場合、静定構造物と呼ばれている。静定構造物に対応するグラフはminimally rigid graphとして知られている。本論文では平面上のトラス構造物を対象として、あたえられた平面上の点集合Ｐに対して、Ｐを頂点とし、辺が交差しないminimally rigid graphをすべて列挙するアルゴリズムについて述べる。minimally rigid graphはLaman graphとも呼ばれ、その組合せ的性質については多くの研究者によって研究されており、そのようなグラフ全体がマトロイドの基を作ることが知られている。したがって、逆探索法によりすべてのLaman graphを列挙することができる。 一方、平面上に埋め込まれた非交差Laman graph全体はマトロイドとはならない。最近、非交差Laman graphに対して、グラフ構造や幾何的構造を明らかにし、非交差Laman graph同士に対して隣接関係を上手に定めることにより逆探索法によって、非交差Laman graphをすべて列挙するアルゴリズムを開発した。あらかじめ用いる枝が一部指定されている場合も取り扱うことができる。本講演ではその概要と構造最適化への応用について述べる。

セッション４: 錐最適化における理論と応用 (Theory and Applications of Conic Optimization)

オーガナイザー： 吉瀬 章子 （筑波大学）

半正定値計画問題（SDP）は「2000年の線形計画問題（LP）」とも呼ばれ，LPにおける非負制約を，対称行列の 半正定値制約に置き換えた問題である．制御理論，組合せ理論などに多くの応用例がある．非負制約と半正定値 制約は全く異質な制約に見受けられるが，ともに閉凸錐を与えるという共通点をもつ．1990年代に内点法の解法 としての有効性が示されて以来，SDPはLPを包括する新しい最適化問題として定着しつつある．近年はさらに閉 凸錐上の最適化問題（錐計画問題）に対象が拡張され，活発な研究が行われている．本セッションでは同分野で 活躍されている4名の研究者をお迎えし，理論と応用に関する最新の成果をお話し頂く．

Etienne de Klerk (Tilburg University)

タイトル： The complexity of optimization over a simplex
概要：We consider the problem of minimizing a continuous function over a simplex. This relatively simple optimization problem has several applications. If the function is quadratic, the applications already include portfolio optimization, population dynamics, genetics, finding maximum stable sets in graphs, and lower bounding the crossing number of certain classes of graphs. For more general functions, the applications include training neural networks and minimizing the expected shortfall of a portfolio.

We will first review complexity results for minimizing polynomials over the standard simplex. In addition, we show that there exists a polynomial time approximation scheme (PTAS) for minimizing some classes of functions (including Lipschitz continuous functions) over the standard simplex.

林 俊介 （京都大学）

タイトル：二次錐制約をもつ半無限計画問題に対する切除平面アプローチ
A cutting plane approach for semi-infinite programming problems with second-order cone constraints
概要：半無限計画問題とは，有限次元の決定変数と無限個の制約式で特徴付けられる最適化問題であり，幅広い分野に 応用が可能なことから，これまで盛んに研究がなされてきた．しかし，既存の研究の殆どは等式制約および不等 式制約のみで表されるような問題を対象としており，二次錐制約を含むような半無限計画問題に対する研究はこ れまで殆どなされていなかった．そこで，本研究では，Lai and Wuの提案した切除平面アプローチを二次錐制約 を含む半無限計画問題に拡張した手法を提案する．また，アルゴリズムにおける部分問題とその双対問題の解が 満たすべき二次錐相補性条件に対して，Jordan代数に基づいた解析を行うことにより，提案手法の収束性を示す． さらに，アルゴリズムの性能を調べるために行ったいくつかの数値実験の結果も合わせて報告する．

Yu Xia (統計数理研究所)

タイトル：The Maxdet problem – Algorithm and applications in machine learning
概要：We give some applications of the Maxdet problem in machine learning. The Maxdet problem is an extension of the semidefinite program and the weighted analytic center problem. It concerns the maximization of a sum of linear function and some weighted logarithmic determinants over the intersection of an affine space and the cone of positive semidefinite matrices. This problem can be approximated by interior-point methods with polynomial complexity. This is a joint work with Takashi Tsuchiya.

山下 真 （神奈川大学）

タイトル：量子化学における超大規模半正定値計画問題と並列計算による高速求解
SemiDefinite Programming arising from　Quantum Chemistry and Parallel Solver
概要：原子および分子の電子構造を計算することは、量子化学の基本的な対象として位置している．分子の基底状 態における電子構造を知るには、電子間の相関を表す行列が求まれば十分である．この行列は物理的制約である N-representability条件を満たさなければならないが、半正定値緩和を施すと半正定値計画問題に帰着できる． これを解くことで，分子の電子状態、エネルギーを変分的に求められる。この事実は 1960 年代には既に知られ ていたが，1990年代後半の主双対内点法の研究により数値的に計算することが可能となった．さらに，2000年以 降には, より精密な化学条件を取り込んだ半正定値計画問題へと発展している．

しかしながら，帰着された半正定値計画問題の規模は非常に大きく，1台の計算機では計算不可能な規模になる 傾向にある．そこで、半正定値計画問題に対するソフトウェアであるSDPA を並列化し，PC クラスタ上の計算パ ワーを用いてこのような超大規模半正定値計画問題に取り組む研究を行っている．

本発表では，前半を電子構造が半正定値計画問題に帰着される過程のダイジェストとし，後半を SDPA の並 列化，および PC クラスタ上の数値結果の紹介とする．