# Car Sequencing¶

## Principles learned¶

• Differenciate structural constraints from first priority objectives

• Create a violation expression using a “max” operator

• Use a list variable

• Set an initial solution

## Problem¶

A number of cars is 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¶

In this problem, we dispose from an initial feasible solution which corresponds to a sequence of classes to be produced. Since the number of cars to be produced in each class is fixed, we can actually consider this problem as a permutation on the initial sequence given. A permutation is easily modeled in LocalSolver with a list variable, which we constrain to be a partition of all indexes.

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;

local pos = 0;
for [c in 0..nbClasses-1] {
initialSequence[p in pos..pos+nbCars[c]-1] = c;
pos += nbCars[c];
}
}

/* Declares the optimization model. */
function model() {
// sequence[i] = j if class initially placed on position j is produced on position i
sequence <- list(nbPositions);

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

// Number of cars with option o in each window
nbCarsWindows[o in 0..nbOptions-1][j in 0..nbPositions-windowSize[o]]
<- sum[k in 0..windowSize[o]-1](options[initialSequence[sequence[j + k]]][o]);

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

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

/* Parameterizes the solver. */
function param() {
sequence.value.clear();
for [p in 0..nbPositions-1]
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);
local listSolution = sequence.value;
for [p in 0..nbPositions-1]
solFile.print(initialSequence[listSolution[p]], " ");
solFile.println();
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python car_sequencing.py instances\4_72.in
Execution (Linux)
export PYTHONPATH=/opt/localsolver_11_0/bin/python
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 = 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)
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])]

#
# Declares the optimization model
#
model = ls.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 LocalSolver 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]]

# 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):

#
# Parameterizes the solver
#
if len(sys.argv) >= 4:
ls.param.time_limit = int(sys.argv)
else:
ls.param.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, '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")
```
Compilation / Execution (Windows)
cl /EHsc car_sequencing.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver110.lib
car_sequencing instances\4_72.in
Compilation / Execution (Linux)
g++ car_sequencing.cpp -I/opt/localsolver_11_0/include -llocalsolver110 -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;

// Initial sequence.
vector<lsint> initialSequence;

// Solver.
LocalSolver localsolver;

// LS Program variable.
LSExpression sequence;

// 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);
initialSequence.resize(nbPositions);
int pos = 0;
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);
}
for (int p = pos; p < pos + nbCars[c]; p++)
initialSequence[p] = c;
pos += nbCars[c];
}
}

void solve(int limit) {
// Declares the optimization model.
LSModel model = localsolver.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

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

// 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++) {
LSExpression classAtPosition = initialArray[sequence[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();

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

// Parameterizes the solver.
localsolver.getParam().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++) {
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;
const char* outputFile = argc >= 3 ? argv : NULL;
const char* strTimeLimit = argc >= 4 ? argv : "60";

try {
CarSequencing model;
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;
}
}
```
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.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;
int[][] options;

// Initial sequence.
int[] initialSequence;

// Solver.
LocalSolver localsolver;

// LS Program variable.
LSExpression sequence;

// Objective.
LSExpression totalViolations;

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

{
{
nbPositions = int.Parse(splitted);
nbOptions = int.Parse(splitted);
nbClasses = int.Parse(splitted);

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 int[nbClasses][];
nbCars = new int[nbClasses];
initialSequence = new int[nbPositions];

int pos = 0;
for (int c = 0; c < nbClasses; c++)
{
nbCars[c] = int.Parse(splitted);
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 (localsolver != null)
localsolver.Dispose();
}

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

// Declares the optimization model.
LSModel model = localsolver.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 LocalSolver arrays to be able to access them with "at" operators
LSExpression initialArray = model.Array(initialSequence);
LSExpression optionArray = model.Array(options);

// 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++)
{
LSExpression classAtPosition = initialArray[sequence[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++)
{
}

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

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

// Parameterizes the solver.
localsolver.GetParam().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++)
{
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;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "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_11_0/bin/localsolver.jar
java -cp /opt/localsolver_11_0/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 int[][] options;

// Initial sequence.
private int[] initialSequence;

// Solver.
private final LocalSolver localsolver;

// LS Program variable.
private LSExpression sequence;

// Objective
private LSExpression totalViolations;

private CarSequencing(LocalSolver localsolver) {
this.localsolver = localsolver;
}

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(); // skip
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) {
// Declares the optimization model.
LSModel model = localsolver.getModel();

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

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

// Number of cars with option o in each window
LSExpression[][] nbCarsWindows = new LSExpression[nbOptions][];
for (int o = 0; o < nbOptions; o++) {
LSExpression oExpr = model.createConstant(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++) {
LSExpression classAtPosition = model.at(initialArray, model.at(sequence, 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++) {
}

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

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

// Parameterizes the solver.
localsolver.getParam().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++) {
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;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "60";

try (LocalSolver localsolver = new LocalSolver()) {
CarSequencing model = new CarSequencing(localsolver);