Home Research Publications Team Courses Resources

I am interested in solving optimization problems, developing efficient and effective algorithms to solve easy/difficult/fundamental/challenging optimization problems. In general, problems that are easy/fundamental in fact are also "difficult" or "challenging" since it will take much more efforts to have some new breakthroughs or contributions. (Yet I am still enjoying doing it, that's why I have done something in shortest paths and max-flows.)

The research topics I have done, been doing, or will do cover the following applications & techniques: [red color denotes on-going research topics; * denotes potetional topics but not starting yet]

• Network optimization
• Shortest Path: (my ph.d. thesis)
• Multiple Pairs Shortest Path (MPSP) algorithms, O(n3) , paper
• Primal-Dual Nonnegative Least Squares algorithm (PDNNLS) == Dijkstra's method, for nonnegative arc lengths, paper
• All Pairs Shortest Path (APSP) algorithm, O(n3), manuscript
• Computational Experiments on MPSP algorithms, manuscript
• Maximum Flows:
• DPNNLS algorithm, solve the max-flow by Kirchhoff's laws, O(m5n) , manuscript
• Augment flows proportionally, O(mn2), manuscript
• Min-cost flows:
• Multicommodity Network Flows: (my ph.d. thesis)
• comprehensive survey
• primal-dual column generation method
• Minimum Distribution Cost Problem: (Distillation, D-node)
• shortest path, UMDCP1, UMDCP2, UMDCP3 , paper
• max-flow & generator
• min-cost network simplex method, detailed graphical operations, paper
• Logistics, Supply Chain Management
• Reverse Logistics Network Design
• facility location with different configurations; greedy heuristics, paper
• Metropolitan Motorcycle Courier Systems
• Monopoly performance estimation, paper
• Cournot game, 2 competitors, 4 scenarios (HS, PP) manuscript
• determine the most profitable HQ/LQ service percentages
• new network models without hub
• Public Bicycle Sharing Systems
• site location selection
• bike transshipment management to satisfy demand
• bike transshipment management considering advertisement exposure
• persistency model in site location (a QIP)
• dynamic bike repositioning based on proportional demands
• simulations for evaluating info sharing
• temporary manpower allocation vs. self bike repositioning
• simulation optimization on several important decisions
• E-scooter sharing systems
• Bioinformatics
• Haplotype Inference manuscript
• compatible relation, merged genotype pairs (MGP)
• greedy selection with Clark's rule
• TagSNP Selection
• bi-objective mathematical programming to select tagSNPs with larger LD values
• Lagrangian Relaxation heuristics
• IP model to select robust tagSNPs for capacitated bio-chips
• Personal Navigation System
• Quickest Itinerary Planning without Timetable thesis
• modeled as a constrained shortest path problem, given max # transfers
• LR, KSP, preprocessing
• Quickest Itinerary Planning with Timetable
• without transfer upper bounds, with/without Walk
• shortest path on an acyclic graph, topological ordering algorithm with BFS/DFS speed-up techniques
• Minimum Fare Itinerary Planning without Timetable
• shortest path on a complete graph, Dijkstra's algorithm with BFS/DFS speed-up techniques
• models for special cases such as one free transfer after MRT, or "2-stage" bus routing in a single trip
• Optimal Biking Routes with a Target Range of Calorie Consumption
• Optimal Euler Subgraphs of bounded lengths
• Network Reliability
• Reliability for Multi-state Capacitated Manufacturing Networks with Distillation Process manuscript
• a compaction preprocessing scheme
• algorithms to calculate the reliability (difficulty: fractional flow, flow dependency)
• min-cost network design with given reliability lower bound
• *Approximation algorithm for calculating reliability
• Semiconductor Manufacturing
• 1-stage Complex Job-Shop Scheduling with recipe, release time, due date, and setup time consideration manuscript
• MIP formulation, problem decomposition (into single stages)
• greedy dispatching rule (load balance), heuristics to reduce the number of variables
• heuristics that involves more scheduling rather than dispatching
• 2-stage Complex Job-Shop Scheduling with recipe, release time, due date, and batch process (2 jobs of the same recipe) consideration
• MIP formulation, problem decomposition (into single stages)
• greedy dispatching rule (FIFO)
• heuristics that involves more scheduling rather than dispatching
• Data Mining
• Change Mining manuscript
• given possible interruption duration with probability distribution, time-window
• Project Management
• stable project baseline schedules with time constraints
• given possible interruption duration with probability distribution, time-window & time-schedule constraints, 2 greedy heuristics & GA
• project network generator
• Staff Rostering
• Designing a Nurse Rostering Information System for Site Management Organizations
• MIP formulation, greedy heuristics
• an information system to verify schedules
• Railway Staff Rostering and Re-rostering Problem
• MIP formulation, greedy heuristics
• Pavement Optimization (with Prof. Tsai in Civil Eng., GA Tech)
• Project level (detailed work plan: which treatment, when, where)
• segment clustering, give a network model, solved by topological ordering algorithm
• with reliability idea, how to make a work plan such that the road condition meets the quality requirement with min-total-cost (also integrating the network level Markovian idea)
• budget balance between working districts and political districts
• Network level
• MIP formulation, how to allocate budget
• E-learning
• Grouping for better cooperative learning
• MIP formulation that groups students for cooperative learning
• considering mutual compensation based on conceptual graph and other criteria
• Telecommunication
• Optimal wavelength assignment & routing algorithm
• *Sensor Network localization