10月2日に SCOPE 講演会を行います。今回は整数計画問題に関する講演（２件）になります。是非ご参加下さい。
日 時 ： 2010年10月2日（土）14:00～
会 場 ： 中央大学 後楽園キャンパス 6 号館4階 6410号室
講演1
講演者 ： Karen Aardal氏（Delft Institute of Technology and CWI - Amsterdam）
講演題目 ： Integer programming, lattices, reduced bases
講演概要：
I will discuss how to use the structure of lattices to reformulate and solve
integer programming problems. I will take a closer look at integer knapsack
problems and illustrate how it is possible to use the structure of lattices
to prove properties of certain classes of knapsack problems, and how these
properties can be used in designing practically efficient algorithms.
講演2
講演者 ： Timo Berthold氏（Zuse Institute Berlin(ZIB), Berlin）
講演題目 ： Solving MIQCPs with SCIP
講演概要：
Mixed-integer programming (MIP) and constraint programming (CP) proved to be powerful tools to model and solve
large-scale optimization problems. Constraint integer programming (CIP) is a novel generalization of MIP that
supports the notion of arbitrary constraints as in CP. We introduce the algorithmic ideas of CIP and present
SCIP, a framework for constraint integer programming.
We show how to extend SCIP towards a solver for mixed integer quadratically constrained programs (MIQCPs).
The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies
already implemented in SCIP. We give an overview of the relaxation, reformulation, separation, and propagation
techniques that are used to handle quadratic constraints efficiently. Computational experiments indicating
the potential of the approach are provided.
In the second part of the talk, we present Undercover, a primal heuristic for mixed-integer nonlinear
programming (MINLP). The heuristic constructs a MIP subproblem (sub-MIP) of a given MINLP by fixing a subset
of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed
in order to linearize each constraint. Subsequently, these variables are fixed to approximate values, e.g.
obtained from a linear outer approximation. The resulting sub-MIP is solved by a MIP solver. We present
computational results on a general test set of MIQCPs selected from the MINLPLib.
日 時 ： 2010年10月2日（土）14:00～
会 場 ： 中央大学 後楽園キャンパス 6 号館4階 6410号室
講演1
講演者 ： Karen Aardal氏（Delft Institute of Technology and CWI - Amsterdam）
講演題目 ： Integer programming, lattices, reduced bases
講演概要：
I will discuss how to use the structure of lattices to reformulate and solve
integer programming problems. I will take a closer look at integer knapsack
problems and illustrate how it is possible to use the structure of lattices
to prove properties of certain classes of knapsack problems, and how these
properties can be used in designing practically efficient algorithms.
講演2
講演者 ： Timo Berthold氏（Zuse Institute Berlin(ZIB), Berlin）
講演題目 ： Solving MIQCPs with SCIP
講演概要：
Mixed-integer programming (MIP) and constraint programming (CP) proved to be powerful tools to model and solve
large-scale optimization problems. Constraint integer programming (CIP) is a novel generalization of MIP that
supports the notion of arbitrary constraints as in CP. We introduce the algorithmic ideas of CIP and present
SCIP, a framework for constraint integer programming.
We show how to extend SCIP towards a solver for mixed integer quadratically constrained programs (MIQCPs).
The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies
already implemented in SCIP. We give an overview of the relaxation, reformulation, separation, and propagation
techniques that are used to handle quadratic constraints efficiently. Computational experiments indicating
the potential of the approach are provided.
In the second part of the talk, we present Undercover, a primal heuristic for mixed-integer nonlinear
programming (MINLP). The heuristic constructs a MIP subproblem (sub-MIP) of a given MINLP by fixing a subset
of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed
in order to linearize each constraint. Subsequently, these variables are fixed to approximate values, e.g.
obtained from a linear outer approximation. The resulting sub-MIP is solved by a MIP solver. We present
computational results on a general test set of MIQCPs selected from the MINLPLib.
アクセス
トータル
