Traveling Salesman (TSP)¶

import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class Tsp {
    // Number of cities
    private int nbCities;

    // Vector of distance between two cities
    private long[][] distMatrixData;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Decision variables
    private HxExpression cities;

    // Objective
    private HxExpression obj;

    private Tsp(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            // The input files follow the TSPLib "explicit" format
            String str = new String();
            String[] pch = new String[2];
            int i = 0;
            while (true) {
                str = input.nextLine();
                pch = str.split(":");
                if (pch[0].compareTo("DIMENSION") == 0) {
                    nbCities = Integer.parseInt(pch[1].trim());
                    System.out.println("Number of cities = " + nbCities);
                } else if (pch[0].compareTo("EDGE_WEIGHT_SECTION") == 0) {
                    break;
                }
            }

            // Distance from i to j
            distMatrixData = new long[nbCities][nbCities];
            for (i = 0; i < nbCities; ++i) {
                for (int j = 0; j < nbCities; ++j) {
                    distMatrixData[i][j] = input.nextInt();
                }
            }
        }
    }

    private void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // A list variable: cities[i] is the index of the ith city in the tour
        cities = model.listVar(nbCities);

        // All cities must be visited
        model.constraint(model.eq(model.count(cities), nbCities));

        // Create a HexalyOptimizer array for the distance matrix in order to be able to
        // access it with "at" operators
        HxExpression distMatrix = model.array(distMatrixData);

        // Minimize the total distance
        HxExpression distLambda = model
            .lambdaFunction(i -> model.at(distMatrix, model.at(cities, model.sub(i, 1)), model.at(cities, i)));
        obj = model.sum(model.sum(model.range(1, nbCities), distLambda),
            model.at(distMatrix, model.at(cities, nbCities - 1), model.at(cities, 0)));

        model.minimize(obj);
        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(limit);

        optimizer.solve();
    }

    /* Write the solution in a file */
    void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(new FileWriter(fileName))) {
            output.println(obj.getValue());
            HxCollection citiesCollection = cities.getCollectionValue();
            for (int i = 0; i < nbCities; ++i) {
                output.print(citiesCollection.get(i) + " ");
            }
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java Tsp inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "5";

        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            Tsp model = new Tsp(optimizer);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}