Case study background and problem formulations
Instructions for optimization with PSG Run-File, PSG MATLAB Toolbox, PSG MATLAB Subroutines and PSG R.
PROBLEM1: problem_TSP
Minimize Linear(TSP) (solve plain TSP)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–
Minimize Linear(TSP) (solve plain TSP)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset1 | 2304 | – | 10628.0 | 8.34 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data | |||||
R | R Code | Data |
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset2 | 2704 | – | 7542.0 | 0.23 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data | |||||
R | R Code | Data |
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset3 | 16129 | – | 118282.0 | 375.73 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data |
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset4 | 22500 | – | 6528.0 | 713.46 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data |
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset5 | 64 | – | 95.0 | 0.02 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data |
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset6 | 38025 | – | 2323.0 | 419.77 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data |
PROBLEM2: problem_MAX_TSP
Maximize Linear(TSP) (find tour in a graph with maximal weight)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–
Maximize Linear(TSP) (find tour in a graph with maximal weight)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset | 64 | – | 281.0 | 0.05 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data | |||||
R | R Code | Data |
PROBLEM3: problem_TSP_with_budget
Minimize Linear(TSP) (minimize length of tour)
subject to
Linear ≤ Const (constraint on budget allocated for “building roads”)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–
Minimize Linear(TSP) (minimize length of tour)
subject to
Linear ≤ Const (constraint on budget allocated for “building roads”)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset | 64 | – | 194.0 | 0.03 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data | |||||
R | R Code | Data |
PROBLEM4: problem_TSP_in_constraint
Minimize Linear (minimize budget allocated for “building roads”)
subject to
Linear(TSP) ≤ Const (constraint on the length of tour)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–
Minimize Linear (minimize budget allocated for “building roads”)
subject to
Linear(TSP) ≤ Const (constraint on the length of tour)
——————————————————————–————————————–
TSP = Travelling Salesman Problem
——————————————————————–————————————–
# of Variables | # of Scenarios | Objective Value | Solving Time, PC 3.14GHz (sec) | ||||
Dataset | 64 | – | 1151.0 | 0.03 | |||
---|---|---|---|---|---|---|---|
Environments | |||||||
Run-File | Problem Statement | Data | Solution | ||||
Matlab Toolbox | Data | ||||||
Matlab Subroutines | Matlab Code | Data | |||||
R | R Code | Data |
CASE STUDY SUMMARY
This case study solves several Travelling Salesman Problems (TSPs). PSG has TSP operator for a compact formulation of problems. The length of the path which goes through all vertices of the graph is calculated with the operator “linear(TSP(matrix_of_distances))”.
TSP optimization problems can be solved only if Gurobi package is installed at the computer. PSG is using Gurobi-based solvers CarGrb or VanGrb for solving problems with TSP operator.
Problems were solved with data downloaded from the link [1].
This case study solves several Travelling Salesman Problems (TSPs). PSG has TSP operator for a compact formulation of problems. The length of the path which goes through all vertices of the graph is calculated with the operator “linear(TSP(matrix_of_distances))”.
TSP optimization problems can be solved only if Gurobi package is installed at the computer. PSG is using Gurobi-based solvers CarGrb or VanGrb for solving problems with TSP operator.
Problems were solved with data downloaded from the link [1].
References
[1] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.