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(n³) , paper
    • Primal-Dual Nonnegative Least Squares algorithm (PDNNLS) == Dijkstra's method, for nonnegative arc lengths, paper
    • All Pairs Shortest Path (APSP) algorithm, O(n³), manuscript
    • Computational Experiments on MPSP algorithms, manuscript
  • Maximum Flows:
    • DPNNLS algorithm, solve the max-flow by Kirchhoff's laws, O(m⁵n) , manuscript
    • Augment flows proportionally, O(mn²), manuscript
  • Min-cost flows:
    • premultiplier network simplex algorithm (my master thesis)
  • Multicommodity Network Flows: (my ph.d. thesis)
    • comprehensive survey
    • primal-dual column generation method
  • Minimum Distribution Cost Problem: (Distillation, D-node)
    • shortest path, UMDCP₁, UMDCP₂, UMDCP₃ , 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