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 = 10;
}

All the variables of the model, called expressions, are declared using left arrows <-. Decision variables are introduced using the built-in function bool() (or also int(), float(), set(),``list()``). Intermediate expression can be built upon these decision variables by using other operators or functions. For example, in the model aboce: product (*), sum (+), less 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. Then, the following trace will appear in your console:

localsolver/examples/toy$ localsolver toy.lsp
LocalSolver 9.0.20190611-Win64. All rights reserved.
Load toy.lsp...
Run model...
Preprocess model 100% ...
Run param...
Run solver...
Initialize solver 100% ...
Push initial solutions 100% ...

Model:   expressions = 38,   decisions = 8  constraints = 1, objectives = 1,
Param:   time limit = 10 sec, no iteration limit

[ optimization direction  ]          maximize

[  0 sec,       0 itr]: obj    =            0
[  0 sec,       2 itr]: obj    =          280

2 iterations performed in 0 seconds

Optimal solution:
  obj    =          280
  gap    =           0%
  bounds =          280

If no time limit is set, the search will continue until optimality is proven (Optimal solution message) or 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, decisions, constraints and objectives.

Once the search is finished, the total number of iterations and the elapsed time are displayed, 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()).