Contributed Session Mon.3.H 0111

Monday, 15:15 - 16:45 h, Room: H 0111

Cluster 13: Logistics, traffic, and transportation [...]

Network problems


Chair: Kwong Meng Teo



Monday, 15:15 - 15:40 h, Room: H 0111, Talk 1

Thomas Kalinowski
Scheduling arc outages in networks to maximize total flow over time

Coauthors: Natashia Boland, Hamish Waterer, Lanbo Zheng


We present a problem arising in the annual maintenance planning process for the Hunter Valley Coal Chain which has the potential to be applied in a variety of transportation network contexts. The problem consists of sending flow from a source s to a sink t in each time period 1,2, … ,T. An additional difficulty comes from the fact that some arcs in the network have associated jobs that have to be scheduled and during processing of a job the corresponding arc is not available. In the talk we discuss some complexity results (NP-hardness of the single node case, efficiently solvable special cases), a MIP model and some computational results on real world data sets.



Monday, 16:15 - 16:40 h, Room: H 0111, Talk 3

Kwong Meng Teo
Solving network flow problems with general non-separable convex costs using a two-phase gradient projection algorithm

Coauthor: Trung Hieu Tran


Network flow problems are often encountered in practical applications such as multi-commodity flows, traffic assignment and telecommunications problems. Simpler problems such as those with quadratic costs are often solved using general solvers such as CPLEX, while more realistic but difficult ones with generalized non-separable convex costs would require specialized network optimization algorithms where speed of convergence and problem size becomes challenging issues in practice. We propose a two-phase gradient projection algorithm to bridge this gap. The proposed algorithm is designed to address the weaknesses of traditional gradient projection approaches reported in the literature, including choice of step size, speed of convergence and ease of implementation. Furthermore, the algorithm has been implemented as a toolbox riding on general solvers such as CPLEX for easy adoption and to handle industrial size problems. We evaluate and compare the performance of the proposed algorithm with other approaches under common network flow scenarios such as (i) integral or continuous flows and (ii) explicit or non-explicit objective.


  In particular, Payday Loans Texas can cater to the needs of its residents. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.