Car Sequencing Color¶

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

public class CarSequencingColor : IDisposable
{
    const int COLOR_HIGH_LOW = 0;
    const int HIGH_LOW_COLOR = 1;
    const int HIGH_COLOR_LOW = 2;
    const int COLOR_HIGH = 3;
    const int HIGH_COLOR = 4;

    // Number of vehicles
    int nbPositions;

    // Number of options
    int nbOptions;

    // Number of classes
    int nbClasses;

    // Paint batch limit
    int paintBatchLimit;

    // Objective order
    int objectiveOrder;

    // Start position
    int startPosition;

    // Options properties
    int[] maxCarsPerWindow;
    int[] windowSize;
    bool[] isPriorityOption;
    bool hasLowPriorityOptions;

    // Classes properties
    int[] colorClass;
    int[] nbCars;
    int[][] optionsData;

    // Initial sequence
    int[] initialSequence;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // LS Program variable
    HxExpression sequence;

    // Objectives
    HxExpression objectiveColor;
    HxExpression objectiveHighPriority;
    HxExpression objectiveLowPriority;

    public CarSequencingColor()
    {
        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]);
            paintBatchLimit = int.Parse(splitted[3]);
            objectiveOrder = int.Parse(splitted[4]);
            startPosition = int.Parse(splitted[5]);

            maxCarsPerWindow = new int[nbOptions];
            windowSize = new int[nbOptions];
            isPriorityOption = new bool[nbOptions];
            hasLowPriorityOptions = false;

            for (int o = 0; o < nbOptions; ++o)
            {
                splitted = input.ReadLine().Split(' ');
                maxCarsPerWindow[o] = int.Parse(splitted[0]);
                windowSize[o] = int.Parse(splitted[1]);
                isPriorityOption[o] = int.Parse(splitted[2]) == 1;
                if (!isPriorityOption[o])
                    hasLowPriorityOptions = true;
            }

            if (!hasLowPriorityOptions)
            {
                if (objectiveOrder == COLOR_HIGH_LOW)
                    objectiveOrder = COLOR_HIGH;
                else if (objectiveOrder == HIGH_COLOR_LOW)
                    objectiveOrder = HIGH_COLOR;
                else if (objectiveOrder == HIGH_LOW_COLOR)
                    objectiveOrder = HIGH_COLOR;
            }

            optionsData = new int[nbClasses][];
            nbCars = new int[nbClasses];
            colorClass = new int[nbClasses];

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

            initialSequence = new int[nbPositions];
            for (int p = 0; p < nbPositions; ++p)
                initialSequence[p] = int.Parse(input.ReadLine());
        }
    }

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

        // Past classes (before startPosition) can not move
        for (int p = 0; p < startPosition; ++p)
            model.Constraint(sequence[p] == p);

        // Create HexalyOptimizer arrays to be able to access them with "at" operators
        HxExpression initials = model.Array(initialSequence);
        HxExpression colors = model.Array(colorClass);
        HxExpression options = model.Array(optionsData);

        // 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];
            for (int j = startPosition - windowSize[o] + 1; j < nbPositions; ++j)
            {
                nbCarsWindows[o][j] = model.Sum();
                for (int k = 0; k < windowSize[o]; ++k)
                {
                    if (j + k >= 0 && j + k < nbPositions)
                    {
                        HxExpression classAtPosition = initials[sequence[j + k]];
                        nbCarsWindows[o][j].AddOperand(options[classAtPosition, o]);
                    }
                }
            }
        }

        // Number of violations of option o capacity in each window
        objectiveHighPriority = model.Sum();
        if (hasLowPriorityOptions)
            objectiveLowPriority = model.Sum();
        for (int o = 0; o < nbOptions; ++o)
        {
            HxExpression nbViolationsWindows = model.Sum();
            for (int j = startPosition - windowSize[o] + 1; j < nbPositions; ++j)
            {
                nbViolationsWindows.AddOperand(
                    model.Max(0, nbCarsWindows[o][j] - maxCarsPerWindow[o])
                );
            }
            if (isPriorityOption[o])
                objectiveHighPriority.AddOperand(nbViolationsWindows);
            else
                objectiveLowPriority.AddOperand(nbViolationsWindows);
        }

        // Color change between position p and position p + 1
        HxExpression[] colorChange = new HxExpression[nbPositions - 1];
        objectiveColor = model.Sum();
        for (int p = startPosition - 1; p < nbPositions - 1; ++p)
        {
            HxExpression currentClass = initials[sequence[p]];
            HxExpression nextClass = initials[sequence[p + 1]];
            colorChange[p] = colors[currentClass] != colors[nextClass];
            objectiveColor.AddOperand(colorChange[p]);
        }

        // Paint limit constraints: at least one change every paintBatchLimit positions
        for (int p = startPosition; p < nbPositions - paintBatchLimit - 1; ++p)
        {
            HxExpression nodeOr = model.Or();
            for (int p2 = 0; p2 < paintBatchLimit; ++p2)
                nodeOr.AddOperand(colorChange[p + p2]);
            model.Constraint(nodeOr);
        }

        // Declare the objectives in the correct order
        switch (objectiveOrder)
        {
            case COLOR_HIGH_LOW:
                model.Minimize(objectiveColor);
                model.Minimize(objectiveHighPriority);
                model.Minimize(objectiveLowPriority);
                break;
            case HIGH_COLOR_LOW:
                model.Minimize(objectiveHighPriority);
                model.Minimize(objectiveColor);
                model.Minimize(objectiveLowPriority);
                break;
            case HIGH_LOW_COLOR:
                model.Minimize(objectiveHighPriority);
                model.Minimize(objectiveLowPriority);
                model.Minimize(objectiveColor);
                break;
            case COLOR_HIGH:
                model.Minimize(objectiveColor);
                model.Minimize(objectiveHighPriority);
                break;
            case HIGH_COLOR:
                model.Minimize(objectiveHighPriority);
                model.Minimize(objectiveColor);
                break;
        }

        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 objectives;
     * - 2nd line: for each position p, index of class at positions p. */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.Write(objectiveColor.GetValue() + " ");
            output.Write(objectiveHighPriority.GetValue() + " ");
            output.WriteLine(objectiveLowPriority.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: CarSequencingColor 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 (CarSequencingColor model = new CarSequencingColor())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}