IMI Workshop on Optimization in the Real World– Toward solving real world optimization problems –2014/10/14 − 15
Seminar Room 7, Faculty of Mathematics building,Ito Campus, Kyushu University

Schedule of Oct. 14 (Each talk consists 40 min. including question time)
13:30 – 13:40 Yasuhide Fukumoto (IMI, Kyushu University) – Opening Remark
13:40 – 14:20 Katsuki Fujisawa (IMI, Kyushu University)
14:30 – 15:10 Kengo Nakajima (University of Tokyo)
15:30 – 16:10 Tobias Achterberg (GUROBI Optimization)
16:20 – 17:00 Gerald Gamrath (ZIB)
17:10 – 17:50 Matteo Fischetti (University of Padova)
18:15 – Banquet @ ZauoBBQ by Bus

Schedule of Oct. 15 (Each talk consists 40 min. including question time)
10:00 – 10:40 Emerson Escolar (Kyushu University)
10:50 – 11:30 Inken Gamrath (ZIB)
11:30 – 13:00 Lunch @ Tenten
13:00 – 13:40 Andrea Lodi (University of Bologna & IBM-Unibo Center of Excellence onMathematical Optimization)
13:50 – 14:30 Takafumi Chida (Hitachi)
14:50 – 15:30 Ryohei Yokoyama (Osaka Prefecture University)
15:40 – 16:20 Tomoshi Otsuki (Toshiba)
16:45 – 17:45 Martin Grötschel1 (ZIB)
18:30 – Banquet of IMI Colloquium

1This talk is organized as a part of IMI Colloquium and held on Lecture Room L-1, 3F

Abstracts• Katsuki Fujisawa (IMI, Kyushu University)
Title : Advanced Computing and Optimization Infrastructure for Extremely LargeScale Graphs on Post Peta-Scale Supercomputers
Abstract : In this talk, we present our ongoing research project that is supported by
the Japan Science and Technology Agency (JST), the Core Research of Evolutionary
Science and Technology (CREST). The objective of this project is to develop an advanced computing and optimization infrastructure for extremely large-scale graphs onpost peta-scale supercomputers. We explain our challenge to Graph 500 and Green
Graph 500 benchmarks that are designed to measure the performance of a computer
system for applications that require irregular memory and network access patterns.
Following its announcement in June 2010, the Graph500 list was released in November
2010. The list has been updated biannually ever since. The Graph500 benchmark measures the performance of any supercomputer performing a BFS (Breadth-First Search)in terms of traversed edges per second (TEPS). We have implemented world s firstGPU-based BFS on the TSUBAME 2.0 supercomputer at Tokyo Institute of Technology in 2012. The Green Graph 500 list collects TEPS-per-watt metrics. In ISC14,
our project team was a winner of the 8th Graph500 benchmark and 3rd Green Graph
500 benchmark. We also present our parallel implementation for large-scale SDP(SemiDefinite Programming) problem. We solved the largest SDP problem (whichhas over 2.33 million constraints), thereby creating a new world record. Our implementation also achieved 1.713 PFlops in double precision for large-scale Cholesky
factorization using 2,720 CPUs and 4,080 GPUs on the TSUBAME 2.5 supercomputer.
• Kengo Nakajima (University of Tokyo)
Title : ppOpen-HPC: Open Source Infrastructure for Development and Executionof Large-Scale Scientific Applications on Post-Peta-Scale Supercomputers with Automatic Tuning (AT)
Abstract : In this presentation, recent achievements and progress of the ”ppOpenHPC” project are overviewed. ppOpen-HPC is an open source infrastructure fordevelopment and execution of optimized and reliable simulation code on post- petascale (pp) parallel computers based on many-core architectures, and it consists ofvarious types of libraries, which cover general procedures for scientific computation.
Source code developed on a PC with a single processor is linked with these libraries,
and the parallel code generated is optimized for post-peta-scale systems. The target post-peta-scale system is the Post T2K System of the University of Tokyo andUniversity of Tsukuba based on many-core architectures, such as Intel MIC/Xeon
Phi. It will be installed in FY.2015-2016 and its peak performance is expected tobe 20-30 PFLOPS. ppOpen-HPC supports approximately 2,000 users of the supercomputer system in the University of Tokyo, enabling them to switch from homogeneous multicore clusters to a post-peta-scale system based on many-core architectures.
ppOpen-HPC is a five-year project (FY.2011-2015) supported by Japanese government(http://postpeta.jst.go.jp/en/). ppOpen-HPC includes the four components, ppOpenAPPL, ppOpen-MATH, ppOpen-AT, and ppOpen-SYS. Libraries in ppOpen-APPL,
ppOpen-MATH, and ppOpen-SYS are called from user’s programs written in Fortranand C/C++ with MPI.

In ppOpen-HPC, we are focusing on five types of discretization methods for scientificcomputing, which are FEM, FDM, FVM, BEM, and DEM. ppOpen-APPL is a set oflibraries covering various types of procedures for these five methods, such as parallel
I/O of data-sets, assembling of coeﬃcient matrix, linear-solvers with robust and scalable preconditioners, adaptive mesh refinement (AMR), and dynamic load-balancing.
Automatic tuning (AT) enables a smooth and easy shift to further development on
new/future architectures through the use of ppOpen-AT. Directive-based special AT
languages for specific procedures in scientific computing, focused on optimum memory access, are being developed. ppOpen-AT automatically and adaptively generates
optimum implementation for eﬃcient memory accesses in the processes of methods
for scientific computing in each component of ppOpen-APPL, such as explicit timemarching procedures, matrix assembling procedures, and implicit linear solvers. And
this is achieved in various environmental constraints such as the architecture of thesupercomputer system, available resources, problem size, etc. In the presentation,
an example of application of ppOpen-AT on 3D FDM code of seismic simulations(Seism3D) will be demonstrated. Moreover, recent achievements in the developmentof ppOpen-MATH/MG, which is a geometric multigrid solver in ppOpen-HPC, willbe also presented.
• Tobias Achterberg (GUROBI Optimization)
Title : Mixed integer programming with the Gurobi optimizer
Abstract : Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth ofapplications appearing to be almost unlimited.
We demonstrate the practical relevance of this technology by highlighting some commercial customer applications of the Gurobi optimizer. We give a brief overview of
the algorithms that are employed to solve mixed integer programs and point out theingredients that are most crucial to the performance of the solver. Improvements tothese components in Gurobi have helped to provide a significant speed-up in the recent years, which directly impacts the success of our customers. Finally, we give anoutlook on the upcoming Gurobi 6.0 release.
• Gerald Gamrath (ZIB)
Title : The SCIP Optimization Suite - Concepts, Developments, and Applications
Abstract : We present the SCIP Optimization Suite, a tool for modeling and solving
optimization problems. It is built around the constraint integer programming framework SCIP, which is one of the fastest MIP solvers available in source code. We startwith a discussion of the concepts of SCIP and how they allow to solve a wide range of
optimization problems including pseudo-boolean optimization, scheduling, and nonconvex MINLP. Then, we report on current developments in the SCIP Optimization
Suite and present several real-world applications in which SCIP is used. Thereby, weelaborate on how these applications and the challenges they bear push forward thedevelopment of SCIP and our research on mixed-integer programming. Hereby, we lay
the focus on a supply chain management project in which we regard instances comingfrom a wide range of applications from all kinds of industry branches which regularly
test the boundaries of our computational possibilities.

• Matteo Fischetti (University of Padova)
Title : Proximity-driven MIP heuristics, with an application to wind farm layout
optimization
Abstract : Large-Neighborhood Search heuristics for general Mixed-Integer Programs (MIPs) such as Local Branching and RINS define a neighborhood of the current incumbent by introducing invalid constraints into the MIP formulation, and use
a black-box MIP solver to optimize the restricted problem. Proximity Search (PS)is a recently-proposed alternative approach, still aimed at improving a given feasible
solution. Instead of modifying the constraints of the MIP at hand with the aim of
reducing search space, PS modifies the objective function to make the search easier. In
the talk I will briefly review the general PS paradigm. I will then apply PS to turbine
layout optimization in a wind farm context, discussing the main ingredients required
for the practical success of the approach. Computational experiments on large-scale
real-world instances will be presented.
• Emerson Escolar (Kyushu University)
Title : Optimal Cycles in Homology via Linear Programming
Abstract : The field of computational topology for data analysis has grown rapidly inrecent years. One tool is the computation of homology groups of simplicial complexes.
In particular, given a complex that models a geometric structure of interest, the homology groups give us information about its connected components, holes, voids, andso on. While homology groups encode information about the presence of these topological features, optimal cycles tighten the representatives of the homology classes,
allowing us to infer additional geometric information, such as the locations of thetopological features. We present the optimal cycles problem for homology as an integer linear optimization problem. Moreover, by a slight modification of the originalproblem, we extend it to the case where we have multiple nonhomologous cycles. We
also discuss practical motivations for the optimal cycles problem and some possible
future directions.
• Inken Gamrath (ZIB)
Title : Optimizing battery load schedules
Abstract : As the influence of renewable energy grows, also the flexible storage ofenergy gains in importance. For the consumers in a power grid, it may be advantageous to store and release energy at suitable times. One aspect in this context isthe construction of storage schedules which provide charging and discharging periods
while considering the storage and power grid properties.
In this talk, we present a model that allows for optimizing a storage schedule for thispurpose. Given predicted demand load curves for a certain future time period anddetermined energy prices, the nonlinear model provides a storage schedule. The modelaccounts for technical constraints, such as the charging and discharging losses due tophysical properties of the storage technology, as well as economical and operational
ones. Since environment parameters can change suddenly, our aim is to find goodsolutions in a short time in order to allow ad hoc reoptimization. We present a casestudy where batteries are used as storage devices, describe diﬀerent variants to copewith nonlinearities and to solve the model, compare them with respect to quality andeﬃciency, and show exemplary computations.
• Andrea Lodi (University of Bologna & IBM-Unibo Center of Excellence on Mathematical Optimization)
Title : Mathematical and organizational issues related to the scheduling of the Operating Theaters
Abstract : The high costs of health care push national and regional health services aswell as local authorities to constantly improve management performances in order toobtain more eﬃcient organization of hospitals activities and provide patients with thebest possible care. During the last decade the number of research studies that aim ateﬃciently organizing and planning surgical activities by reducing costs and keeping agood level of care has dramatically grown. A better planning and management of activities and resources directly and indirectly involved in surgical procedures can therefore
result in more eﬀective procedures, e.g., a reduction in waiting times for patients anda better overall performance of the hospital itself. We present two case studies related
to Operating Theater planning in Emilia-Romagna region. The first one is focusedon a local hospital department that has to jointly plan operating room assignment tosurgeons and patients admission by taking into consideration, for a subset of patients,
some compulsory pre-operative activities such as outpatient anaesthetist appointment
and autologous blood donation. We propose a Mixed-Integer Linear Programming
model, we test it on real data instances and we compare the results with the currently
used planning procedures. The second case study is focused on a multispecialty Operating Theater. We present an optimization model that calculates, on a weekly basis,the subset of patients in the waiting list that will be scheduled for surgery treatment
in order to: (i) comply with the regional guidelines related to maximum waiting time
per pathology, and (ii) significantly reduce the violation of time slots (overtime) andthe misuse of surgical time (under-utilization). The proposed surgical list is evaluatedin relation with the impact that the planned surgeries have on shared resources such
as Induction Room, Recovery Room, and anaesthetists and nurses staﬀ. (Joint workwith V. Agnoletti, M. Buccioli, E. Padovani, P. Tubertini)• Ryohei Yokoyama (Osaka Prefecture University)
Title : Mixed-Integer Linear Programming Approaches to Optimal Design and Operation of Distributed Energy Systems
Abstract : To reduce fossil fuel consumption and CO2 emission, several approaches
are conceived as follows: reduction in end-use energy consumption, positive use of renewable energy sources, enhancement of eﬃciencies of energy conversion and storage
equipment, and eﬃcient energy utilization by proper design and operation of energy
supply systems. Optimization can make a significant contribution to the last approach.
In this presentation, the application of optimization to the energy field will be presented. The first author has conducted research works on optimization of distributed
energy systems, and especially has adopted mixed-integer linear programming (MILP)
approaches to optimal design and operation of the systems. In the first part of thepresentation, some subjects to be taken into account in designing and operating thesystems will be described, which will be followed by some application examples ofMILP approaches to optimal design and operation. In addition, the first and second
authors have recently conducted a joint research work to solve a large-scale optimal

design problem eﬃciently. In the second part of the presentation, a MILP branch andbound method in consideration of the hierarchical relationship between design andoperation, which has been produced as a result of the joint research work, will beintroduced.
• Takafumi Chida (Hitachi)
Title : Recent Issues and Advances in Research on Supply Chain Network Design
Abstract : Economic partnership has accelerated market opening in various areas
around the world. In this global era, we have to consider wider options and establish more world-wide supply chain. The decision problem turns to be complicatedwith many options related with each other. We introduce mathematical and engineering approach for global supply chain network design. We developed the mixed
integer programming model which includes preferential tariﬀ under economic partnership agreement.
• Tomoshi Otsuki (Toshiba)
Title : Demand Response Optimization Based on Building’s Characteristics
Abstract : Toshiba has been engaged in various scheduling and optimization problems. Among them, we focus on the demand response (DR) research that targeted forelectric power supply-demand balance by cooperation between power suppliers andconsumers in this presentation. As part of this research, we are developing a clusteredbuilding energy management system (BEMS) for eﬀective and eﬃcient energy management among multiple buildings, and are now conducting Yokohama Smart CityProject (YSCP), one of the largest DR pilot projects in Japan. The clustered BEMS
is aimed at reducing the total power consumption of a group of buildings through apower demand reduction plan for the individual buildings. In the presentation, wefirst introduce the YSCP pilot project, and then show some optimization solutions
and their computer simulation results of the DR plan.
• Martin Grötschel (ZIB)
Title : Is mathematics useful?
Abstract : Calculating percentages, profit margins, areas, volumes, and other simple
computations are obviously useful. Is this all the mathematics that people encounterin daily life? Is there more mathematics contained in the products that surroundus? Do industry and commerce really need mathematics? Is the mathematics taught
at universities useful at all? Should it be?
I will address these questions in my lecture.
My view: Mathematics plays a very important role in the modern world and mathematicians have a much higher responsibility (than many of us are aware) in theworld-wide eﬀorts to solve the big challenges of our time. Mathematics is one of
the most important intellectual endeavors of mankind but is also a versatile tool tosupport whatever is done in science, technology, business, society, etc. significantly.
In my lecture I can t cover all the issues involved but will try to elucidate how a combination of application specific mathematical modeling, simulation and optimization isaﬀecting industry and business. I will demonstrate by means of many examples whereand how the mathematical methods developed in my research environment in Berlin

(TU Berlin, DFG Research Center Matheon and Zuse Institute) is already aﬀecting
our lives.