Traveling Salesman Problem with Draft Limits (TSPDL)

# Copyright (c) Hexaly. Permission is hereby granted to use, copy,
# and modify this code for applications developed with Hexaly.
import hexaly.optimizer
import sys

if len(sys.argv) < 2:
    print("Usage: python tspdl.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 == "N:":
            nb_cities = int(next(file_it))
        if pch == "Distance:[":
            # Distance from i to j
            dist_matrix_data = [[int(next(file_it)) for i in range(nb_cities)]
                                for j in range(nb_cities)]
        if pch == "Demand:":
            next(file_it)
            # Vector representing the demand in terms of weight for each city
            item_weight_data = [int(next(file_it)) for i in range(nb_cities)]
            # Initial weight of the vehicle transporting all the items to be delivered
            total_weight = sum(item_weight_data)
        if pch == "Draft:":
            next(file_it)
            break

    # Vector used to store the weight (draft) limit for each city
    weight_limit_data = [int(next(file_it)) for i 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 Hexaly arrays for all vector data in order to be able to access them with "at" operator.
    dist_matrix = model.array(dist_matrix_data)
    item_weight = model.array(item_weight_data)
    weight_limit = model.array(weight_limit_data)

    # Compute the weight of the vehicle along the tour
    weight_lambda = model.lambda_function(lambda i, prev:
                                          model.iif(i == 0, total_weight, prev - item_weight[cities[i-1]]))
    weight = model.array(model.range(0, nb_cities), weight_lambda, 0)

    # At each step, the vehicle's weight must not exceed the weight limit allowed for the city.
    # N.B: Setting a constraint over all terms of an array is done with the 'and' operator:
    weight_constraint_lambda = model.lambda_function(lambda i:
                                                     weight[i] <= weight_limit[cities[i]])
    model.constraint(model.and_(model.range(0, nb_cities), weight_constraint_lambda))

    # 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")

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <string.h>
#include <vector>

using namespace hexaly;
using namespace std;

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

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

    // Vector representing the demand in terms of weight for each city
    vector<int> itemWeightData;

    // Vector used to store the weight (draft) limit for each city
    vector<int> weightLimitData;

    // Initial weight of the vehicle transporting all the items to be delivered
    int totalWeight;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression cities;

    // Objective
    HxExpression obj;

    /* Read instance data */
    void readInstance(const string& fileName) {
        std::ifstream infile;
        infile.exceptions(std::ifstream::failbit | std::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, "N") == 0) {
                getline(infile, str);
                line = strdup(str.c_str());
                pch = strtok(NULL, ":");
                nbCities = atoi(pch);
            } else if (strcmp(pch, "Distance") == 0) {
                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];
                    }
                }
            } else if (strcmp(pch, "Demand") == 0) {
                itemWeightData.resize(nbCities);
                totalWeight = 0;
                for (int i = 0; i < nbCities; ++i) {
                    infile >> itemWeightData[i];
                    totalWeight += itemWeightData[i];
                }
            } else if (strcmp(pch, "Draft") == 0) {
                break;
            }
        }

        weightLimitData.resize(nbCities);
        for (int i = 0; i < nbCities; ++i) {
            infile >> weightLimitData[i];
        }
    }

    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 Hexaly arrays for all vector data in order to be able to access them with "at" operator.
        HxExpression distMatrix = model.array();
        HxExpression itemWeight = model.array(itemWeightData.begin(), itemWeightData.end());
        HxExpression weightLimit = model.array(weightLimitData.begin(), weightLimitData.end());

        for (int i = 0; i < nbCities; ++i) {
            HxExpression row = model.array(distMatrixData[i].begin(), distMatrixData[i].end());
            distMatrix.addOperand(row);
        }

        HxExpression weightLambda = model.createLambdaFunction([&](HxExpression i, HxExpression prev) {
                return model.iif(
                        model.eq(i, 0),
                        totalWeight,
                        model.sub(prev, model.at(itemWeight, model.at(cities, model.sub(i, 1))))); });
        HxExpression weight = model.array(model.range(0, nbCities), weightLambda, 0);

        // At each step, the vehicle's weight must not exceed the weight limit allowed for the city.
        // N.B: Setting a constraint over all terms of an array is done with the 'and' operator:
        HxExpression weightConstraintLambda = model.createLambdaFunction([&](HxExpression i) {
                return model.leq(model.at(weight, i), model.at(weightLimit, model.at(cities, i))); });
        model.constraint(model.and_(model.range(0, nbCities), weightConstraintLambda));

        // 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: tspdl 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 {
        Tspdl 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;
    }
}

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
using System;
using System.IO;
using Hexaly.Optimizer;

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

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

    // Vector representing the demand in terms of weight for each city
    long[] itemWeightData;

    // Vector used to store the weight (draft) limit for each city
    long[] weightLimitData;

    // Initial weight of the vehicle transporting all the items to be delivered
    long totalWeight;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression cities;

    // Objective
    HxExpression obj;

    public Tspdl()
    {
        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;
            string[] matrixLine;
            while ((line = input.ReadLine()) != null)
            {
                string[] splitted = line.Split(':');
                if (splitted[0].Equals("N"))
                {
                    nbCities = int.Parse(splitted[1]);
                }
                else if (splitted[0].Equals("Distance"))
                {
                    distMatrixData = new long[nbCities][];
                    for (int i = 0; i < nbCities; ++i)
                    {
                        matrixLine = input
                                .ReadLine()
                                .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
                        distMatrixData[i] = new long[nbCities];
                        for (int j = 0; j < nbCities; ++j)
                        {
                            distMatrixData[i][j] = long.Parse(matrixLine[j]);
                        }
                    }
                }
                else if (splitted[0].Equals("Demand"))
                {
                    matrixLine = input.ReadLine()
                            .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
                    itemWeightData = new long[nbCities];
                    totalWeight = 0;
                    for (int i = 0; i < nbCities; ++i)
                    {
                        itemWeightData[i] = long.Parse(matrixLine[i]);
                        totalWeight += itemWeightData[i];
                    }
                }
                else if (splitted[0].Equals("Draft"))
                {
                    break;
                }
            }

            matrixLine = input.ReadLine()
                    .Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
            weightLimitData = new long[nbCities];
            for (int i = 0; i < nbCities; ++i)
            {
                weightLimitData[i] = long.Parse(matrixLine[i]);
            }
        }
    }

    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 Hexaly arrays for all vector data in order to be able to access them with "at" operator.
        HxExpression distMatrix = model.Array(distMatrixData);
        HxExpression itemWeight = model.Array(itemWeightData);
        HxExpression weightLimit = model.Array(weightLimitData);

        // Compute the weight of the vehicle along the tour
        HxExpression weightLambda = model.LambdaFunction((i, prev) => model.If(
                model.Eq(i, 0),
                totalWeight,
                model.Sub(prev, model.At(itemWeight, model.At(cities, model.Sub(i, 1))))));
        HxExpression weight = model.Array(model.Range(0, nbCities), weightLambda, 0);

        // At each step, the vehicle's weight must not exceed the weight limit allowed for the city.
        // N.B: Setting a constraint over all terms of an array is done with the 'and' operator:
        HxExpression weightConstraintLambda = model.LambdaFunction(i =>
                model.Leq(model.At(weight, i), model.At(weightLimit, model.At(cities, i))));
        model.Constraint(model.And(model.Range(0, nbCities), weightConstraintLambda));

        // 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: Tspdl 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 (Tspdl model = new Tspdl())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

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

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

    // Vector representing the demand in terms of weight for each city
    private long[] itemWeightData;

    // Vector used to store the weight (draft) limit for each city
    private long[] weightLimitData;

    // Initial weight of the vehicle transporting all the items to be delivered
    private long totalWeight;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Decision variables
    private HxExpression cities;

    // Objective
    private HxExpression obj;

    private Tspdl(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
            input.useLocale(Locale.ROOT);
            String str = new String();
            String[] pch = new String[2];
            int i = 0;
            while (true) {
                str = input.nextLine();
                pch = str.split(":");
                if (pch[0].compareTo("N") == 0) {
                    nbCities = Integer.parseInt(pch[1].trim());
                } else if (pch[0].compareTo("Distance") == 0) {
                    distMatrixData = new long[nbCities][nbCities];
                    for (i = 0; i < nbCities; ++i) {
                        for (int j = 0; j < nbCities; ++j) {
                            distMatrixData[i][j] = input.nextInt();
                        }
                    }
                } else if (pch[0].compareTo("Demand") == 0) {
                    itemWeightData = new long[nbCities];
                    totalWeight = 0;
                    for (i = 0; i < nbCities; ++i) {
                        itemWeightData[i] = input.nextInt();
                        totalWeight += itemWeightData[i];
                    }
                } else if (pch[0].compareTo("Draft") == 0) {
                    break;
                }

            }

            weightLimitData = new long[nbCities];
            for (i = 0; i < nbCities; ++i) {
                weightLimitData[i] = 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 Hexaly arrays for all vector data in order to be able to access them with "at" operator.
        HxExpression distMatrix = model.array(distMatrixData);
        HxExpression itemWeight = model.array(itemWeightData);
        HxExpression weightLimit = model.array(weightLimitData);

        // Compute the weight of the vehicle along the tour
        HxExpression weightLambda = model.lambdaFunction((i, prev) -> model.iif(
                model.eq(i, 0),
                totalWeight,
                model.sub(prev, model.at(itemWeight, model.at(cities, model.sub(i, 1))))));
        HxExpression weight = model.array(model.range(0, nbCities), weightLambda, 0);

        // At each step, the vehicle's weight must not exceed the weight limit allowed for the city.
        // N.B: Setting a constraint over all terms of an array is done with the 'and' operator:
        HxExpression weightConstraintLambda = model.lambdaFunction(i ->
                model.leq(model.at(weight, i), model.at(weightLimit, model.at(cities, i))));
        model.constraint(model.and(model.range(0, nbCities), weightConstraintLambda));

        // 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 Tspdl 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()) {
            Tspdl model = new Tspdl(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);
        }
    }
}