Changhyun Kwon (권창현), Mathematical Models of Transportation Systems and Networks

June 23rd, 2016

FYI: Short Course on “Mathematical Models of Transportation Systems and Networks” organized by Dept. of Industrial and Systems Engineering, KAIST. You need to bring your laptop to learn the programming in Julia.

Mathematical Models of Transportation Systems and Networks
Changhyun Kwon (권창현)
Industrial and Management Systems Engineering, University of South Florida
2016/7/5 10am-12am, 1:30pm-3:30pm
2016/7/6 10am-12am, 1:30pm-3:30pm
(Room 1501 of Bldg. E2)
This short course covers selected topics in mathematical models arising in the analysis of transportation systems and networks. We will briefly review basic topics in network optimization and then will proceed to commonly used models for logistics service planning by private companies as well as management of public vehicular infrastructure. This course will cover topics such as risk-averse routing, vehicle routing problems, network user equilibrium, road pricing and network design, location problems, and modeling drivers’ decision making processes, with applications in bike-sharing services, electric-vehicle charging, hazardous materials transportation, and congestion mitigation. This course will also introduce some computational tools available in the Julia Language.Outline (subject to change)

1. Basic Topics in Network Optimization
– Shortest Path Problem
– Minimum Cost Network Flow
– Transportation Problem
– Multi-Commodity Network Flow
– Intro to Julia and JuMP

2. Risk-Averse Routing
– Robust Shortest Path Problem
* Scenario-based
* Interval data
* Polyhedral uncertainty set
* Two multiplicative coefficients
* Julia: RobustShortestPath.jl
– Value-at-Risk
– Conditional Value-at-Risk
– Worst-case Conditional Value-at-Risk

3. Vehicle Routing Problem
– Traveling Salesman Problem
– Subtour Elimination
– Vehicle Routing Problem
– VRP with Time Windows
– Green VRP / Electric-VRP
– Energy Minimizing VRP
– Medical-Waste Collection VRP
– Bike-Balancing VRP

4. Network User Equilibrium
– System Optimum
– User Equilibrium
* Complementarity Problem
* Variational Inequality Problem
– Computation
* Frank-Wolfe Algorithm
* Julia: VariationalInequality.jl
* Julia: Complementarity.jl
* Julia: TrafficAssignment.jl
– Stochastic User Equilibrium
– Braess Paradox
– Price of Anarchy

5. Network Regulation
– Bilevel Optimization
– Road Pricing
– Network Design
– Inverse Optimization for Road Pricing
– Single-level Reformulation
– Leader-Follower Game

6. Location Problems
– Classic Location Problems
* p-median
* p-center
* set-covering
* maximal covering
* fixed-charge facility location
* two-stage problem
– Hub Location Problems
* p-hub center
* hub-covering
* p-hub median
– Lagrangian Relaxation
– Flow-Capturing Location Problem
– Flow-Refueling Location Problem
– Infrastructure Planning for Electric Vehicles

7. Generalized Bounded Rationality
– Satisficing Behavior
– Perception-Error
– Equivalence
– Comparison with Random-Utility Model
– Monte-Carlo Method
– Julia: PathDistribution.jl
– Application in Robust Network Design

Chun-Hung Liu, Packing and covering topological minors and immersions

June 10th, 2016
Packing and covering topological minors and immersions
Chun-Hung Liu
Department of Mathematics, Princeton University, Princeton, NJ, USA
2016/06/29 Wed 4PM-5PM
A set F of graphs has the Erdős-Posa property if there exists a function f such that every graph either contains k disjoint subgraphs each isomorphic to a member in F or contains a set of at most f(k) vertices intersecting all such subgraphs. In this talk I will address the Erdős-Posa property with respect to three closely related graph containment relations: minor, topological minor, and immersion. We denote the set of graphs containing H as a minor, topological minor and immersion by M(H),T(H) and I(H), respectively. Robertson and Seymour in 1980’s proved that M(H) has the Erdős-Posa property if and only if H is planar. And they left the question for characterizing H in which T(H) has the Erdős-Posa property in the same paper. This characterization is expected to be complicated as T(H) has no Erdős-Posa property even for some tree H. In this talk, I will present joint work with Postle and Wollan for providing such a characterization. For immersions, it is more reasonable to consider an edge-variant of the Erdős-Posa property: packing edge-disjoint subgraphs and covering them by edges. I(H) has no this edge-variant of the Erdős-Posa property even for some tree H. However, I will prove that I(H) has the edge-variant of the Erdős-Posa property for every graph H if the host graphs are restricted to be 4-edge-connected. The 4-edge-connectivity cannot be replaced by the 3-edge-connectivity.

On the Erdős-Szekeres convex polygon problem

May 25th, 2016
On the Erdős-Szekeres convex polygon problem
Andreas Holmsen
Department of Mathematical Sciences, KAIST
2016/05/27 4PM (Room 2411 of Bldg E6-1)
Very recently, Andrew Suk made a major breakthrough on the Erdos-Szekeres convex polygon problem, in which he solves asymptotically this 80 year old problem of determining the minimum number of points in the plane in general position that always guarantees n points in convex position. I will review his proof in full detail.

Neil Immerman, Towards Capturing Order-Independent P

May 4th, 2016

FYI: Joint Seminar on Theoretical Computer Science

Towards Capturing Order-Independent P
Neil Immerman
College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA
2016/5/11 Wed 4PM-5PM (E3-1, Room 3445)
In Descriptive Complexity we characterize the complexity of decision problems by how rich a logical language is needed to describe the problem. Important complexity classes have natural logical characterizations, for example NP is the set of problems expressible in second order existential logic (NP = SOE) and P is the set of problems expressible in first order logic, plus a fixed point operator (P = FO(FP)).
The latter characterization is over ordered graphs, i.e. the vertex set is a linearly ordered set. This is appropriate for computational problems because all inputs to a computer are ordered sequences of bits. Any ordering will do; we are interested in the order-independent properties of graphs. The search for order-independent P is closely tied to the complexity of graph isomorphism. I will explain these concepts and the current effort to capture order-independent P.

Suil O (오수일), Interlacing families and the Hermitian spectral norm of digraphs

April 20th, 2016
Interlacing families and the Hermitian spectral norm of digraphs
Suil O (오수일)
Department of Mathematics, Simon Fraser University, Burnaby, B.C., Canada
2016/6/1 Wed 4PM-5PM
Recently, Marcus, Spielman, and Srivastava proved the existence of infinite families of bipartite Ramanujan graphs of every degree at least 3 by using the method of interlacing families of polynomials. In this talk, we apply their method to prove that for any connected graph G, there exists an orientation of G such that the spectral radius of the corresponding Hermitian adjacency matrix is at most that of the universal cover of G.