Scientific Program: March 27th (Auditorium)

Linear Programming solvers: the state of the art

• Author: Julian Hall (University of Edinburgh)

• Abstract: As the fundamental model in optimal decision-making, and as a sub-problem when solving more general optimization problems, the requirement to solve large, sparse linear programming (LP) problems efficiently is hugely important. For all but the most specialised of problems, solutions are found using the simplex method and interior point methods. This talk will discuss the merits of these two approaches and the techniques underlying their efficient implementation, for both general and structured LP problems. A survey of software, both commercial and open-source, will also be presented.

• Materials: slides, code

A New Metric for the Analysis of the Scientific Article Citation Network

• Author: Junji Nakano (The Institute of Statistical Mathematics)

• Abstract: Citation plays an important role in the bibliometrics analysis since the introduction of the impact factors, but traditional measures focused only on the direct citations between articles. In this work, we introduce a new metric, namely Article Network Influence (ANI), to measure quantitatively the influence of an article in the whole Web of Science or its own research community. We demonstrate the use of this new metric on the analysis of article citation network in statistics research community. We identify the main differences between the new metric and several traditional measures, including the impact factor, pagerank and FWCI.

• Materials: Please send an e-mail asking for slides to Prof. Nakano.

The MODAL GasLab: Goals and state of affairs

• Author: Thorsten Koch (Zuse Institute Berlin)

• Abstract: The Research Campus MODAL brings together researchers and practitioners under one roof. Its five-year mission: to explore challenging questions in real-world applications. To seek out new methods and new solutions. This talk will explain the overall setting and give an overview and introduction to the following three presentations and set them into perspective.

Optimized Execution of Dispatching: Building the future decision support system for nationwide gas transmission system operations

• Authors: Mladen Terzic (Open Grid Europe) and Frank Klimek (Open Grid Europe)

• Abstract: Open Grid Europe (OGE) is Germanys largest gas transmission system operator (TSO). OGE operates more than 11,000 km of pipeline, transporting the equivalent of the total energy demand of Germany either into the country or passing through to the neighbors by using 17 border crossing points and over 1,100 exit points. A 24/7 operated dispatching center in Essen is controlling the network including its 27 compressor stations ensuring the security of supply.

  Due to new regulations and the emerging energy transition towards renewables, the demands on the dispatching center are increasing. Implementing a decision support system (DSS) for the operators that supports taking efficient and reliable decisions and allows early detection of critical network situations is a major endeavor that has been started five years ago and is now showing first results.

• Materials: slides

Optimal operation of macroscopic gas flow over time

• Authors: Kai Hoppmann (Zuse Institute Berlin), Felix Hennings, Thorsten Koch, and Ralf Lenz

• Abstract: Together with our project partner Open Grid Europe (OGE), in the GasLab of the research campus MODAL we have developed a prototypical "navigation system" for the dispatchers, i.e., the people who operate the gas grid. Based on a prognosis for future supplies and demands at the entries and exits, the navigation system suggests technical control measures, e.g., starting a compressor machine or routing gas along a different path, and non-technical control measures, e.g., the usage of balancing energy, in order to ensure a stable operation of the network. Our algorithmic approach, which is based on mixed-integer linear programs, can conceptually be split into two stages: The so-called network model capturing the transient aspects of gas flow while only using a highly simplified view on the compressor stations, followed by the so-called station model, which validates the results of the network model using a detailed version of the compressor stations and their surrounding network parts and finally produces the specific technical instructions shown to the dispatchers.

  In my talk, a basic version of the network model is presented. In particular, the main simplifications and assumptions that we make in order to derive a linear formulation for transient gas flows are discussed. Additionally, our simplified model for the capabilities of compressor stations is discussed. Finally, we conclude with a presentation and visualization of some computational experiments.

• Materials: slides

Controlling transient gas flow in complex pipeline intersection areas

• Authors: Felix Hennings (Zuse Institute Berlin), Lovis Anderson, Kai Hoppmann, Thorsten Koch, and Mark Turner

• Abstract: Together with our project partner Open Grid Europe (OGE), in the GasLab of the research campus MODAL we have developed a prototypical "navigation system" for the dispatchers, i.e., the people who operate the gas grid. Based on a prognosis for future supplies and demands at the entries and exits, the navigation system suggests technical control measures, e.g., starting a compressor machine or routing gas along a different path, and non-technical control measures, e.g., the usage of balancing energy, in order to ensure a stable operation of the network. Our algorithmic approach, which is based on mixed-integer linear programs, can conceptually be split into two stages: The so-called network model capturing the transient aspects of gas flow while only using a highly simplified view on the compressor stations, followed by the so-called station model, which validates the results of the network model using a detailed version of the compressor stations and their surrounding network parts and finally produces the specific technical instructions shown to the dispatchers.

  In my talk, a prototype version of the station model will be presented. This includes an overview of the general problem description containing constraints on the single network elements as well as requirements for their interaction. Furthermore, we introduce our approach for solving the problem and show some preliminary results achieved using real-world network data from our project partner.

• Materials: slides

Shunting Scheduling Method in a Railway Depot for Dealing with Changes in Operational Conditions

• Author: Yuki Maekawa (Hitachi)

• Abstract: A shunting schedule in a railroad depot consists of instructions to allocate or move train-units in the field. In my presentation, we introduce a scheduling method which can reconstruct solution in response to various changes in operational conditions. In our method, based on the mathematical model which formalizes the problem as a kind of Flexible Job Shop Scheduling Problems (FJSSP), the solution can be derived by an algorithm which uses Constraint Programming (CP) with domain-oriented heuristics. Being evaluated on some test cases, it is showed that the proposed method can find a reasonable solution in a practical time while suppressing the differences from the original schedule.

The hypernetwork simplex algorithm and railway optimization

• Author: Ralf Borndörfer (Zuse Institute Berlin)

• Abstract: Network flows is a classical area of discrete optimization with beautiful problems, which can be solved by a multitude of powerful combinatorial algorithms. Often, such models are also used for applications, in which one would like to use hypergraphic models, the reason being that no or only very few comparable algorithms are known for hypergraph problems. Of course, such problems are in general much harder and it is therefore unlikely that such methods can exist in the general case.

  However, there are applications in which hypergraphic models provide a real advantage over graphical models. One such application is railway vehicle rotation scheduling, in which hypergraphs can be used to model train composition requirements. Such problems give rise to a special type of what we call graph-based hypergraphs.

  For such hypergraphs, the fractional minimum cost hyperflow problem, that is, the LP relaxation of the vehicle rotation problem, can be solved using a generalization of the network simplex method. This gives rise to the first purely combinatorial method to solve these problems.

  The talk will explain this method as well as its modeling background.

• Materials: slides

Scientific Program: March 28th (Seminar Room 1)

Current and future projects for CPS applications with ABCI —AI Bridging Cloud Infrastructure—

• Author: Katsuki Fujisawa (Institute of Mathematics for Industry, Kyushu University and AIST-Tokyo Tech Real World Big-Data Computation Open Innovation Laboratory)

• Abstract: In this paper, we present our ongoing research project. The objective of many ongoing Research projects in high performance computing (HPC) areas is to develop an advanced computing and optimization infrastructure for industrial applications on AI Bridging Cloud Infrastructure (ABCI). ABCI is the world's first large-scale Open AI Computing Infrastructure, constructed and operated by National Institute of Advanced Industrial Science and Technology (AIST).

  In the cyber physical system (CPS), it is possible to create new industries by optimizing and simulating the real-world data in social mobility. For this reason, we are attracting significant attention from a number of industries including social infrastructure, manufacturing industry, retail industry and so on. In this talk, we briefly explain our ongoing research projects for realizing the CPS applications.

Mobility Optimization of Humans and Products on Cyber Physical System via Mathematical Programming

• Author: Nozomi Hata (Kyushu University)

• Abstract: A number of companies have tried their best to improve the efficiency of their factories. They utilize various kind of technologies, such as robotics, mathematical optimization, and so on. On the other hand, many people, including us, are now developping and implementing the Cyber Physical Systems (CPSs). CPSs enable us to analyze, to simulate, and even to optimize a part of the real world by creating its digital twin in the cyber world. In this presentation, we will apply CPSs to factories. Our focused factories have two features; first they have various types of products, and second each of them are producted not so much. Such factories needs human work in most processes. In our approaches we optimized the mobility of workers and products in progress through several mathematical optimization problems. First, we apply a scheduling problem to optimize the mobility of products. Second, we utilize a layout optimization problem to optimize the mobility of humans. These combination improves the efficiency in factories.

Construction and Evaluation of the HEV Control Algorithm using a Black-Box simulator

• Author: Nariaki Tateiwa (Kyushu University)

• Abstract: When developing a new car, we need to consider numerous powertrain candidates consisted of engines, motors, and so on. For hybrid electric vehicle systems, studies using model-based simulators have been actively conducted. In model-based development, we calculate the fuel economy of the powertrain simulator instead of evaluating the performance of the powertrain. This makes it faster and lower cost to choose the optimal powertrain out of the candidates.

  The fuel economy of the powertrain simulator is measured by traveling at a predetermined speed of about 30 minutes. In this presentation, we propose a method that obtains optimal long-term control by solving the shortest path problem with state of charge constraints after constructing a graph expressing the transition of the fuel and battery consumption. In order to have versatility for powertrain simulator, our algorithms are constructed with simulator as a black-box. We also propose a search method for vehicle control using bicubic spline interpolation without the preparation of a controller. We finally remove almost all edges from a graph by 97.2% at most through the utilization of binary integer linear programming, which enables a 3.88x speedup in obtaining the optimal vehicle control.

• Materials: slides

Unit Commitment Problem Revisited in the course of Electricity Market Reform in Japan

• Author: Takufumi Yoshida (Toshiba)

• Abstract: After full retail competition realized in 2016 in the course of electricity market reform in Japan, power generation companies need to operate their units in more economically-efficient way, e.g. utilizing daily-start-stop (DSS) operation of the thermal units, to survive in the competitive market. However, DSS makes operations more difficult and complicated, which causes trade-off between the economic efficiency and the operational feasibility.

  Toshiba developed a new power generation scheduling system for TEPCO Fuel & Power, Inc. to resolve the trade-off problem. It employs multi-stage optimization strategy to solve the large-scale and complicated unit commitment problems. In TEPCO's case, it can produce an operationally-feasible day-ahead schedule in a few minutes, the economic efficiency of which is equivalent to the fuel cost saving of as much as 0.48%.

• Materials: slides

Solving Energy System Models with GAMS on HPC platforms

• Author: Michael R. Bussieck (GAMS)

• Abstract: GAMS is a widely used platform to implement Energy System Models (ESM) like unit commitment, optimal power flow, and economic dispatch. Such models developed and maintained by (academic) research institutes, multi-national organizations, and commercial companies often evolved over time and represent sophisticated and intricate software systems. The modeled time horizon of ESMs spans decades and due to open markets for electricity these models cover bigger and bigger regions. Hence ESMs tend to push the boundaries of available computational resources. In the last three years a multidisciplinary team of researchers from ZIB/TU Berlin/JSC/HLRS/GAMS/DLR investigated ways to handle linear programming based ESMs of exceptional size in a project named BEAM-ME (http://www.beam-me-projekt.de/beam-me/EN/Home/home_node.html). We will give an overview of the various activities in this project and emphasize on challenges related to migrating GAMS based ESMs to a high-performance computing environment.

• Materials: slides

Map-Matching Algorithms using Shortest Path Algorithm on Time-Expanded Graph

• Author: Akira Tanaka (Kyushu University)

• Abstract: In recent years, the utilization of the Global Positioning System (GPS) has become more popular. We can access a large amount of vehicle tracking data, which can be used for the traffic management and the traffic congestion prediction. However, such data contains measurement errors according to the landform and vehicle system. Thus, we need to restore the pathway for a given vehicle trajectory, and this process is called map-matching. In this presentation, we propose robust map-matching algorithm based on shortest path problem on time-expanded graph. Our algorithm succeeds in obtaining a reasonable vehicle trajectory as a whole even if GPS errors sometimes occur. We evaluate it with the actual GPS data and road information in Japan. Experiments show that the proposed algorithm outperforms related work with regard to accuracy and computation time.

• Materials: slides

Demand Prediction and Repositioning Problem for Bike-Sharing System

• Author: Akihiro Yoshida (Kyushu University)

• Abstract: Bike-sharing systems have been widely spreading in the world. They provide an environment-friendly solution for the first-and-last mile problem and help bridge the gap between existing transportation modes such as subways and bus systems. The management of these systems gives rise to many optimization problems. One of the important issues is repositioning problem, which has been tackled by some researches. We expand previous researches for applying bike-sharing system which serves several types of bikes, such as electric bicycle and standard bicycle. Our algorithm is consisted of two procedures. First, we conduct the demand prediction to capture users' riding behavior. Based on the information, we solve repositioning problem formulated as Integer Programming problem. Numerical experiments are conducted by real data of Metro Bike Share in Los Angeles.

Cross-validation in sparse linear regression with piecewise continuous nonconvex penalties and its acceleration

• Author: Tomoyuki Obuchi (Tokyo Institute of Technology) and Ayaka Sakata (The Institute of Statistical Mathematics)

• Abstract: We investigate the signal reconstruction performance of sparse linear regression in the presence of noise when piecewise continuous nonconvex penalties are used. First, we present a theoretical analysis of a typical reconstruction performance, using the replica method, under the assumption that each component of the design matrix is given as an independent and identically distributed (i.i.d.) Gaussian variable. This clarifies the superiority of the SCAD and MCP estimators compared with L1 in a wide parameter range, although the nonconvex nature of the penalty tends to lead to solution multiplicity in certain regions. Second, we develop an approximate formula efficiently computing the cross-validation error without actually conducting the cross-validation, which is also applicable to the non-i.i.d. design matrices. We implement instability detection procedures, which allows the approximate formula to stand alone and resultantly enables us to draw phase diagrams for any specific dataset. Third, we propose an annealing procedure, called nonconvexity annealing, to obtain the solution path efficiently.

• Materials: slides

Fused Sparse Transition Probability Matrix Estimation

• Author: Hideitsu Hino (The Institute of Statistical Mathematics)

• Abstract: In a product market or stock market, different products or stocks compete for the same consumers or purchasers. A method to estimate the time-varying transition matrix of the product share is proposed. The method is based on the assumption that each of the observed time series of shares is a stationary distribution of the underlying Markov processes characterized by transition probability matrices. The transition probability matrices for every observation are estimated under natural assumptions. On a real-world dataset of the share of automobiles, the proposed method is shown to find intrinsic transition of shares.

Scientific Program: March 29th (Seminar Room 1)

Adaptive LP-Newton method for second-order cone optimization problem

• Authors: Takayuki Okuno (RIKEN) and Mirai Tanaka (The Institute of Statistical Mathematics and RIKEN)

• Abstract: The LP-Newton method solves the linear optimization problem (LP) by repeatedly projecting a current point onto a certain relevant polytope. In this paper, we extend the algorithmic framework of the LP-Newton method to the second-order cone optimization problem (SOCP) via a linear semi-infinite optimization problem (LSIP) reformulation of the given SOCP. In the extension, we produce a sequence by projection onto polyhedral cones constructed from LPs obtained by finitely relaxing the LSIP. We show the global convergence property of the proposed algorithm under mild assumptions, and investigate its efficiency through numerical experiments comparing the proposed approach with the primal-dual interior-point method for the SOCP.

• Materials: slides, printer-friendly version

DNN-based Branch-and-bound for the Quadratic Assignment Problem

• Authors: Koichi Fujii (NTT DATA Mathematical Systems), Yuji Shinano, and Naoki Ito

• Abstract: The quadratic assignment problems are known as having weak linear/quadratic relaxation, which leads branch-and-bound algorithm to large number of nodes. On the other hand, some techniques for better/stable relaxation of polynomial optimization are explored recently. One of the most effective technique is to solve doubly nonnegative relaxation (DNN) of polynomial optimization by the bisection and projection method, which updated the lower bound of some instances in the quadratic assignment problem benchmark QAPLIB.

  In this talk, we introduce the implementation of DNN-based branch-and-bound for quadratic assignment problems. Since we solve the dual problem of DNN relaxation, we also implement tabu search based heuristics to acquire the primal solution. The implementation works on distributed memory machines by using parallel branch-and-bound framework UG.

• Materials: slides

Implementation issues of Interior-Point Method for real-world NLP problems

• Author: Takahito Tanabe (NTT DATA Mathematical Systems)

• Abstract: From the early 1990's, we are working on the development of interior point method code (NUOPT) for general nonlinear programming models.

  On the handling of large scale nonlinear problems, little room is left for any simplification of their treatment. In a sense, this helps us determine our software design to some extent, and simultaneously forces us to deal with difficult implementation issues, like calculation of second derivatives or fast and stable factorization of large sparse indefinite matrix.

  In reality, each problems have their own specific features. To attract our users, we have to incorporate the 'trick of the trade' into our software in a manner that does not damage the generality of the code.

  In this talk, we briefly summarize the design of our software and its transition, and some important features to handle instances that arise from real world applications. And we also discuss some implementation issues of Interior-Point Method for nonlinear programming.

• Materials: slides

Aggregation Technique of Mixed Integer Rounding Cut and Cutting Plane Selection

• Author: Koichi Fujii (NTT DATA Mathematical Systems)

• Abstract: Cutting planes plays important role in branch-and-bound for mixed integer problems. In this talk, we give two topics about them.

  Mixed integer rounding cuts are one of the most important cutting plane class. Generating those cutting planes consists of three phases: aggregation, bound substitution and rounding. We introduce the modified rules for aggregation and bound substitution, which leads to strong cutting planes on some specific class of mixed integer problems.

  How to select cutting planes is also an important topic. Some features are well known for cutting planes selection. For example, the distance between the cutting plane and the relxation solution and the parallelism among cutting planes. The distance between the cutting plane and the incumbent is recently explored and implemented in the latest version of SCIP. In this talk, we introduce other technique, using multiple solutions on the optimial face, and some new techinque, using simplex information, and discuss its computational results.

• Materials: slides

Optimal Landscape Management against Spread of Disastrous Events by Integer Programming

• Author: Atsushi Yoshimoto (The Institute of Statistical Mathematics)

• Abstract: A new optimization model is proposed to capture the spatial dynamics of the spread of disastrous events by a cellular automaton model and find the optimal solution to control its spread within a 0-1 integer programming framework. The model seeks a solution by minimizing the total costs to implement treatments for preventing the spread and damage of disastrous colonization. By incorporating a cellular automaton model governed by state- and distance-dependent probability rule of colonization into a 0-1 integer programming model, we evaluate and compare an optimal allocation of treatments on colonized and uncolonized areas. With a hypothetical stylized map, our experiments show that treatments on colonized cells are effective when implemented at the front line of the disastrous events, while treatments on uncolonized areas are conducted with some distance or buffer zone away from the front line. These buffer zones are likely to be colonized regardless of treatment. When the annual budget limit exists, treatments on colonized cells are implemented first. With heterogeneity in the disastrous spread dynamics, the proposed optimization model provides an optimal allocation of treatments much different from the solution with homogeneous environment. However, treatments at the front line of the disastrous events are always recommended.

A Model for Scheduling High-Cadence Telescope Observations

• Authors: João Pedro Pedroso (Universidade do Porto), Shiro Ikeda, Tomoki Morokuma, and Shigeyuki Sako

• Abstract: In this talk we present a mathematical model for maximizing the number of observations made during a night with a telescope. The aim is to have selected sky locations photographed as many times as possible, taking into account constraints on the interval between successive observations of the same location and the time required for moving from one telescope position to the next.

• Materials: slides

Smooth Constraint Convex Minimization via Conditional Gradients

• Author: Sebastian Pokutta (Georgia Institute of Technology)

• Abstract: Conditional Gradients (aka Frank-Wolfe Methods) are an important class of algorithms for smooth constraint convex minimization, in particular when projection onto the feasible region is non-trivial or sparse representation of iterates via extreme points is desired. Due to their simplicity, conditional gradient methods have become the methods of choice for many applications despite often suboptimal theoretical convergence rates. In fact, often the empirically observed rates are significantly better than the worst-case rates and recent refinements of the basic conditional gradients methods achieve, e.g., linear convergence in the strongly convex case or allow for variance-reduced stochastic variants. In this talk I will discuss some of these recent developments and discuss further extensions as well as open problems.

• Materials: slides