Operations-Research-2

Algorithms of integer linear programming applied to TSP problem

• CPLEX
  • Exact solvers.
    • Compact solvers.
      1. Gavish Graves solver.
      2. MTZ solver.
    • Non compact solvers.
      1. Loop solver.
      2. Heuristic Loop solver.
      3. Lazy Constraint callback.
      4. Lazy Constraint callback + Heuristic callback (Patching).
      5. Generic callback.
      6. Generic callback (Patching).
  • Math-heuristic solvers.
    1. Hard Fixing.
    2. Soft fixing.
• Heuristic solvers.
  • Construction algorithm.
    1. Nearest Neighborhood.
    2. Insertion.
    3. GASP variants of previous algorithms.
  • Refinement algorithm.
    1. Greedy Refinement (2-opt).
  • Meta-heuristich algorithm.
    1. Multi-start variations (using multithreading).
    2. Hybrid Variable Neighborhood Search (VNS).
    3. Reactive Tabu Search.
    4. Simulating anealing.
    5. Genetic algorithms (using multithreading).

Report about used techniques

All the previous implemented algorithms and the used CPLEX functions are explained in the report. In the same file you can find also the explanation of tsp instances format in TSPlib dataset, used in training and test phases. In the report, there is also the explanation of Gnuplot tool, used to show results of algorithm and python programs used to keep input instances and generate performance profile of several algorithms.

Documentation

If you want to compile the documentation, you need to type on terminal:

cd TSP\TSP
doxygen Doxyfile

If you don't have doxygen program, you can install it following this link.

Authors

The project was developed by CristiFab and RaffaDNDM.