Car Sequencing Problem

import hexaly.optimizer
import sys


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

#
# Read instance data
#


def read_instance(instance_file):
    file_it = iter(read_integers(instance_file))
    nb_positions = next(file_it)
    nb_options = next(file_it)
    nb_classes = next(file_it)
    max_cars_per_window = [next(file_it) for i in range(nb_options)]
    window_size = [next(file_it) for i in range(nb_options)]
    nb_cars = []
    options = []
    initial_sequence = []

    for c in range(nb_classes):
        next(file_it)  # Note: index of class is read but not used
        nb_cars.append(next(file_it))
        options.append([next(file_it) == 1 for i in range(nb_options)])
        [initial_sequence.append(c) for p in range(nb_cars[c])]

    return nb_positions, nb_options, max_cars_per_window, window_size, options, \
        initial_sequence


def main(instance_file, output_file, time_limit):
    nb_positions, nb_options, max_cars_per_window, window_size, options, \
        initial_sequence = read_instance(instance_file)

    with hexaly.optimizer.HexalyOptimizer() as optimizer:
        #
        # Declare the optimization model
        #
        model = optimizer.model

        # sequence[i] = j if class initially planned on position j is produced on position i
        sequence = model.list(nb_positions)

        # sequence is a permutation of the initial production plan, all indexes must
        # appear exactly once
        model.constraint(model.partition(sequence))

        # Create Hexaly arrays to be able to access them with "at" operators
        initial_array = model.array(initial_sequence)
        option_array = model.array(options)

        # Number of cars with option o in each window
        nb_cars_windows = [None] * nb_options
        for o in range(nb_options):
            nb_cars_windows[o] = [None] * nb_positions
            for j in range(nb_positions - window_size[o] + 1):
                nb_cars_windows[o][j] = model.sum()
                for k in range(window_size[o]):
                    class_at_position = initial_array[sequence[j + k]]
                    nb_cars_windows[o][j].add_operand(model.at(
                        option_array,
                        class_at_position,
                        o))

        # Number of violations of option o capacity in each window
        nb_violations_windows = [None] * nb_options
        for o in range(nb_options):
            nb_violations_windows[o] = [None] * nb_positions
            for p in range(nb_positions - window_size[o] + 1):
                nb_violations_windows[o][p] = model.max(
                    nb_cars_windows[o][p] - max_cars_per_window[o], 0)

        # Minimize the sum of violations for all options and all windows
        total_violations = model.sum(
            nb_violations_windows[o][p]
            for p in range(nb_positions - window_size[o] + 1) for o in range(nb_options))
        model.minimize(total_violations)

        model.close()

        # Set the initial solution
        sequence.get_value().clear()
        for p in range(nb_positions):
            sequence.get_value().add(p)

        # Parameterize the optimizer
        optimizer.param.time_limit = time_limit

        optimizer.solve()

        #
        # Write the solution in a file with the following format:
        # - 1st line: value of the objective;
        # - 2nd line: for each position p, index of class at positions p.
        #
        if output_file is not None:
            with open(output_file, 'w') as f:
                f.write("%d\n" % total_violations.value)
                for p in range(nb_positions):
                    f.write("%d " % initial_sequence[sequence.value[p]])

                f.write("\n")


if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Usage: python car_sequencing.py instance_file [output_file] [time_limit]")
        sys.exit(1)

    instance_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 60
    main(instance_file, output_file, time_limit)

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

using namespace hexaly;
using namespace std;

class CarSequencing {
public:
    // Number of vehicles
    int nbPositions;

    // Number of options
    int nbOptions;

    // Number of classes
    int nbClasses;

    // Options properties
    vector<int> maxCarsPerWindow;
    vector<int> windowSize;

    // Classes properties
    vector<int> nbCars;
    vector<vector<bool>> options;

    // Initial sequence
    vector<int> initialSequence;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Hexaly Program variable
    HxExpression sequence;

    // Objective
    HxExpression totalViolations;

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

        infile >> nbPositions;
        infile >> nbOptions;
        infile >> nbClasses;

        maxCarsPerWindow.resize(nbOptions);
        for (int o = 0; o < nbOptions; ++o)
            infile >> maxCarsPerWindow[o];

        windowSize.resize(nbOptions);
        for (int o = 0; o < nbOptions; ++o)
            infile >> windowSize[o];

        options.resize(nbClasses);
        nbCars.resize(nbClasses);
        initialSequence.resize(nbPositions);
        int pos = 0;
        for (int c = 0; c < nbClasses; ++c) {
            int tmp;
            infile >> tmp;  // Note: index of class is read but not used
            infile >> nbCars[c];
            options[c].resize(nbOptions);
            for (int o = 0; o < nbOptions; ++o) {
                int v;
                infile >> v;
                options[c][o] = (v == 1);
            }
            for (int p = pos; p < pos + nbCars[c]; ++p)
                initialSequence[p] = c;
            pos += nbCars[c];
        }
    }

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

        // sequence[i] = j if class initially planned on position j is produced on position i
        sequence = model.listVar(nbPositions);

        // sequence is a permutation of the initial production plan, all indexes must appear exactly once
        model.addConstraint(model.partition(sequence));

        // Create HexalyOptimizer arrays to be able to access them with "at" operators
        HxExpression initialArray = model.array(initialSequence.begin(), initialSequence.end());
        HxExpression optionArray = model.array();
        for (int c = 0; c < nbClasses; ++c) {
            HxExpression classOptions = model.array(options[c].begin(), options[c].end());
            optionArray.addOperand(classOptions);
        }

        // Number of cars with option o in each window
        vector<vector<HxExpression>> nbCarsWindows;
        nbCarsWindows.resize(nbOptions);
        for (int o = 0; o < nbOptions; ++o) {
            nbCarsWindows[o].resize(nbPositions - windowSize[o] + 1);
            for (int j = 0; j < nbPositions - windowSize[o] + 1; ++j) {
                nbCarsWindows[o][j] = model.sum();
                for (int k = 0; k < windowSize[o]; ++k) {
                    HxExpression classAtPosition = initialArray[sequence[j + k]];
                    nbCarsWindows[o][j].addOperand(model.at(optionArray, classAtPosition, o));
                }
            }
        }

        // Number of violations of option o capacity in each window
        vector<vector<HxExpression>> nbViolationsWindows;
        nbViolationsWindows.resize(nbOptions);
        for (int o = 0; o < nbOptions; ++o) {
            nbViolationsWindows[o].resize(nbPositions - windowSize[o] + 1);
            for (int j = 0; j < nbPositions - windowSize[o] + 1; ++j) {
                nbViolationsWindows[o][j] = model.max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o]);
            }
        }

        // Minimize the sum of violations for all options and all windows
        totalViolations = model.sum();
        for (int o = 0; o < nbOptions; ++o) {
            totalViolations.addOperands(nbViolationsWindows[o].begin(), nbViolationsWindows[o].end());
        }

        model.minimize(totalViolations);
        model.close();

        // Set the initial solution
        sequence.getCollectionValue().clear();
        for (int p = 0; p < nbPositions; ++p)
            sequence.getCollectionValue().add(p);

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

        optimizer.solve();
    }

    /* Write the solution in a file with the following format:
     * - 1st line: value of the objective;
     * - 2nd line: for each position p, index of class at positions p. */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << totalViolations.getValue() << endl;
        for (int p = 0; p < nbPositions; ++p) {
            outfile << initialSequence[sequence.getCollectionValue().get(p)] << " ";
        }
        outfile << endl;
    }
};

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

    const char* instanceFile = argv[1];
    const char* outputFile = argc >= 3 ? argv[2] : NULL;
    const char* strTimeLimit = argc >= 4 ? argv[3] : "60";

    try {
        CarSequencing model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (outputFile != NULL)
            model.writeSolution(outputFile);
        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 CarSequencing : IDisposable
{
    // Number of vehicles
    int nbPositions;

    // Number of options
    int nbOptions;

    // Number of classes
    int nbClasses;

    // Options properties
    int[] maxCarsPerWindow;
    int[] windowSize;

    // Classes properties
    int[] nbCars;
    int[][] options;

    // Initial sequence
    int[] initialSequence;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // LS Program variable
    HxExpression sequence;

    // Objective
    HxExpression totalViolations;

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

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            string[] splitted = input.ReadLine().Split(' ');
            nbPositions = int.Parse(splitted[0]);
            nbOptions = int.Parse(splitted[1]);
            nbClasses = int.Parse(splitted[2]);

            splitted = input.ReadLine().Split(' ');

            maxCarsPerWindow = new int[nbOptions];

            for (int o = 0; o < nbOptions; ++o)
                maxCarsPerWindow[o] = int.Parse(splitted[o]);

            splitted = input.ReadLine().Split(' ');

            windowSize = new int[nbOptions];

            for (int o = 0; o < nbOptions; ++o)
                windowSize[o] = int.Parse(splitted[o]);

            options = new int[nbClasses][];
            nbCars = new int[nbClasses];
            initialSequence = new int[nbPositions];

            int pos = 0;
            for (int c = 0; c < nbClasses; ++c)
            {
                splitted = input.ReadLine().Split(' ');
                nbCars[c] = int.Parse(splitted[1]);
                options[c] = new int[nbOptions];
                for (int o = 0; o < nbOptions; ++o)
                {
                    int v = int.Parse(splitted[o + 2]);
                    options[c][o] = (v == 1) ? 1 : 0;
                }
                for (int p = pos; p < pos + nbCars[c]; ++p)
                    initialSequence[p] = c;
                pos += nbCars[c];
            }
        }
    }

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

    void Solve(int limit)
    {
        optimizer = new HexalyOptimizer();

        // Declare the optimization model
        HxModel model = optimizer.GetModel();

        // sequence[i] = j if class initially planned on position j is produced on position i
        sequence = model.List(nbPositions);

        // sequence is a permutation of the initial production plan, all indexes must appear exactly once
        model.Constraint(model.Partition(sequence));

        // Create HexalyOptimizer arrays to be able to access them with "at" operators
        HxExpression initialArray = model.Array(initialSequence);
        HxExpression optionArray = model.Array(options);

        // Number of cars with option o in each window
        HxExpression[][] nbCarsWindows = new HxExpression[nbOptions][];
        for (int o = 0; o < nbOptions; ++o)
        {
            nbCarsWindows[o] = new HxExpression[nbPositions - windowSize[o] + 1];
            for (int j = 0; j < nbPositions - windowSize[o] + 1; ++j)
            {
                nbCarsWindows[o][j] = model.Sum();
                for (int k = 0; k < windowSize[o]; ++k)
                {
                    HxExpression classAtPosition = initialArray[sequence[j + k]];
                    nbCarsWindows[o][j].AddOperand(optionArray[classAtPosition, o]);
                }
            }
        }

        // Number of violations of option o capacity in each window
        HxExpression[][] nbViolationsWindows = new HxExpression[nbOptions][];
        for (int o = 0; o < nbOptions; ++o)
        {
            nbViolationsWindows[o] = new HxExpression[nbPositions - windowSize[o] + 1];
            for (int j = 0; j < nbPositions - windowSize[o] + 1; ++j)
                nbViolationsWindows[o][j] = model.Max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o]);
        }

        // Minimize the sum of violations for all options and all windows
        totalViolations = model.Sum();
        for (int o = 0; o < nbOptions; ++o)
            totalViolations.AddOperands(nbViolationsWindows[o]);

        model.Minimize(totalViolations);
        model.Close();

        // Set the initial solution
        sequence.GetCollectionValue().Clear();
        for (int p = 0; p < nbPositions; ++p)
            sequence.GetCollectionValue().Add(p);

        // Parametrize the optimizer
        optimizer.GetParam().SetTimeLimit(limit);

        optimizer.Solve();
    }

    /* Write the solution in a file with the following format:
     * - 1st line: value of the objective;
     * - 2nd line: for each position p, index of class at positions p. */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(totalViolations.GetValue());
            for (int p = 0; p < nbPositions; ++p)
                output.Write(initialSequence[sequence.GetCollectionValue().Get(p)] + " ");
            output.WriteLine();
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: CarSequencing inputFile [outputFile] [timeLimit]");
            Environment.Exit(1);
        }

        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "60";

        using (CarSequencing model = new CarSequencing())
        {
            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 CarSequencing {
    // Number of vehicles
    private int nbPositions;

    // Number of options
    private int nbOptions;

    // Number of classes
    private int nbClasses;

    // Options properties
    private int[] maxCarsPerWindow;
    private int[] windowSize;

    // Classes properties
    private int[] nbCars;
    private int[][] options;

    // Initial sequence
    private int[] initialSequence;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // LS Program variable
    private HxExpression sequence;

    // Objective
    private HxExpression totalViolations;

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

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            nbPositions = input.nextInt();
            nbOptions = input.nextInt();
            nbClasses = input.nextInt();

            maxCarsPerWindow = new int[nbOptions];
            for (int o = 0; o < nbOptions; ++o) {
                maxCarsPerWindow[o] = input.nextInt();
            }

            windowSize = new int[nbOptions];
            for (int o = 0; o < nbOptions; ++o) {
                windowSize[o] = input.nextInt();
            }

            options = new int[nbClasses][nbOptions];
            nbCars = new int[nbClasses];
            initialSequence = new int[nbPositions];
            int pos = 0;
            for (int c = 0; c < nbClasses; ++c) {
                input.nextInt(); // Note: index of class is read but not used
                nbCars[c] = input.nextInt();
                for (int o = 0; o < nbOptions; ++o) {
                    int v = input.nextInt();
                    options[c][o] = (v == 1) ? 1 : 0;
                }
                for (int p = pos; p < pos + nbCars[c]; ++p)
                    initialSequence[p] = c;
                pos += nbCars[c];
            }
        }
    }

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

        // sequence[i] = j if class initially planned on position j is produced on position i
        sequence = model.listVar(nbPositions);

        // Create HexalyOptimizer arrays to be able to access them with "at" operators
        HxExpression initialArray = model.array(initialSequence);
        HxExpression optionArray = model.array(options);

        // Number of cars with option o in each window
        HxExpression[][] nbCarsWindows = new HxExpression[nbOptions][];
        for (int o = 0; o < nbOptions; ++o) {
            HxExpression oExpr = model.createConstant(o);
            nbCarsWindows[o] = new HxExpression[nbPositions - windowSize[o] + 1];
            for (int j = 0; j < nbPositions - windowSize[o] + 1; ++j) {
                nbCarsWindows[o][j] = model.sum();
                for (int k = 0; k < windowSize[o]; ++k) {
                    HxExpression classAtPosition = model.at(initialArray, model.at(sequence, j + k));
                    nbCarsWindows[o][j].addOperand(model.at(optionArray, classAtPosition, oExpr));
                }
            }
        }

        // Number of violations of option o capacity in each window
        HxExpression[][] nbViolationsWindows = new HxExpression[nbOptions][];
        for (int o = 0; o < nbOptions; ++o) {
            nbViolationsWindows[o] = new HxExpression[nbPositions - windowSize[o] + 1];
            for (int j = 0; j < nbPositions - windowSize[o] + 1; ++j) {
                HxExpression delta = model.sub(nbCarsWindows[o][j], maxCarsPerWindow[o]);
                nbViolationsWindows[o][j] = model.max(0, delta);
            }
        }

        // Minimize the sum of violations for all options and all windows
        totalViolations = model.sum();
        for (int o = 0; o < nbOptions; ++o) {
            totalViolations.addOperands(nbViolationsWindows[o]);
        }

        model.minimize(totalViolations);
        model.close();

        // Set the initial solution
        sequence.getCollectionValue().clear();
        for (int p = 0; p < nbPositions; ++p)
            sequence.getCollectionValue().add(p);

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

        optimizer.solve();
    }

    /*
     * Write the solution in a file with the following format:
     * - 1st line: value of the objective;
     * - 2nd line: for each position p, index of class at positions p.
     */
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            output.println(totalViolations.getValue());
            for (int p = 0; p < nbPositions; ++p) {
                output.print(initialSequence[(int) sequence.getCollectionValue().get(p)] + " ");
            }
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java CarSequencing 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] : "60";

        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            CarSequencing model = new CarSequencing(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);
        }
    }
}