Car sequencing

Principles learned

  • Differenciate structural constraints from first priority objectives
  • Create a violation expression using a “max” operator
  • Use of n-ary operator “or”

Problem

../_images/car.png

A number of cars are to be produced; they are not identical, because different options are available as variants on the basic model. The assembly line has different stations which install the various options (air- conditioning, sun-roof, etc.). These stations have been designed to handle at most a certain percentage of the cars passing along the assembly line. Furthermore, the cars requiring a certain option must not be bunched together, otherwise the station will not be able to cope. Consequently, the cars must be arranged in a sequence so that the capacity of each station is never exceeded. For instance, if a particular station can only cope with at most two thirds of the cars passing along the line, the sequence must be built so that at most 2 cars in any window of 3 require that option. The problem has been shown to be NP-hard.

Download the example

Data

The format of the data files is as follows:

  • 1st line: number of cars; number of options; number of classes.
  • 2nd line: for each option, the maximum number of cars with that option in a block.
  • 3rd line: for each option, the block size to which the maximum number refers.
  • Then for each class: index no.; no. of cars in this class; for each option, whether or not this class requires it (1 or 0).

For more details, see CSPLib.

Program

The decisions variables are classOnPos[c][p] equal to 1 if a car of the class c is at the position p and 0 otherwise. Constraints are created to ensure that all cars of each class are assigned to one position, and that each position contains only one car. Expressions nbCarsWindows[o][p] compute the number of cars with option o in each window and expressions nbViolationsWindows[o][p] compute the number of capacity violations for option o in each window.

Even though the definition of the problem is purely a satisfaction problem, we chose to add an objective to minimize the sum of capacity violations for all options and all windows. Having 0 violations on this criteria is indeed more a “business” constraint than a structural one: if it is not entirely satisfied, the assembly chain will slow down but it will be able to continue. On the contrary, having two cars on one spot is not practical because the assembly line is not designed to do this: it is a structural constraint. See this section of the quick start guide for more information about the difference to make between “high priority objectives” and constraints.

Execution:
localsolver car_sequencing.lsp inFileName=instances/4_72.in [lsTimeLimit=] [solFileName=]
/********** car_sequencing.lsp **********/

use io;

/* Reads instance data. */
function input() {
    local usage = "Usage: localsolver car_sequencing.lsp "
        + "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]";

    if (inFileName == nil) throw usage;
    local inFile = io.openRead(inFileName);
    nbPositions = inFile.readInt();
    nbOptions = inFile.readInt();
    nbClasses = inFile.readInt();

    maxCarsPerWindow[1..nbOptions] = inFile.readInt();
    windowSize[1..nbOptions] = inFile.readInt();

    for [c in 1..nbClasses] {
        inFile.readInt(); // Note: index of class is read but not used
        nbCars[c] = inFile.readInt();
        options[c][1..nbOptions] = inFile.readInt();
    }
}

/* Declares the optimization model. */
function model() {    
    // classOnPos[c][p] = 1 if class c is at position p, and 0 otherwise
    classOnPos[1..nbClasses][1..nbPositions] <- bool();

    // All cars of class c are assigned to positions
    for [c in 1..nbClasses] 
        constraint sum[p in 1..nbPositions](classOnPos[c][p]) == nbCars[c];

    // One car assigned to each position p
    for [p in 1..nbPositions] 
        constraint sum[c in 1..nbClasses](classOnPos[c][p]) == 1;

    // optionsOnPos[o][p] = 1 if option o appears at position p, and 0 otherwise
    optionsOnPos[o in 1..nbOptions][p in 1..nbPositions] 
        <- or[c in 1..nbClasses : options[c][o]](classOnPos[c][p]);

    // Number of cars with option o in each window
    nbCarsWindows[o in 1..nbOptions][p in 1..nbPositions - windowSize[o] + 1] 
        <- sum[k in 1..windowSize[o]](optionsOnPos[o][p + k - 1]);

    // Number of violations of option o capacity in each window
    nbViolationsWindows[o in 1..nbOptions][p in 1..nbPositions - windowSize[o] + 1] 
        <- max(nbCarsWindows[o][p] - maxCarsPerWindow[o], 0);

    // Minimize the sum of violations for all options and all windows
    totalViolations <- sum[o in 1..nbOptions][p in 1..nbPositions - windowSize[o] + 1](nbViolationsWindows[o][p]);
    minimize totalViolations;
}

/* Parameterizes the solver. */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 60;
}

/* Writes the solution in a file following the following format: 
 * - 1st line: value of the objective;
 * - 2nd line: for each position p, index of class at positions p. */
function output() {
    if(solFileName == nil) return;
    local solFile = io.openWrite(solFileName);
    solFile.println(totalViolations.value);
    for [p in 1..nbPositions][c in 1..nbClasses : classOnPos[c][p].value == 1] 
        solFile.print(c - 1, " ");
    solFile.println();
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python27\
python car_sequencing.py instances\4_72.in
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python car_sequencing.py instances/4_72.in
########## car_sequencing.py ##########

import localsolver
import sys

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


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


with localsolver.LocalSolver() as ls:

    #
    # Reads instance data 
    #

    file_it = iter(read_integers(sys.argv[1]))
    nb_positions = file_it.next()
    nb_options = file_it.next()
    nb_classes = file_it.next()
    max_cars_per_window = [file_it.next() for i in range(nb_options)]
    window_size = [file_it.next() for i in range(nb_options)]
    nb_cars = []
    options = []

    for c in range(nb_classes):
        file_it.next()
        nb_cars.append(file_it.next())
        options.append([file_it.next() == 1 for i in range(nb_options)])

    #
    # Declares the optimization model
    #
    model = ls.model

    # class_on_pos[c][p] = 1 if class c is at position p, and 0 otherwise
    class_on_pos = [[model.bool() for j in range(nb_positions)] for i in range(nb_classes)]

    # All cars of class c are assigned to positions
    for c in range(nb_classes):
        model.constraint(model.sum(class_on_pos[c][p] for p in range(nb_positions)) == nb_cars[c])

    # One car assigned to each position p
    for p in range(nb_positions): 
        model.constraint(model.sum(class_on_pos[c][p] for c in range(nb_classes)) == 1)

    # options_on_pos[o][p] = 1 if option o appears at position p, and 0 otherwise
    options_on_pos = [None]*nb_options
    for o in range(nb_options):
        options_on_pos[o] = [None]*nb_positions
        for p in range(nb_positions):
            options_on_pos[o][p] = model.or_(class_on_pos[c][p] for c in range(nb_classes) if options[c][o])

    # 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 p in range(nb_positions - window_size[o] + 1):
            nb_cars_windows[o][p] = model.sum(options_on_pos[o][p + k] for k in range(window_size[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()

    #
    # Parameterizes the solver
    #
    ls.param.nb_threads = 2
    if len(sys.argv) >= 4: ls.create_phase().time_limit = int(sys.argv[3])
    else: ls.create_phase().time_limit = 60

    ls.solve()

    #
    # Writes the solution in a file
    #
    if len(sys.argv) >= 3:
        # Writes the solution in a file following the following format: 
        # * 1st line: value of the objective;
        # * 2nd line: for each position p, index of class at positions p.
        with open(sys.argv[2], 'w') as f:
            f.write("%d\n" % total_violations.value)
            for p in range(nb_positions):
                for c in range(nb_classes):
                    if class_on_pos[c][p].value == 1:
                        f.write("%d " % c)
                        break

            f.write("\n")
Compilation / Execution (Windows)
cl /EHsc car_sequencing.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.lib
car_sequencing instances\4_72.in
Compilation / Execution (Linux)
g++ car_sequencing.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o car_sequencing
./car_sequencing instances/4_72.in
//********* car_sequencing.cpp *********

#include <iostream>
#include <fstream>
#include <vector>
#include "localsolver.h"

using namespace localsolver;
using namespace std;

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

    // Number of options. 
    int nbOptions;

    // Number of classes. 
    int nbClasses;

    // Options properties. 
    vector<lsint> maxCarsPerWindow;
    vector<lsint> windowSize;

    // Classes properties. 
    vector<lsint> nbCars;
    vector<vector<bool> > options;

    // Solver. 
    LocalSolver localsolver;

    // LS Program variables. 
    vector<vector<localsolver::LSExpression> > classOnPos;

    // Objective 
    LSExpression totalViolations;

    // Reads 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);
        for (int c = 0; c < nbClasses; c++) {
            int ignored;
            infile >> ignored;
            infile >> nbCars[c];
            options[c].resize(nbOptions);
            for (int o = 0; o < nbOptions; o++) {
                int v;
                infile >> v;
                options[c][o] = (v == 1);
            }
        }
    }

    void solve(int limit) {
        // Declares the optimization model. 
        LSModel model = localsolver.getModel();

        // classOnPos[c][p] = 1 if class c is at position p, and 0 otherwise
        classOnPos.resize(nbClasses);
        for (int c = 0; c < nbClasses; c++) {
            classOnPos[c].resize(nbPositions);
            for (int p = 0; p < nbPositions; p++) {
                classOnPos[c][p] = model.boolVar();
            }
        }

        // All cars of class c are assigned to positions
        for (int c = 0; c < nbClasses; c++) {
            LSExpression nbCarsFromClass = model.sum(classOnPos[c].begin(), classOnPos[c].end());
            model.constraint(nbCarsFromClass == nbCars[c]);
        }

        // One car assigned to each position p
        for (int p = 0; p < nbPositions; p++) {
            LSExpression nbCarsOnPos = model.sum();
            for (int c = 0; c < nbClasses; c++) {
                nbCarsOnPos += classOnPos[c][p];
            }
            model.constraint(nbCarsOnPos == 1);
        }

        // optionsOnPos[o][p] = 1 if option o appears at position p, and 0 otherwise
        vector<vector<LSExpression> > optionsOnPos;
        optionsOnPos.resize(nbOptions);
        for (int o = 0; o < nbOptions; o++) {
            optionsOnPos[o].resize(nbPositions);
            for (int p = 0; p < nbPositions; p++) {
                optionsOnPos[o][p] = model.or_();
                for (int c = 0; c < nbClasses; c++) {
                    if (options[c][o]) optionsOnPos[o][p].addOperand(classOnPos[c][p]);
                }
            }
        }

        // Number of cars with option o in each window
        vector<vector<LSExpression> > 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++) {
                    nbCarsWindows[o][j] += optionsOnPos[o][j + k];
                }
            }
        }

        // Number of violations of option o capacity in each window
        vector<vector<LSExpression> > 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();

        // Parameterizes the solver. 
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(limit);

        localsolver.solve();
    }

    // Writes the solution in a file following 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++) {
            for (int c = 0; c < nbClasses; c++) {
                if (classOnPos[c][p].getValue() == 1) {
                    outfile << c << " ";
                    break;
                }
            }
        }
        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 << "Error occurred: " << e.what() << endl;
        return 1;
    }
}
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc CarSequencing.cs /reference:localsolvernet.dll
CarSequencing instances\4_72.in
/********** CarSequencing.cs **********/

using System;
using System.IO;
using localsolver;

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;
    bool[][] options;

    // Solver. 
    LocalSolver localsolver;

    // LS Program variables. 
    LSExpression[][] classOnPos;

    // Objective.
    LSExpression totalViolations;

    public CarSequencing()
    {
        localsolver = new LocalSolver();
    }

    // Reads 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 bool[nbClasses][];
            nbCars = new int[nbClasses];

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

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

    void Solve(int limit)
    {
        localsolver = new LocalSolver();

        // Declares the optimization model.
        LSModel model = localsolver.GetModel();

        // classOnPos[c][p] = 1 if class c is at position p, and 0 otherwise
        classOnPos = new LSExpression[nbClasses][];
        for (int c = 0; c < nbClasses; c++)
        {
            classOnPos[c] = new LSExpression[nbPositions];
            for (int p = 0; p < nbPositions; p++)
            {
                classOnPos[c][p] = model.Bool();
            }
        }

        // All cars of class c are assigned to positions
        for (int c = 0; c < nbClasses; c++)
        {
            LSExpression nbCarsFromClass = model.Sum();
            for (int p = 0; p < nbPositions; p++)
            {
                nbCarsFromClass.AddOperand(classOnPos[c][p]);
            }
            model.Constraint(nbCarsFromClass == nbCars[c]);
        }

        // One car assigned to each position p
        for (int p = 0; p < nbPositions; p++)
        {
            LSExpression nbCarsOnPos = model.Sum();
            for (int c = 0; c < nbClasses; c++)
            {
                nbCarsOnPos.AddOperand(classOnPos[c][p]);
            }
            model.AddConstraint(nbCarsOnPos == 1);
        }

        // optionsOnPos[o][p] = 1 if option o appears at position p, and 0 otherwise
        LSExpression[,] optionsOnPos = new LSExpression[nbOptions, nbPositions];
        for (int o = 0; o < nbOptions; o++)
        {
            for (int p = 0; p < nbPositions; p++)
            {
                optionsOnPos[o, p] = model.Or();
                for (int c = 0; c < nbClasses; c++)
                {
                    if (options[c][o]) optionsOnPos[o, p].AddOperand(classOnPos[c][p]);
                }
            }
        }

        // Number of cars with option o in each window
        LSExpression[][] nbCarsWindows = new LSExpression[nbOptions][];
        for (int o = 0; o < nbOptions; o++)
        {
            nbCarsWindows[o] = new LSExpression[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++)
                {
                    nbCarsWindows[o][j].AddOperand(optionsOnPos[o, j + k]);
                }
            }
        }

        // Number of violations of option o capacity in each window
        LSExpression[][] nbViolationsWindows = new LSExpression[nbOptions][];
        for (int o = 0; o < nbOptions; o++)
        {
            nbViolationsWindows[o] = new LSExpression[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();

        // Parameterizes the solver.
        LSPhase phase = localsolver.CreatePhase();
        phase.SetTimeLimit(limit);

        localsolver.Solve();
    }

    // Writes the solution in a file following 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++)
            {
                for (int c = 0; c < nbClasses; c++)
                {
                    if (classOnPos[c][p].GetValue() == 1)
                    {
                        output.Write(c + " ");
                        break;
                    }
                }
            }
            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);
        }
    }
}
Compilation / Execution (Windows)
javac CarSequencing.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. CarSequencing instances\4_72.in
Compilation/Execution (Linux)
javac CarSequencing.java -cp /opt/localsolver_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. CarSequencing instances/4_72.in
/******** CarSequencing.java *********/

import java.util.*;
import java.io.*;
import localsolver.*;

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 boolean[][] options;

    // Solver.
    private LocalSolver localsolver;

    // LS Program variables.
    private LSExpression[][] classOnPos;

    // Objective
    private LSExpression totalViolations;

    // Reads 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 boolean[nbClasses][nbOptions];
            nbCars = new int[nbClasses];
            for (int c = 0; c < nbClasses; c++) {
                input.nextInt(); // skip
                nbCars[c] = input.nextInt();
                for (int o = 0; o < nbOptions; o++) {
                    int v = input.nextInt();
                    options[c][o] = (v == 1);
                }
            }
        }
    }

    private void solve(int limit) {
        localsolver = new LocalSolver();

        // Declares the optimization model.
        LSModel model = localsolver.getModel();

        // classOnPos[c][p] = 1 if class c is at position p, and 0 otherwise
        classOnPos = new LSExpression[nbClasses][nbPositions];
        for (int c = 0; c < nbClasses; c++) {
            for (int p = 0; p < nbPositions; p++) {
                classOnPos[c][p] = model.boolVar();
            }
        }

        // All cars of class c are assigned to positions
        for (int c = 0; c < nbClasses; c++) {
            LSExpression nbCarsFromClass = model.sum(classOnPos[c]);
            model.constraint(model.eq(nbCarsFromClass, nbCars[c]));
        }

        // One car assigned to each position p
        for (int p = 0; p < nbPositions; p++) {
            LSExpression nbCarsOnPos = model.sum();
            for (int c = 0; c < nbClasses; c++) {
                nbCarsOnPos.addOperand(classOnPos[c][p]);
            }
            model.constraint(model.eq(nbCarsOnPos, 1));
        }

        // optionsOnPos[o][p] = 1 if option o appears at position p, and 0 otherwise
        LSExpression[][] optionsOnPos = new LSExpression[nbOptions][nbPositions];
        for (int o = 0; o < nbOptions; o++) {
            for (int p = 0; p < nbPositions; p++) {
                optionsOnPos[o][p] = model.or();
                for (int c = 0; c < nbClasses; c++) {
                    if (options[c][o])
                        optionsOnPos[o][p].addOperand(classOnPos[c][p]);
                }
            }
        }

        // Number of cars with option o in each window
        LSExpression[][] nbCarsWindows = new LSExpression[nbOptions][];
        for (int o = 0; o < nbOptions; o++) {
            nbCarsWindows[o] = new LSExpression[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++) {
                    nbCarsWindows[o][j].addOperand(optionsOnPos[o][j + k]);
                }
            }
        }

        // Number of violations of option o capacity in each window
        LSExpression[][] nbViolationsWindows = new LSExpression[nbOptions][];
        for (int o = 0; o < nbOptions; o++) {
            nbViolationsWindows[o] = new LSExpression[nbPositions - windowSize[o] + 1];
            for (int j = 0; j < nbPositions - windowSize[o] + 1; j++) {
                LSExpression 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();

        // Parameterizes the solver.
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(limit);

        localsolver.solve();
    }

    // Writes the solution in a file following 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++) {
                for (int c = 0; c < nbClasses; c++) {
                    if (classOnPos[c][p].getValue() == 1) {
                        output.print(c + " ");
                        break;
                    }
                }
            }
            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 {
            CarSequencing model = new CarSequencing();
            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);
        }
    }
}