以下の日時で「OR横断若手の会 (通称 KSMAP)」の第3回研究会開催が開催されます。Ted Ralphs 氏とThorsten Koch 氏については RAMP シンポジウム でも発表されますが、これに加えて10月1日午後に中央大学(東京)でも講演予定です。また Stefan Vigerske氏は 9月26日の午後に中央大学で講演予定です。
<< 開 催 要 領 >>
●第 3 回研究会
日時:10 月 6 日 (土) 14:00 ~ 17:20
場所:京都大学 総合研究8号館 講義室3
(2011年度まで工学部8号館と呼ばれていた建物です)
[京都大学周辺地図] http://www.kyoto-u.ac.jp/ja/access/campus/map5r.htm
[京都大学構内地図] http://www.kyoto-u.ac.jp/ja/access/campus/map6r_n.htm
-------------------------------------------------------------------
テーマと講師:
14:00 ~ 15:00
(1) Ted Ralphs (Lehigh University)
「Complexity and Multi-level Optimization」
Many real-world optimization problems involve multiple decision-makers,
multiple
objectives, and/or decisions that are made in multiple stages. Such
problems arise both in practical applications (game theory, stochastic
programming) and in theoretical contexts (analysis of recursive
algorithms). The computational complexity of such problems is often
difficult to discern, but can generally be understood in terms of the
so-called "polynomial time hierarchy," of which the classes P and NP are
the first two levels. In this talk, we discuss the complexity of and
relationships between a number of related problem classes, focusing
specifically on multi-level problems with discrete decisions at some or
all levels/stages. We present a new result that shows that the
separation problem for a certain strengthened version of the well-known
generalized subtour elimination constraints is not in NP unless the
polynomial time hierarchy collapses to its second level.
15:10 ~ 16:10
(2) Stefan Vigerske (GAMS Software GmbH)
「Solving MINLPs with SCIP」
We discuss recent extensions of the constraint integer programming
framework SCIP for solving mixed-integer nonlinear programs. Nonlinear
constraints (convex or nonconvex) are handled within an LP-based
branch-and-cut algorithm by reformulation, linear relaxation, and domain
propagation. In an extensive computational study, we compare the
performance of our implementation with state-of-the-art solvers for
MINLP and analyze the impact of various solver components on the overall
performance.
16:20 ~ 17:20
(3) Thorsten Koch (Zuse Institute Berlin)
「What Could a Million Cores Do To Solve Integer Programs?」
Given the steady increase in cores per CPU, it is only a matter of time
until
supercomputers will have a million or more cores. In this talk, we
investigate the opportunities and challenges that will arise when trying
to utilize this vast computing power to solve a single
integer linear optimization problem. We also raise the question of
whether best practices in sequential solution of ILPs will be effective
in massively parallel environments.
------------------------------------------------------------------
<< 開 催 要 領 >>
●第 3 回研究会
日時:10 月 6 日 (土) 14:00 ~ 17:20
場所:京都大学 総合研究8号館 講義室3
(2011年度まで工学部8号館と呼ばれていた建物です)
[京都大学周辺地図] http://www.kyoto-u.ac.jp/ja/access/campus/map5r.htm
[京都大学構内地図] http://www.kyoto-u.ac.jp/ja/access/campus/map6r_n.htm
-------------------------------------------------------------------
テーマと講師:
14:00 ~ 15:00
(1) Ted Ralphs (Lehigh University)
「Complexity and Multi-level Optimization」
Many real-world optimization problems involve multiple decision-makers,
multiple
objectives, and/or decisions that are made in multiple stages. Such
problems arise both in practical applications (game theory, stochastic
programming) and in theoretical contexts (analysis of recursive
algorithms). The computational complexity of such problems is often
difficult to discern, but can generally be understood in terms of the
so-called "polynomial time hierarchy," of which the classes P and NP are
the first two levels. In this talk, we discuss the complexity of and
relationships between a number of related problem classes, focusing
specifically on multi-level problems with discrete decisions at some or
all levels/stages. We present a new result that shows that the
separation problem for a certain strengthened version of the well-known
generalized subtour elimination constraints is not in NP unless the
polynomial time hierarchy collapses to its second level.
15:10 ~ 16:10
(2) Stefan Vigerske (GAMS Software GmbH)
「Solving MINLPs with SCIP」
We discuss recent extensions of the constraint integer programming
framework SCIP for solving mixed-integer nonlinear programs. Nonlinear
constraints (convex or nonconvex) are handled within an LP-based
branch-and-cut algorithm by reformulation, linear relaxation, and domain
propagation. In an extensive computational study, we compare the
performance of our implementation with state-of-the-art solvers for
MINLP and analyze the impact of various solver components on the overall
performance.
16:20 ~ 17:20
(3) Thorsten Koch (Zuse Institute Berlin)
「What Could a Million Cores Do To Solve Integer Programs?」
Given the steady increase in cores per CPU, it is only a matter of time
until
supercomputers will have a million or more cores. In this talk, we
investigate the opportunities and challenges that will arise when trying
to utilize this vast computing power to solve a single
integer linear optimization problem. We also raise the question of
whether best practices in sequential solution of ILPs will be effective
in massively parallel environments.
------------------------------------------------------------------