Traveling Salesman Problem (TSP)

import hexaly.optimizer
import sys

if len(sys.argv) < 2:
    print("Usage: python tsp.py inputFile [outputFile] [timeLimit]")
    sys.exit(1)


def read_elem(filename):
    with open(filename) as f:
        return [str(elem) for elem in f.read().split()]


with hexaly.optimizer.HexalyOptimizer() as optimizer:
    #
    # Read instance data
    #
    file_it = iter(read_elem(sys.argv[1]))

    # The input files follow the TSPLib "explicit" format
    for pch in file_it:
        if pch == "DIMENSION:":
            nb_cities = int(next(file_it))
        if pch == "EDGE_WEIGHT_SECTION":
            break

    # Distance from i to j
    dist_matrix_data = [[int(next(file_it)) for i in range(nb_cities)]
                        for j in range(nb_cities)]

    #
    # Declare the optimization model
    #
    model = optimizer.model

    # A list variable: cities[i] is the index of the ith city in the tour
    cities = model.list(nb_cities)

    # All cities must be visited
    model.constraint(model.count(cities) == nb_cities)

    # Create an Hexaly array for the distance matrix in order to be able
    # to access it with "at" operators
    dist_matrix = model.array(dist_matrix_data)

    # Minimize the total distance
    dist_lambda = model.lambda_function(lambda i:
                                        model.at(dist_matrix, cities[i - 1], cities[i]))
    obj = model.sum(model.range(1, nb_cities), dist_lambda) \
        + model.at(dist_matrix, cities[nb_cities - 1], cities[0])
    model.minimize(obj)

    model.close()

    # Parameterize the optimizer
    if len(sys.argv) >= 4:
        optimizer.param.time_limit = int(sys.argv[3])
    else:
        optimizer.param.time_limit = 5

    optimizer.solve()

    #
    # Write the solution in a file
    #
    if len(sys.argv) >= 3:
        # Write the solution in a file
        with open(sys.argv[2], 'w') as f:
            f.write("%d\n" % obj.value)
            for c in cities.value:
                f.write("%d " % c)
            f.write("\n")

#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <string.h>
#include <vector>

using namespace hexaly;
using namespace std;

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

    // Vector of distance between two cities
    vector<vector<int>> distMatrixData;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression cities;

    // Objective
    HxExpression obj;

    /* Read instance data */
    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        infile.open(fileName.c_str());

        // The input files follow the TSPLib "explicit" format
        string str;
        char* pch;
        char* line;

        while (true) {
            getline(infile, str);
            line = strdup(str.c_str());
            pch = strtok(line, " :");
            if (strcmp(pch, "DIMENSION") == 0) {
                getline(infile, str);
                line = strdup(str.c_str());
                pch = strtok(NULL, " :");
                nbCities = atoi(pch);
            } else if (strcmp(pch, "EDGE_WEIGHT_SECTION") == 0) {
                break;
            }
        }

        // Distance from i to j
        distMatrixData.resize(nbCities);
        for (int i = 0; i < nbCities; ++i) {
            distMatrixData[i].resize(nbCities);
            for (int j = 0; j < nbCities; ++j) {
                infile >> distMatrixData[i][j];
            }
        }
    }

    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.count(cities) == nbCities);

        // Create an Hexaly array in order to be able to access it with "at" operators
        HxExpression distMatrix = model.array();
        for (int i = 0; i < nbCities; ++i) {
            HxExpression row = model.array(distMatrixData[i].begin(), distMatrixData[i].end());
            distMatrix.addOperand(row);
        }

        // Minimize the total distance
        HxExpression distLambda =
            model.createLambdaFunction([&](HxExpression i) { return model.at(distMatrix, cities[i - 1], cities[i]); });
        obj = model.sum(model.range(1, nbCities), distLambda) + model.at(distMatrix, cities[nbCities - 1], cities[0]);

        model.minimize(obj);

        model.close();

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

        optimizer.solve();
    }

    /* Write the solution in a file */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << obj.getValue() << endl;
        HxCollection citiesCollection = cities.getCollectionValue();
        for (int i = 0; i < nbCities; ++i) {
            outfile << citiesCollection[i] << " ";
        }
        outfile << endl;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: tsp inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }

    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "5";
    try {
        Tsp model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const exception& e) {
        cerr << "An error occurred: " << e.what() << endl;
        return 1;
    }
}

using System;
using System.IO;
using Hexaly.Optimizer;

public class Tsp : IDisposable
{
    // Number of cities
    int nbCities;

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

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression cities;

    // Objective
    HxExpression obj;

    public Tsp()
    {
        optimizer = new HexalyOptimizer();
    }

    // Read instance data
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            // The input files follow the TSPLib "explicit" format
            string line;
            while ((line = input.ReadLine()) != null)
            {
                string[] splitted = line.Split(':');
                if (splitted[0].Contains("DIMENSION"))
                    nbCities = int.Parse(splitted[1]);
                else if (splitted[0].Contains("EDGE_WEIGHT_SECTION"))
                    break;
            }

            string[] matrixText = input
                .ReadToEnd()
                .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
            distMatrixData = new long[nbCities][];
            for (int i = 0; i < nbCities; ++i)
            {
                distMatrixData[i] = new long[nbCities];
                for (int j = 0; j < nbCities; ++j)
                    distMatrixData[i][j] = long.Parse(matrixText[i * nbCities + j]);
            }
        }
    }

    public void Dispose()
    {
        if (optimizer != null)
            optimizer.Dispose();
    }

    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.List(nbCities);

        // All cities must be visited
        model.Constraint(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 => distMatrix[cities[i - 1], cities[i]]);
        obj = model.Sum(model.Range(1, nbCities), distLambda) + distMatrix[cities[nbCities - 1], 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)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(obj.GetValue());
            HxCollection citiesCollection = cities.GetCollectionValue();
            for (int i = 0; i < nbCities; ++i)
                output.Write(citiesCollection.Get(i) + " ");
            output.WriteLine();
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Tsp inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "30";

        using (Tsp model = new Tsp())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}

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);
        }
    }
}