Solving your first business problem¶

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;

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

    ratioNums[1..nbOptions] = inFile.readInt();
    ratioDenoms[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();
    }
}

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[1..nbClasses][1..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 1..nbClasses]
    constraint sum[p in 1..nbPositions](cp[c][p]) == nbCars[c];

for [p in 1..nbPositions]
    constraint sum[c in 1..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 1..nbOptions][p in 1..nbPositions] <-
    or[c in 1..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 1..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 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1]
    <- sum[k in 1..ratioDenoms[o]](op[o][p+k-1]);

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

nbViolationsWindows[o in 1..nbOptions][p in 1..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 1..nbOptions]
  [p in 1..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[1..nbClasses][1..nbPositions] <- bool();

    // constraints:
    // for each class c, no more than nbCars[c] assigned to positions
    for [c in 1..nbClasses]
        constraint sum[p in 1..nbPositions](cp[c][p]) == nbCars[c];

    // constraints: one car assigned to each position p
    for [p in 1..nbPositions]
        constraint sum[c in 1..nbClasses](cp[c][p]) == 1;

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

    // expressions: compute the number of cars in each window
    nbCarsWindows[o in 1..nbOptions][p in 1..nbPositions-ratioDenoms[o]+1]
        <- sum[k in 1..ratioDenoms[o]](op[o][p+k-1]);

    // expressions: compute the number of violations in each window
    nbViolationsWindows[o in 1..nbOptions][p in 1..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 1..nbOptions][p in 1..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 local search:

function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 60;
    if (lsNbThreads == nil) lsNbThreads = 2;
    if (lsTimeBetweenDisplays == nil) lsTimeBetweenDisplays = 3;
}

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 (use the smaller instance free_trial_cs.in if your LocalSolver license is limited in size).

> 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|builtinvariablesandfunctions.html]].

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

LocalSolver 5.5 (Linux64, build 20150629)
Copyright (C) 2015 Innovation 24, Aix-Marseille University, CNRS.
All rights reserved. See LocalSolver Terms and Conditions for details.

Load car_sequencing.lsp...
Run input...
Run model...
Preprocess model 100% ...
Close model 100% ...
Run param...
Run solver...
Initialize threads 100% ...
Push initial solutions 100% ...

Model:
  expressions = 27001, operands = 75873
  decisions = 10000 (bool = 10000, int = 0, float = 0),
  constraints = 520, objectives = 1, constants  = 17
  Preprocessing transformed 8483 expressions

Param:
  time limit = 30 sec, no iteration limit
  seed = 0, nb threads = 2, annealing level = 1

Objectives:
  Obj 0: minimize, bound = 0

Phases:
  Phase 0: time limit = 30 sec, no iteration limit, optimized objective = 0


Phase 0:
[  0 sec,       0 itr] : infeas : 1040 violated expressions
[  3 sec,  188106 itr] : obj =           40
[  6 sec,  410130 itr] : obj =           28
[  9 sec,  644028 itr] : obj =           23
[ 12 sec,  883183 itr] : obj =           18
[ 15 sec, 1120551 itr] : obj =           16
[ 18 sec, 1337814 itr] : obj =           13
[ 21 sec, 1566804 itr] : obj =           12
[ 24 sec, 1804435 itr] : obj =           10
[ 27 sec, 2046929 itr] : obj =            9
[ 30 sec, 2286995 itr] : obj =            7
[ 30 sec, 2286995 itr] : obj =            7

2286995 iterations, 4573688 moves performed in 30 seconds
Feasible solution: obj =            7
Run output...

Each 3rd 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 ,) and statistics on moves are displayed:

• mov is the total number of moves performed. Note that it is larger than the number of iterations since several searches are performed in parallel.
• inf is the rate of infeasible moves (moves leading to infeasible solutions)
• acc is the rate of accepted moves (moves leading to feasible solutions whose cost is accepted by the simulated annealing heuristic).
• imp is the total number of strictly improving moves. Note that it is cumulated over all parallel searches hence you can observe an increase of this number while the best objective function does not change (when one search is catching up with the others).

Remind that 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:

1. First line = the objective function
2. 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;

    // 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.
    local solFile = io.openWrite(solFileName);
    solFile.println(obj.value);
    for [p in 1..nbPositions][c in 1..nbClasses : cp[c][p].value]
        solFile.print(c - 1, " ");
    solFile.println();
}