Skip to main content

Über dieses Buch

This book clearly shows the importance, usefulness, and powerfulness of current optimization technologies, in particular, mixed-integer programming and its remarkable applications. It is intended to be the definitive study of state-of-the-art optimization technologies for students, academic researchers, and non-professionals in industry. The chapters of this book are based on a collection of selected and extended papers from the “IMI Workshop on Optimization in the Real World” held in October 2014 in Japan.



Advanced Computing and Optimization Infrastructure for Extremely Large-Scale Graphs on Post Peta-Scale Supercomputers

In this paper, we present our ongoing research project. The objective of this project is to develop advanced computing and optimization infrastructures for extremely large-scale graphs on post 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. The 1st Graph500 list was released in November 2010. 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 first GPU-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 2014, 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 (which has 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.
Katsuki Fujisawa, Toyotaro Suzumura, Hitoshi Sato, Koji Ueno, Yuichiro Yasui, Keita Iwabuchi, Toshio Endo

ppOpen-HPC: Open Source Infrastructure for Development and Execution of Large-Scale Scientific Applications on Post-Peta-Scale Supercomputers with Automatic Tuning (AT)

ppOpen-HPC is an open source infrastructure for development and execution of large-scale scientific applications on post-peta-scale (pp) supercomputers with automatic tuning (AT). ppOpen-HPC focuses on parallel computers based on many-core architectures and consists of various types of libraries covering general procedures for scientific computations. The 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. In this article, recent achievements and progress of the ppOpen-HPC project are summarized.
Kengo Nakajima, Masaki Satoh, Takashi Furumura, Hiroshi Okuda, Takeshi Iwashita, Hide Sakaguchi, Takahiro Katagiri, Masaharu Matsumoto, Satoshi Ohshima, Hideyuki Jitsumoto, Takashi Arakawa, Futoshi Mori, Takeshi Kitayama, Akihiro Ida, Miki Y. Matsuo

Structure-Based Primal Heuristics for Mixed Integer Programming

Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.
Gerald Gamrath, Timo Berthold, Stefan Heinz, Michael Winkler

Optimal Turbine Allocation for Offshore and Onshore Wind Farms

Green energy became a topic of great interest in the recent years, as every year the demand for energy is increasing and the old resources, fossil fuels in particular, are pollutant and are becoming scarce. As a result, many countries have ambitious plans regarding green energy production. In particular, lots of money and energy are spent on the optimal design of wind farms, as an efficient use of the available resources is instrumental for their economical success. In the present paper we address the optimization of turbine positions, which is one of the most relevant problems in the design of a wind farm, and propose a heuristic approach based on Mixed-Integer Linear Programming techniques. Computational results on very large scale instances prove the practical viability of the approach.
Martina Fischetti, Matteo Fischetti, Michele Monaci

Optimal Cycles for Persistent Homology Via Linear Programming

In this work, we discuss the problem of finding optimal cycles for homology groups of simplicial complexes and for persistent homology of filtrations. We review the linear programming formulation of the optimal homologous cycle problem and its extension to allow for multiple cycles. By inserting these linear programming problems into the persistent homology algorithm, we are able to compute an optimal cycle, that has been optimized at birth, for every persistent interval in the persistent diagram.
Emerson G. Escolar, Yasuaki Hiraoka

Optimal Battery Control for Smart Grid Nodes

Energy storages can be of great value when added to power grids. They introduce the possibility to store and release energy whenever this is favorable. This is particularly relevant, for example, if power supply is volatile (as is the case with renewable energy) and the network is small (so that there are few other nodes that might balance fluctuations in consumption or production). We present models and methods from mathematical optimization for computing an optimized storage schedule for this purpose. We look at alternative optimization objectives, such as smallest possible peak load, lowest energy costs, or the closest approximation of a prescribed load curve. The optimization needs to respect general operational and economic constraints as well as limitations in the use of storage, which are imposed by the chosen storage technology. We therefore introduce alternative approaches for modeling the non-linear properties of energy storages and study their impact on the efficiency of the optimization process. Finally, we present a computational study with batteries as storage devices. We use this to highlight the trade-off between solution quality and computational tractability. A version of the model for the purpose of leveling peaks and instabilities has been implemented into a control system for an office-building smart grid scenario.
Andreas Draegert, Andreas Eisenblätter, Inken Gamrath, Axel Werner

Pre-operative Activities and Operating Theater Planning in Emilia-Romagna, Italy

The high costs of health care push national and regional health services as well as local authorities to constantly improve management performances in order to obtain more efficient organization of hospitals activities and provide patients with the best possible care. During the last decade the number of research studies that aim at efficiently organizing and planning surgical activities by reducing costs and keeping a good level of care has dramatically grown. We present a case-study focused on a local hospital department that has to jointly plan operating room assignment to surgeons and patients admission by taking into consideration, for a subset of patients, some compulsory pre-operative activities such as outpatient anesthetist appointment and autologous blood donation. We propose a Mixed Integer Programming model, we test it on real-world instances and we compare the results with the currently used planning procedures.
Andrea Lodi, Paolo Tubertini

Recent Issues in International Supply Chain Network Design—Economic Partnership Modeling

In this paper, we present a supply chain network design technique with a preferential tariff under an economic partnership agreement. The proposed model has constraints to judge whether a preferential tariff applies under two types of rules which identify the product origin country. This model can estimate the cost reduction amount under preferential tariff utilization, and design the minimum total cost supply chain network. We show results of some case studies of factory location selection under the assumption that applicable new tariff schemes will go into effect and labor cost will rise remarkably in the future. These results suggest two types of strategies: selecting the lowest location and selecting high-cost locations for which a preferential tariff applies. It is confirmed that the proposed model can effectively perform such a quantitative evaluation.
Junko Hosoda, Kenichi Funaki, Takafumi Chida

MILP Approaches to Optimal Design and Operation of Distributed Energy Systems

Energy field is one of the practical areas to which optimization can contribute significantly. In this chapter, the application of mixed-integer linear programming (MILP) approaches to optimal design and operation of distributed energy systems is described. First, the optimal design and operation problems are defined, and relevant previous work is reviewed. Then, an MILP method utilizing the hierarchical relationship between design and operation variables is presented. In the optimal design problem, integer variables are used to express the types, capacities, numbers, operation modes, and on/off states of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. The presented method can change the enumeration tree for the branching and bounding procedures, and can search the optimal solution very efficiently. Finally, future work in relation to this method is described.
Ryohei Yokoyama, Yuji Shinano

Demand Response Optimization Based on Building’s Characteristics

Demand response (DR) is one of the technologies that targets for power control based on the cooperation between power suppliers and consumers. In the case of buildings’ power control, it is important for buildings to achieve buildings’ power reduction target more correctly under individual buildings’ less burden. We suppose the framework of buildings’ aggregator that collects the information for power reduction (NEGAWATT information) and requests each building to reduce demand to achieve buildings’ power reduction target efficiently. In the framework, we first collect the NEGAWATT information based on buildings’ characteristics, and then we make the demand response plans (DR plans) that meet the requirements of buildings. In this paper, we focus on the DR optimization techniques based on NEGAWATT information, and show two simulation results, one of which shows the aggregation effect in a simple simulation, the other of which shows the multiple scenario methods to deal with the DR optimization under uncertainty. These simulations show that DR utilizing NEGAWATT information is more efficient for demand-supply balance than conventional DR methods.
Tomoshi Otsuki
Weitere Informationen

Premium Partner


    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.