# 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¶

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.

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

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

if (inFileName == nil) throw usage;

for [c in 1..nbClasses] {
}
}

/* 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)

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

with localsolver.LocalSolver() as ls:

#
#

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

ifstream infile;
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++) {
}
}
}

// 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++) {
}

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.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.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();
}

{
{
nbPositions = int.Parse(splitted[0]);
nbOptions = int.Parse(splitted[1]);
nbClasses = int.Parse(splitted[2]);

maxCarsPerWindow = new int[nbOptions];

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

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++)
{
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++)
{
}
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++)
{
}
}

// 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++)
{
}
}
}

// 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++)
{
}
}
}

// 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++)
{
}

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

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++) {
}
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])
}
}
}

// 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++) {
}
}
}

// 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++) {
}

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