Solving your first business problem in C++

The car sequencing problem is a well-known combinatorial optimization problem related to the organization of the production line of a car manufacturer. It involves scheduling a set of cars which are divided into classes by different sets of options. The assembly line has different stations where the various options (air-conditioning, sun-roof, etc.) are installed by teams. Each such station has a certain workload capacity given by the parameters P and Q: the station is able to handle P cars with the given option in each sequence of Q cars. The goal of the problem is to produce of a sequence of cars respecting the given demand for each class and such that overcapacities are minimized. In other words, for each option P/Q and for each window of length Q, a penalty max(0,N-P) is counted where N is the number of such options actually scheduled in this window.

In this section, we present a simple model for this problem. We illustrate how to read the input data from a file, we show how to model the Car Sequencing Problem by clearly defining the decisions, constraints, and objective of the problem, and we introduce some of the parameters that can be used to control the search.

Note

The full program for this problem is available among our code templates, together with its Hexaly Modeler, Python, Java, and C# versions, plus a certain number of instance files.

Reading input data

Data files for this problem are available in folder hexaly/examples/carsequencing and more files can be downloaded from http://www.csplib.org (problem number 001). The format of these files is:

  • 1st line: number of cars; number of options; number of classes.

  • 2nd line: for each option, the maximum number of cars with this option in a block (parameter P).

  • 3rd line: for each option, the block size to which the maximum number refers (parameter Q).

  • Then for each class: index of the class; number of cars in this class; for each option, whether or not this class requires it (0 or 1).

Below is the code to read the input data. To simplify the modeling, we also define an initial sequence of cars, starting with all the cars belonging to the first class, followed by all the cars belonging to the second class, and so on:

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

Modeling the problem

One of the most important steps when modeling an optimization problem with Hexaly is to define the decision variables. These decisions are such that instantiating them allows evaluating all other expressions in your model (in particular, the constraints and objectives). Hexaly Optimizer will try to find the best possible decisions with respect to the given objectives and constraints. Here, we want to decide the order of cars in the production line. The best way to model an order with Hexaly is to define a list decision variable. Here, the list represents the sequence of cars: the i-th element of the list corresponds to the index of the i-th car to build. In other words, if the i-th element in the list is equal to j, then the i-th car to build is the one described by initialSequence[j]:

sequence = model.listVar(nbPositions);

Defining the constraints of your model is another important modeling task. Generally speaking, constraints should be limited to strictly necessary requirements. In the car sequencing problem, it is physically impossible to have two cars at the same position. On the contrary, satisfying all P/Q ratios is not always possible, which is why we define it as a first-priority objective instead. Limiting the use of constraints is generally a good practice, as Hexaly Optimizer tends to benefit from denser search spaces. Therefore, symmetry-breaking constraints and other types of non-necessary constraints should also be avoided.

To satisfy the assignment requirements, each car to be produced must be present exactly once on the assembly line. Using the partition operator, we ensure that every element between 0 and the total number of positions (excluded) is present exactly once in the list, meaning that every car appears exactly once in the sequence:

model.addConstraint(model.partition(sequence));

Before writing the objective function, we introduce some intermediate expressions. From the value of the sequence, we can compute, for each option and each position in the line, the number of cars with this option in the window starting at this position:

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(optionArray[classAtPosition][o]);
        }
    }
}

Indeed, for each position p, the index of the car at position p is sequence[p]. This car is described by the expression initialArray[sequence[p]]. To know whether this car includes any option o, we check the value of optionArray[initialArray[sequence[p]]][o]. This ability to define intermediate expressions makes the model more readable and more efficient (if these intermediate expressions are used in several other expressions).

We can then deduce the number of violations on overcapacities for each option and 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]);
    }
}

Note that we are using here a different way to express a sum. Indeed, you can define a sum with the sum operator, but you can also use arithmetic operators + and -. Ultimately, the last step consists in defining the objective function, which is the sum of all violations:

totalViolations = model.sum();
for (int o = 0; o < nbOptions; ++o) {
    totalViolations.addOperands(nbViolationsWindows[o].begin(), nbViolationsWindows[o].end());
}

Parameterizing the optimizer

Some parameters can be defined after closing the model in order to control the search:

optimizer.getParam().setTimeLimit(60);

All control parameters can be found in the HxParam class.

Setting an initial solution

Besides control parameters, it is also possible to set an initial solution. Having an initial solution is not necessary for Hexaly Optimizer to function properly, but it can sometimes be useful if you wish to start the optimization from an existing solution, or for debugging purposes.

To initialize the value of a list decision variable, you must first make sure it is empty, then add its elements one by one:

sequence.getCollectionValue().clear();
for (int p = 0; p < nbPositions; ++p)
    sequence.getCollectionValue().add(p);

Launching the resolution

Having launched Hexaly Optimizer as explained on the previous page, you should observe the following output:

Hexaly Optimizer 14.0.20250724-Linux64. All rights reserved.
Load car_sequencing.hxm...
Run input...
Run model...
Run param...
Run optimizer...

Model:  expressions = 10929, decisions = 1, constraints = 1, objectives = 1
Param:  time limit = 60 sec, no iteration limit

[objective direction ]:     minimize

[  0 sec,       0 itr]:          403
[ optimality gap     ]:      100.00%
[  1 sec,   32710 itr]:            6
[  2 sec,   97525 itr]:            2
[  3 sec,  167931 itr]:            1
[  4 sec,  241127 itr]:            1
[  4 sec,  241144 itr]:            0
[ optimality gap     ]:           0%

241144 iterations performed in 4 seconds

Optimal solution:
obj    =            0
gap    =           0%
bounds =            0

Run output...

Each second (in accordance with the parameter in function setTimeBetweenDisplays, of default value 1), a brief report of the current state of the search is displayed: the number of elapsed seconds and the number of iterations performed, and the values of the objective functions given in lexicographic order (separated with |).

You can disable all displays by calling the setVerbosity method with parameter 0.

Writing solutions

Here, we define a function writing the solution of the problem in a file. It writes the solution in the following format:

  1. First line: the objective value

  2. Second line: for each position p, index of the class at position p

You can retrieve the value of any expression (decisions, intermediate expressions) thanks to the getValue function:

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

Complete code

Here is the complete C++ code for the Car Sequencing Problem:

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