Solving your first model¶

Knapsack toy model¶

Below is a LocalSolver Program (LSP) which models the following knapsack toy instance (see examples/toy): 8 items with weights 10, 60, 30, 40, 30, 20, 20, 2 and values 1, 10, 15, 40, 60, 90, 100, 15 respectively. The total weight must not exceed 102.

/********** toy.lsp **********/

/* Declares the optimization model. */
function model() {

    // 0-1 decisions
    x_0 <- bool(); x_1 <- bool(); x_2 <- bool(); x_3 <- bool();
    x_4 <- bool(); x_5 <- bool(); x_6 <- bool(); x_7 <- bool();

    // weight constraint
    knapsackWeight <- 10*x_0 + 60*x_1 + 30*x_2 + 40*x_3 + 30*x_4 + 20*x_5 + 20*x_6 + 2*x_7;
    constraint knapsackWeight <= 102;

    // maximize value
    knapsackValue <- 1*x_0 + 10*x_1 + 15*x_2 + 40*x_3 + 60*x_4 + 90*x_5 + 100*x_6 + 15*x_7;
    maximize knapsackValue;
}

/* Parameterizes the solver. */
function param() {
    lsTimeLimit = 1;
}

All the variables of the model, called expressions, are declared using left arrows <-. Decision variables are introduced using the built-in function bool(). Intermediate expression can be built upon these decision variables by using other operators or functions: product (*), sum (+), lower than or equal to (<=). Many other mathematical operators are available, allowing you to model and solve highly-nonlinear combinatorial optimization problems. The keywords constraint or maximize are used for tagging expressions as constrained or maximized.

To solve this model, call LocalSolver with the LSP file as argument. In addition, the value of the built-in programming variable lsTimeLimit is overwritten in order to limit the running time of the local-search solver to 1 second. Then, the following trace will appear in your console:

localsolver/examples/toy$ localsolver toy.lsp lsTimeLimit=2
LocalSolver 5.0 (Linux64, build 20141222)
Copyright (C) 2014 Innovation 24, Aix-Marseille University, CNRS.
All rights reserved (see Terms and Conditions for details).

Load toy.lsp...
Run model...
Preprocess model 100% ...
Close model 100% ...
Preprocessing transformed 3 expressions.
Run param...
Run solver...
Initialize threads 100% ...
Push initial solutions 100% ...

Model:
  expressions = 27, constants  = 11, operands = 50
  decisions = 8, constraints = 1, objectives = 1

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

Objectives:
  Obj 0: maximize, bound = 331

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


Phase 0:
[0 sec, 0 itr]: obj = (0)
[1 sec, 3031 itr]: obj = (280)
[2 sec, 68641 itr]: obj = (280)
[2 sec, 68641 itr]: obj = (280)
68641 iterations, 136816 moves performed in 2 seconds
Feasible solution: obj = (280)

If no time limit is set, the search will continue until you force the stop of the program by pressing Ctrl+C. The trace in console starts with the key figures of the model: number of expressions, operands, decisions, constraints and objectives. They are followed by the time limit with other default parameters (number of threads, simulated annealing level, ...). The trace about objectives and phases will be detailed later in the guide, when multiobjective optimization will be addressed.

Once the search is finished, the total number of iterations and the total number of moves are displayed (note that we can have more moves than iterations when using several threads), as well as the status and the value of the best solution found. The solution status can be Inconsistent, Infeasible, Feasible or Optimal.

Classical knapsack model¶

The previous model was very limited as it was not possible to solve arbitrary knapsack without changing the whole program. To read the knaspack instances from a formatted file, the LSP program can be modified as follows (see examples/knapsack).

/********** knapsack.lsp **********/

use io;

/* Reads instance data. */
function input() {
    local usage = "Usage: localsolver knapsack.lsp "
        + "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]";

    if (inFileName == nil) throw usage;

    local inFile = io.openRead(inFileName);
    nbItems = inFile.readInt();
    weights[i in 0..nbItems-1] = inFile.readInt();
    prices[i in 0..nbItems-1] = inFile.readInt();
    knapsackBound = inFile.readInt();
}

/* Declares the optimization model. */
function model() {
    // 0-1 decisions
    x[i in 0..nbItems-1] <- bool();

    // weight constraint
    knapsackWeight <- sum[i in 0..nbItems-1](weights[i] * x[i]);
    constraint knapsackWeight <= knapsackBound;

    // maximize value
    knapsackValue <- sum[i in 0..nbItems-1](prices[i] * x[i]);
    maximize knapsackValue;
}

/* Parameterizes the solver. */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 20; 
}

/* Writes the solution in a file */
function output() {
    if(solFileName == nil) return;
    local solFile = io.openWrite(solFileName);
    solFile.println(knapsackValue.value);
    for [i in 0..nbItems-1 : x[i].value == 1]
        solFile.print(i + " ");
    solFile.println();
}

By launching it with the following command line, you will obtain an output similar to the previous model. Note that for more flexibility, we have defined some of our variables in command line (inFileName, lsTimeLimit).

localsolver/examples/knapsack$ localsolver knapsack.lsp inFileName=instances/toy.in lsTimeLimit=1

All mathematical operators can be both used for modeling and for programming. For instance, the statement c <- a * b means that we declare a modeling expression c corresponding to the product of the modeling expressions a and b, while c = a * b means that we assign to the programming variable c the result of the product of the programming variables a and b. For n-ary operators, the n-ary functional form (for example sum(a, b, c)) allows to declare expressions with an arbitrary number of operands. When the number of operands is fixed, the binary infix form (for example a + b + c) can also be used. For example, the statement:

knapsackWeight <- sum[i in 0..nbItems-1](weights[i] * x[i]);

declares the expression knapsackWeight as the sum of the product of expressions weights[i] and x[i] for all items from 0 to nbItems-1.

As explained in the introduction to LocalSolver’s modeler, a singularity of the LSP language is to offer no main function. the LSP language induces a modeling framework composed of 5 predefined functions input(), model(), param(), display(), output(). These functions, called in this order, induce the flow of the program launched by the LocalSolver executable:

• input: for declaring your data or reading them from files.
• model: for declaring your optimization model.
• param: for parameterizing the local-search solver before running.
• display: for displaying some info in console or in some files during the resolution.
• output: for writing results in console or in some files, once the resolution is finished.

These 5 predefined functions have a default implementation. So you only have to implement and write the functions you need (At least, the function model()).