optimizationconstraintstraveling-salesmanminizinc

MiniZinc: Getting two outputs for an optimal path in a simple TSP model


I am a student starting with the basics of optimization. Basically when I run my TSP model in MiniZinc (IDE 2.8.5, Gecode 6.3.0), I got two "optimal" paths, but it should be only one, right?

include "alldifferent.mzn";

enum Cidades = {A, B, C, D, E, F, G};

int: n = card(Cidades);  % Number of cities

array[Cidades, Cidades] of int: dist = 
  array2d(Cidades, Cidades, 
    [0, 133, 400, 300, 500, 600, 300,
     133, 0, 300, 200, 400, 500, 200,
     400, 300, 0, 100, 200, 300, 200,
     300, 200, 100, 0, 200, 300, 100,
     500, 400, 200, 200, 0, 100, 300,
     600, 500, 300, 300, 100, 0, 400,
     300, 200, 200, 100, 300, 400, 0]);

var Cidades: start_city = A;  
array[1..n+1] of var Cidades: tour;  % n+1 to include the travel back to start city

% Restrições
constraint alldifferent([tour[i] | i in 1..n]);
constraint tour[1] == start_city;
constraint tour[n+1] == start_city;  % back to start city

var int: total_distance = sum(i in 1..n) (dist[tour[i], tour[i+1]]);

solve minimize total_distance;

output ["Distância total: \(total_distance) km\n"] ++
       ["Caminho: \(tour)\n"];

I was expecting to have only one output with the optimal minimal total distance. I got this:



Running tsp_1.mzn
395msec

Distância total: 1533 km
Caminho: [A, G, F, E, D, C, B, A]
----------
Distância total: 1433 km
Caminho: [A, G, D, E, F, C, B, A]
----------
==========
Finished in 395msec.

Solution

  • It is actually a single optimal solution, the last solution. The first one is an intermediate solution and - IMHO - great to see the progress of the solver when running larger problem instances.

    If you are using the MiniZincIDE, then you can set it to just show the final solution by the following:

    If you are running MiniZinc using the command line, then the option -a should not be used (since it shows the intermediate solutions).