# Solving your first business problem¶

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 distinguished 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 LSP model for this problem. Meanwhile, we illustrate how to read data from a file, we show how modeling the car sequencing by clearly defining the decisions, the constraints and the objective of the problem, and we introduce some of the parameters that can be used to control the search. The full program for this problem is available in our example tour, together with its Python, C++, Java and C# versions, plus a certain number of instance files.

## Reading input data¶

Data files for this problem are available in folder
`localsolver/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 of the `input()`

function to read input data. Note that
undefined variables are equal to `nil`

what allows checking the existence of
a variable (here we throw an error if inFileName or solfileName is not defined.
Then we merely read integers one after another in the file
(regardless of line breaks):

```
use io;
/* Read 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();
ratioNums[o in 0...nbOptions] = inFile.readInt();
ratioDenoms[o in 0...nbOptions] = inFile.readInt();
for [c in 0...nbClasses] {
inFile.readInt(); // Note: index of class is read but not used
nbCars[c] = inFile.readInt();
options[c][o in 0...nbOptions] = inFile.readInt();
}
}
```

## Modeling the problem¶

One of the most important step when modeling an optimization problem with the
LSP language is to define what are the decisions to be taken. These decisions
are such that instantiating them allows evaluating all other expressions of
your model (in particular, the constraints and the objectives). LocalSolver
will try to find the best possible decisions with respect to the given
objectives and constraints. Here we want to decide the ordering of cars in the
production line. In terms of 0-1 modeling, it amounts to defining
`nbClasses * nbPositions`

variables `cp[c][p]`

such that `cp[c][p]`

is
equal to 1 when the car at position `p`

belongs to class `c`

and 0 otherwise:

```
cp[c in 0...nbClasses][p in 0...nbPositions] <- bool();
```

Defining the constraints of your model is another important modeling task. Generally speaking, constraints should be limited to striclty necessary requirements. In the car sequencing problem, it is physically impossible to have two cars at the same position, whereas satisfying all P/Q ratios is not always possible which is why it was defined here as an ‘’objective’’. Limiting the use of constraints is especially important in local-search modeling because it defines the search space and the ability to move from one solution to another.

Here we have two families of constraints expressing the assignment requirements: we must have exactly one car per position and the demand in cars for each class should be satisfied:

```
for [c in 0...nbClasses]
constraint sum[p in 0...nbPositions](cp[c][p]) == nbCars[c];
for [p in 0...nbPositions]
constraint sum[c in 0...nbClasses](cp[c][p]) == 1;
```

Now, to write the objective, we introduce some intermediate expressions. First,
we declare some expressions `op[o][p]`

which are equal to 1 when the car at
position `p`

has option `o`

and 0 otherwise:

```
op[o in 0...nbOptions][p in 0...nbPositions] <-
or[c in 0...nbClasses : options[c][o]](cp[c][p]);
```

Indeed, option `o`

appears at position `p`

if this position hosts one of
the classes featuring this option. The list of such classes is specified by the
iteration `[c in 0...nbClasses : options[c][o]]`

. This ability to define
intermediate expressions makes the model more readable and more efficient
(if this intermediate expressions are used in several other expressions).
Similarly, the number of times option `o`

appears between position `j`

and
position `j+Q[o]-1`

can be defined as:

```
nbCarsWindows[o in 0...nbOptions][p in 0...nbPositions-ratioDenoms[o]+1]
<- sum[k in 0...ratioDenoms[o]](op[o][p+k]);
```

Finally, the penalty function on overcapacities can be written exactly as it was defined above in the specifications of the problem:

```
nbViolationsWindows[o in 0...nbOptions][p in 0...nbPositions-ratioDenoms[o]+1]
<- max(nbCarsWindows[o][p]-ratioNums[o], 0);
```

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:

```
obj <- sum[o in 0...nbOptions]
[p in 0...nbPositions-ratioDenoms[o]+1](nbViolationsWindows[o][p]);
minimize obj;
```

Here is the resulting code of the `model()`

function in the LSP model
corresponding to the car sequencing problem:

```
function model() {
// 0-1 decisions:
// cp[c][p] = 1 if class c is at position p, and 0 otherwise
cp[c in 0...nbClasses][p in 0...nbPositions] <- bool();
// constraints:
// for each class c, no more than nbCars[c] assigned to positions
for [c in 0...nbClasses]
constraint sum[p in 0...nbPositions](cp[c][p]) == nbCars[c];
// constraints: one car assigned to each position p
for [p in 0...nbPositions]
constraint sum[c in 0...nbClasses](cp[c][p]) == 1;
// expressions:
// op[o][p] = 1 if option o appears at position p, and 0 otherwise
op[o in 0...nbOptions][p in 0...nbPositions] <-
or[c in 0...nbClasses : options[c][o]](cp[c][p]);
// expressions: compute the number of cars in each window
nbCarsWindows[o in 0...nbOptions][p in 0...nbPositions-ratioDenoms[o]+1]
<- sum[k in 0...ratioDenoms[o]](op[o][p+k]);
// expressions: compute the number of violations in each window
nbViolationsWindows[o in 0...nbOptions][p in 0...nbPositions-ratioDenoms[o]+1]
<- max(nbCarsWindows[o][p]-ratioNums[o], 0);
// objective: minimize the sum of violations for all options and all windows
obj <- sum[o in 0...nbOptions][p in 0...nbPositions-ratioDenoms[o]+1](nbViolationsWindows[o][p]);
minimize obj;
}
```

## Parameterizing the solver¶

Some parameters can be defined in the `param()`

function in order to control
the search:

```
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 60;
if (lsTimeBetweenDisplays == nil) lsTimeBetweenDisplays = 5;
}
```

This last function makes our model complete. Some of the control parameters can
be set in command line, instead of being defined in the LSP file. For instance,
the following command line launches the resolution for 300 seconds on the
instance `localsolver/examples/carsequencing/instances/carseq_500_8_20_08.in`

.

```
> localsolver car_sequencing.lsp inFileName=instances/carseq_500_8_20_08.in solFileName=sol.txt lsTimeLimit=30
```

All control parameters can be found in the section Built-in variables and functions.

Having launched LocalSolver with the above command line, you should observe the following output.

```
LocalSolver 9.0.20190611-Win64. All rights reserved.
Load car_sequencing.lsp...
Run input...
Run model...
Preprocess model 100% ...
Run param...
Run solver...
Initialize solver 100% ...
Push initial solutions 100% ...
Model: expressions = 27001, decisions = 10000 constraints = 520, objectives = 1,
Param: time limit = 30 sec, no iteration limit
[ optimization direction ] minimize
[ 0 sec, 0 itr]: No feasible solution found (infeas = 1040)
[ 5 sec, 217424 itr]: obj = 33
[ 10 sec, 384536 itr]: obj = 24
[ 15 sec, 584611 itr]: obj = 19
[ 20 sec, 783454 itr]: obj = 15
[ 25 sec, 1043836 itr]: obj = 12
[ 30 sec, 1310253 itr]: obj = 10
[ 31 sec, 1310253 itr]: obj = 10
1310253 iterations performed in 31 seconds
Feasible solution:
obj = 10
gap = 100.00%
bounds = 0
Run output...
```

Each 5th second (in accordance with parameter `lsTimeBetweenDisplays`

),
a brief report of the current state of the search is displayed: the number of
elapsed seconds and the number of iterations performed, the value of objective
functions are given in lexicographic order (separated with `|`

).

You can disable all displays by setting `lsVerbosity`

to 0.

## Writing solutions¶

You can define an `output()`

function that will be called by LocalSolver at
the end of the search. For instance we chose here to define a function writing
the solution of the problem to a file whose name must be assigned
(for instance in the command line) to some variable `solFileName`

. It writes
the solution in the following format:

First line = the objective function

Second line = the classes at positions 1 to nbPositions

Writing to a file is done with the usual `print`

and `println`

functions:

```
function output() {
if(solFileName == nil) return;
/* 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. */
local solFile = io.openWrite(solFileName);
solFile.println(obj.value);
for [p in 0...nbPositions][c in 0...nbClasses : cp[c][p].value]
solFile.print(c, " ");
solFile.println();
}
```