Tilte: The First Workshop on Computational Aspects of Solving Large-scale Optimization Problems
Date: March 23, 2012
Place: Room 6301, 6th building, 3rd floor, Korakuen Campus, Chuo University
http://global.chuo-u.ac.jp/english/visit/index.php
http://global.chuo-u.ac.jp/english/visit/korakuen.php
◯9:45 - 10:00 Katsuki Fujisawa (Chuo University)
Title: Introduction : CREST project and Workshops on Computational Aspects for Solving Large Scale Optimization Problems
◯10:00 - 10:30 Toyotaro Suzumura (Tokyo Institute of Technology)
Title: Performance Evaluation of Graph500 on Large-Scale Distributed Environment
◯10:30 - 11:00 Hans Mittelmann (Arizona State University, USA)
Title: Benchmarks for Optimization Software
Abstract: Under the title "Benchmarks for Optimization Software" we maintain extensive
evaluations of a large selection of optimization software. In this talk we
will report on the benchmarks in discrete optimization including those
based on MIPLIB 2010 as well as selected ones in continuous optimization.
[1] Benchmarks for Optimization Software, http://plato.asu.edu/bench.html
[2] MIPLIB 2010, http://miplib.zib.de, Math Prog Comp 3, 103-163 (2011)
◯11:00 - 11:15 Break
◯11:15 - 11:45 Toh Kim Chuan (National University of Singapore)
Title: Computational experience in solving large scale semidefinite programming.
Abstract: In this talk, we will report our computational experience
in solving large scale semidefinite programming based on two classes of methods.
The first class consists of inexact primal-dual interior-point methods for which
the linear system in each iteration is solved by a preconditioned Krylov subspace method.
The second class are nonlinear programming based
methods such as proximal-point method, alternating direction method of multiplier,
inexact accelerated proximal gradient method.
We will discuss the merits of the two classes of methods and present some
computational results.
◯11:45 - 12:15 Yasuaki Matsukawa and *Akiko Yoshise (University of Tsukuba)
Title: A Primal Barrier Function Phase I Algorithm for Nonsymmetric Conic Optimization Problems
Abstract: We call a positive semidefinite matrix whose elements are nonnegative a
{\em doubly nonnegative matrix}, and the set of those matrices the {\em
doubly nonnegative cone} (DNN cone).
The DNN cone is not symmetric but can be represented as the projection of
a symmetric cone embedded in a higher dimension.
In a previous paper, the authors demonstrated the efficiency of the DNN
relaxation using the symmetric cone representation of the DNN cone.
They showed that the DNN relaxation gives significantly tight bounds for a
class of quadratic assignment problems, but the computational time is not
affordable as long as we employ the symmetric cone representation.
They then suggested a primal barrier function approach for solving the DNN
optimization problem directly, instead of using the symmetric cone
representation.
However, most of existing studies on the primal barrier function approach
assume the availability of a feasible interior point.
This fact means that those studies are not inextricably tied to the
practical usage.
Motivated by these observations, we propose a primal barrier function
Phase I algorithm for solving conic optimization problems over the closed
convex cone $K$ having the following properties:
(a) $K$ is not necessarily symmetric, (b) a self-concordant function $f$
is defined over $\inter K$, and (c) its dual cone $K^*$ is not explicit or
is intractable, all of which are observed when $K$ is the DNN cone.
We analyze the algorithm and provide a sufficient condition for finite
termination.
◯12:15 - 13:30 Lunch
◯13:30 - 15:00 Tutorial Session 1
◎Timo Berthold (Zuse Institute Berlin, Germany)
Title: What is Linear and Mixed Integer Programming(LP/MIP)
Abstract: Linear programming (LP) means the optimization of a linear function
subject to a set of linear constraints. In mixed-integer programming
(MIP), additionally, some of the variables are required to take integer
values. Linear and mixed-integer programming are two of the most essential
techniques in theory and practice of mathematical optimization.
Nowadays, linear programs with hundreds of thousands of variables and
constraints can be solved efficiently. Although this is not generally true
for mixed-integer programming - which is NP-hard -, state-of-the-art
software often is able to solve large, practically relevant problems.
This talk is supposed to be an introduction to the computational aspects
of LP and MIP. We present three commonly used algorithms to solve
large-scale, practically relevant problems of these types: the simplex algorithm for
LPs, the general cutting plane method and the branch-and-bound algorithm
for IPs. We discuss some of their pitfalls and ruses and showcase a few
algorithmic enhancements the today's MIP solvers are equipped with.
◎Ambros Gleixner and Stefan Heinz (Zuse Institute Berlin, Germany)
Title: First steps with Zimpl and SCIP
Abstract: In this tutorial, we demonstrate the usage of the modeling language Zimpl
and the mixed integer programming solver SCIP. We show how to model two
different formulations for the well-known binpacking problem and discuss
their limitations. Feeding them into SCIP we compare their computational
performance within a standalone branch-and-cut solver.
Zimpl is an algebraic modeling language featuring exact arithmetic. SCIP is
branch-cut-and-price framework targeted towards the need of researchers. It
allows total control of the solution process and the access of detailed
information down to the guts of the solver. Both tools are part of the ZIB
Optimization Suite (http://zibopt.zib.de), which is free for academic use
and available in source code.
◎Stefan Heinz (Zuse Institute Berlin, Germany)
Title: Using SCIP as a branch-and-price framework
Abstract: Column generation is a technique to handle large-scale linear programs
efficiently. In practice, it is widely used to solve real world problems
within a branch-and-price approach. Examples are rolling stock roster
planning, duty scheduling, and vehicle scheduling.
In this talk we are focusing on the branch-and-price feature of SCIP. We
illustrate using the steel mill slab problem, how the framework SCIP is
easily customized for all needs of branch-and-price approach.
We first present the basic idea of column generation and
branch-and-price. Second, we show step-by-step, how the framework SCIP can
be applied as a branch-and-price framework. Finally, we discuss some
pitfalls of the branch-and-price method which are easily avoidable within
the SCIP framework.
◯15:30 - 15:45 Break
◯15:45 - 16:45 Tutorial Session 2
◎ Ambros Gleixner (Zuse Institute Berlin, Germany)
Title: Improving the accuracy of LP solvers
Abstract: We describe an iterative refinement procedure for computing extended precision or exact solutions
to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a
sequence of closely related LPs with limited precision arithmetic. The LPs solved at iterations of
this algorithm share the same constraint matrix as the original problem instance and are transformed
only by modification of the objective function, right-hand side, and variable bounds.
Exact computation is used to compute and store the exact representation of the transformed
problems, while numeric computation is used for computing approximate LP solutions and applying
iterations of the simplex algorithm. At all steps of the algorithm the LP bases encountered in the
transformed problems correspond directly to LP bases in the original problem description.
We demonstrate that this algorithm is effective in practice for computing extended precision
solutions and that this leads to direct improvement of the best known methods for solving LPs
exactly over the rational numbers. A proof-of-concept implementation is done within the SoPlex LP
solver.
◎ Timo Berthold (Zuse Institute Berlin, Germany)
Title: Primal Heuristics for MIP
Abstract: In modern MIP-solvers like the state-of-the-art
branch-cut-and-price-framework SCIP, primal heuristics play a major role
in finding and improving feasible solutions at the early steps of the
solution process.
Primal heuristics in SCIP can be categorized in three groups:
* rounding and propagation heuristics
* diving and objective diving heuristics
* large neighborhood search heuristics
We give examples for each of these classes, concentrating on recently
propsed algorithms. Further, we discuss the question of how the quality of
a primal heuristic should be evaluated and introduce a new a new
performance measure, the "primal integral". It assess the impact of these
primal heuristics on the ability to find feasible solutions, in
particular early during search. Finally, we discuss some computational results.
◯16:45 - 17:00 Break
◯17:00 - 17:30 Domenico Salvagnin (University of Padova, Italy)
Title: Three ideas for the Quadratic Assignment Problem
Abstract: We address the exact solution of the famous esc instances of the quadratic assignment problem. These
are extremely hard instances that remained unsolved―even allowing for a tremendous computing
power―by using all previous techniques from the literature. During this challenging task we found
that three ideas were particularly useful, and qualified as a breakthrough for our approach. The
present talk is about describing these ideas and their impact in solving esc instances. Our method
was able to solve, in a matter of seconds or minutes on a single PC, all easy cases (all esc16* plus
esc32e and esc32g). The three very hard instances esc32c, esc32d and esc64a were solved in less than
half an hour, in total, on a single PC. We also report the solution, in about 5 hours, of tai64c. By
using a facility-flow splitting procedure, we were also able to solve to proven optimality, for the
first time, esc32h (in about 2 hours) as well as “the big fish” esc128 (to our great surprise, the
solution of the latter required just a few seconds on a single PC).
◯17:30 - 18:00 *Shunji Umetani (Osaka University), Masanao Arakawa (Fujitsu Limited) and Mutsunori Yagiura (Nagoya University)
Title: A heuristic algorithm for the set multicover problem with generalized upper bound constraints
Abstract: The set covering problem (SCP) is one of representative combinatorial
optimization problem, which has many practical applications, e.g.,
crew scheduling, vehicle routing, facility location and data analysis.
In this talk, we consider an extension of SCP introducing (i)
multicover and (ii) generalized upper bound (GUB) constraints, which
substantially extend the variety of its applications.
For the conventional SCP, it has been known that relaxed problems
give us a good device called the pricing method to reduce the number of
variables, and several efficient heuristic algorithms utilizing this
idea have been developed to solve very large-scale instances with up
to 5000 constraints and 1,000,000 variables.
However, GUB constraints often make the standard pricing method less
effective, because they prevent solutions from having highly evaluated
variables simultaneously.
To overcome this, we develop a hybrid approach of metaheuristics and
the pricing method, in which we propose an evaluation scheme of
variables based on penalty weights that are adaptively controlled
during the search of metaheuristic algorithm.
Another feature of our algorithm is an efficient implementation of
local search with the 2-flip neighborhood.
According to computational comparison on benchmark instances with the
latest MIP solvers, our algorithm performs quite efficiently for
various types of problem instances, especially for very large-scale
instances.
アクセス
トータル
