KAIST Discrete Math Seminar

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

  • Andreas Holmsen, Topological methods in matching theory
    Topological methods in matching theory
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2015/4/7 Tue 4PM-5PM
    Around 15 years ago, Aharoni and Haxell gave a wonderful generalization of Hall’s marriage theorem. Their proof introduced topological methods in matching theory which were further developed by Berger, Meshulam, and others. Recently, motivated by some geometric questions, we extended these methods further, and in this talk I’ll explain the ideas and some of our results.
    Tags:

  • [NIMS Workshop] “Combinatorial Optimization at Work”

    [FYI- NIMS Workshop]  “Combinatorial Optimization at Work”

    March 23-25, 2015

    Location: CAMP Conference Room, NIMS, Daejeon

    Speakers:

    Schedule:

    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
      • Sudoku
      • 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

    Abstracts

    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.

    Tags:

  • Eun Jung Kim, Tree-cut width: computation and algorithmic applications
    Tree-cut width: computation and algorithmic applications
    Eun Jung Kim
    CNRS, LAMSADE, Paris, France
    2015/3/17 Tue 4PM-5PM
    Wollan has recently introduced the graph parameter tree-cut width, which plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems which are not believed to be fixed-parameter tractable (FPT) when parameterized by treewidth.
    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.
    Tags:

  • [Lecture Series] Eric Vigoda, Approximating the Permanent

    FYI (Lecture Series)

    Approximating the Permanent
    Eric Vigoda
    College of Computing, Georgia Institute of Technology, Atlanta, GA, USA
    2015/3/11 Wed 9AM-10:15AM (E3-1, Room 1501)
    I’ll explain the canonical paths method for bounding the mixing time of a
    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.
    Tags:

Monthly Archives