AustinLBuchanan/Location_Models

Example codes for IEM 4203/5203: shortest paths, transportation problem, k-median, k-center, set cover, facility location, max k-cover

Location Models

Example codes for facilities courses at Oklahoma State University (IEM 4203/5203). All codes are written in Python, handle graphs using NetworkX, and solve linear and integer programs using the Gurobi optimizer.

NetworkX Codes

1. NetworkX_Basics
   • Creates a directed graph in NetworkX, adds nodes, adds (weighted) edges.
   • Writes the graph to an external .json file and reads it back in.
2. NetworkX_Distances
   • Reads a directed graph from an external .json file.
   • Calculates edge-weighted distances.
   • Finds (single-source) shortest paths.
3. NetworkX_Roads
   • Calculates distances in a large undirected road network from Colorado with 1 million edges.

Gurobi Codes

1. Gurobi_Shortest_Path
   • Reads a directed graph from an external .json file.
   • Solves shortest path problem as an integer program, and then as a linear program.
2. Gurobi_Transportation_Problem
   • Solves transportation problem (for drum sets) as a linear program.
3. Gurobi_kMedian
   • Solves k-median problem as an integer program.
   • Random instance has 100 sites and 1,000 demand points in the plane.
   • Forces Gurobi to solve the LP relaxation using concurrent method.
   • Visualizes instance and solution using matplotlib.
4. Gurobi_Uncapacitated_Facility_Location
   • Solves uncapacitated facility location problem as a mixed integer program.
   • Random instance has 100 sites and 1,000 demand points in the plane.
   • Forces Gurobi to solve the LP relaxation using concurrent method.
   • Visualizes instance and solution using matplotlib.
5. Gurobi_Capacitated_Facility_Location
   • Solves capacitated facility location problem as a mixed integer program.
   • Random instance has 100 sites and 1,000 demand points in the plane.
   • Forces Gurobi to solve the LP relaxation using concurrent method.
   • Visualizes instance and solution using matplotlib.
6. Gurobi_Set_Cover
   • Solves set cover problem as an integer program.
   • Toy instance asks to locate a minimum number of ambulances to guarantee an 8-minute response time.
7. Gurobi_kCenter
   • Solves k-center problem as a mixed integer program.
   • Toy instance asks to locate 3 ambulances to minimize the worst-case response time.
8. Gurobi_Max_kCover
   • Solves max k-cover problem as an integer program.
   • Toy instance asks to locate 3 ambulances to maximize coverage within a 3-minute response time.