Department of Mathematics, Sungkyunkwan University, Suwon
Department of Mathematics, Sungkyunkwan University, Suwon
Department of Mathematical Sciences, KAIST
[FYI- NIMS Workshop] “Combinatorial Optimization at Work”
March 23-25, 2015
Location: CAMP Conference Room, NIMS, Daejeon
- Thorsten Koch, The Zuse Institute Berlin (ZIB), Berlin, Germany
- Robert Schwarz, The Zuse Institute Berlin (ZIB), Berlin, Germany
- Jakob Witzig, The Zuse Institute Berlin (ZIB), Berlin, Germany
March 23 Monday
- 13:30 Opening Remarks
- 14:00-15:00 Thorsten Koch, An application driven approach to OR: the ZIB perspective
- 15:30-16:30 Thorsten Koch, How to Survive Industry Projects as a Mathematician
- 16:30-17:00 Discussion
March 24 Tuesday
- 9:30-10:30 Thorsten Koch, SCIP: Past, Present, and Future
- 10:30-11:30 Robert Schwarz, Jakob Witzig, Introduction to MIP modeling with Zimpl
- Linear Programming and geometric interpretation (diet problem)
- Integer Variables
- Modeling tricks (logical constraints, absolute value, max/min)
- Tour of Zimpl features and syntax
- Examples in Zimpl “playground” (in browser)
- 13:30-15:30 Robert Schwarz, Jakob Witzig, Tour of Applications with Zimpl Exercises
- Assignment Problem
- Shortest Path
- Minimum Spanning Tree
- Steiner Tree Problem in Graphs – Minimum Cost Network Flow
- (Sparse) Binary Classification
- 16:00-17:00 Robert Schwarz, Jakob Witzig, The Traveling Salesman Problem
- Comparison of model formulations
- Separation of subtour elimination constraints
- Primal heuristics (construction, improvement)
March 25 Wednesday
- 9:30-10:30 Thorsten Koch, From Simulation to Optimization: Mixed Integer Nonlinear Programs for Gas Network Optimization
- 10:30-11:30 Robert Schwarz, Evaluating and Extending the Capacity of Gas Networks
- Model for balanced flow situations from capacity contracts
- Estimating demand from historical data
- Network expansion measures
- 13:30-14:30 Jakob Witzig, Reoptimization for MIPs
- Branch-and-Bound trees
- An application in elevator control
- 14:30 Closing remarks
Thorsten Koch, An application driven approach to OR: the ZIB perspective
What is OR, where should it be located? In the first part of the talk we will, from the perspective of the department of Optimization at the Zuse Institute Berlin (ZIB), give an overview of the network of projects and initiatives, like the Federal Ministry of Education and Research founded Research Campus Modal, the German Research Foundation founded collaborative research centre TRR 154, the Einstein Foundations Research Center Matheon, etc. ZIB is deeply networked through these initiatives with academia on the one hand and other hand has been successfully collaborating directly with industry for more than 20 years now. The goal has always been to deliver world class research on real world problems.
Thorsten Koch, How to Survive Industry Projects as a Mathematician
This talks aims at sharing the personal experience from over 10 years of successfully employing integer programming in industry projects with the audience. After numerous research-industry collaboration projects we found that there are several reoccurring topics during these projects. The problems encountered seem to be universally the same, as there are very common misunderstandings between the partners. We will try to draw some general conclusions and using the projects of the author as examples to show some common pitfalls. We will talk about acquiring projects, getting them running and how to explain the results to practitioners. Furthermore, we will try to outline what is important to make collaboration projects with industry worthwhile for both partners and what impact and repercussions they can have on a mathematical career. Finally, we will give some notes on what are required skills that could be thought to students will to follow this path.
Thorsten Koch, SCIP: Past, Present, and Future
We will give an overview on the current development of mathematical programming tools at ZIB: SCIP, Zimpl, SoPlex, UG, and GCG. This will include the history, present state of affairs and planed future developments.
Thorsten Koch, From Simulation to Optimization: Mixed Integer Nonlinear Programs for Gas Network Optimization
The FORNE projects deals with several questions regarding the planning and operation of gas transport networks. One of the central questions is whether it is possible to find a stationary state for a particular demand/supply situation given all parameters of the network. This includes discrete decisions like whether a given compressor is running at all and also continued ones like the rate of revolution of the compressor in case it is running. Traditionally, this problem is solved by use of an experienced human network planner together with a simulation tool. In this talk we report how we transformed this simulation problem into a fully automatized optimization model. A detailed account of the mathematical models and solution methods will be given. We will discuss the meaning of feasibility in this setting. Furthermore, it is possible to answer several more involved questions, which also include stochastic aspects once the above procedure is available.
CNRS, LAMSADE, Paris, France
We present a 2-approximation fpt-algorithm for the problem of deciding whether the tree-cut width is at most k: that is, given a graph G and a positive integer k, the algorithm correctly decides in time 2O(k2 log k)·n5 log n that the tree-cut width of G is strictly bigger than k, or returns a tree-cut decomposition whose width is at most 2k. Moreover, we develop the notion of nice tree-cut decompositions and show that any tree-cut decomposition can be transformed into a nice one in polynomial time. Based on this notion, we introduce a general three-stage dynamic framework for the design of FPT algorithms on nice tree-cut decompositions and apply it to several classic problems.
This talk is based on two recent works with Robert Ganian, Stefan Szeider, Sang-il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos.
FYI (Lecture Series)
College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
Markov chain. I’ll show the analysis of a Markov chain for generating a
random matching of a graph and its extension for the estimating the
number of perfect matchings of a bipartite graph.