Mathematical modeling features

Decision variables

LocalSolver makes a clear distinction between decision variables and intermediate expressions. A decision variable is a variable that cannot be deduced or computed from other variables or expressions. The question to ask when you use LocalSolver is What are the most atomic decisions I want to take?

This aspect can be a bit disturbing compared to other optimization techniques such as linear programming or constraint programming but it is really crucial for the performance of the underlying local search and algorithms. For example, on the previous knapsack problem, the only decisions are the boolean variables x[i] equal to 1 if the object i is in the bag or 0 otherwise. On the opposite, the total weight of elements in the bag, defined as sum[i in 0..nbItems-1](values[i] * x[i]) is a typical intermediate expression: its value can be deduced from decision variables.

There are three kinds of decisions in LocalSolver. You have already seen booleans in the previous pages. The two other kinds of decisions are floating quantities and integer quantities.

Boolean decisions

Boolean decisions can take two values 0 or 1. They are declared using the built-in function bool() that returns a new binary decision. Booleans enables you to model any problem where a binary decision is involved (such as the knapsack problem). Most of combinatorial optimization problems (assignment, allocation, packing, covering, partitioning, routing, scheduling, etc.) can be simply expressed as pure 0-1 models.

To have an idea of what it is possible with boolean decisions, have a look at our Example tour.

Floating-point decisions

Floating-point decisions are used to model continuous quantitative decisions taking values in a given range. They are declared using the built-in function float(a,b) that returns a floating-point decision with range [a,b]. The largest range of a floating-point decision is defined by the IEEE 754 double-precision floating-point format, which is roughly [-10^307, 10^307].

Integer decisions

In a similar way, integer decisions are used to model integer quantitative decisions taking values in a given range. They are declared using the built-in function int(a,b) that returns an integer decision with range [a,b]. The largest range of an integer decision is [-2^63, 2^63-1], which is roughly [-10^18, 10^18].

Constraints

A constraint is a kind of tag put on an expression that enforces it to be true (1). In LocalSolver, any variable or intermediate expression that has a boolean value (0, 1) can be constrained. Thus, ‘’all’’ expressions involving relational operators (<, <=, >, >=, ==, !=) but also logical and (&&), or (||), xor or immediate if (iif) can be constrained without limitation on the type of the problem. In particular, LocalSolver is not limited to linear constraints but can also handle highly-nonlinear models.

To tag an expression as a constraint in the modeler, simply prefix it by the keyword constraint. You cannot constrain the same expression twice:

// These two formulations are equivalent
constraint knapsackWeight <= 102;
weightCst <- knaspackWeight <= 102;
constraint weightCst;

Try to avoid hard constraints as much as possible, because LocalSolver (and more generally local search) is not suited for solving hardly constrained problems. In particular, banish constraints that are not surely satisfied in practice. Ideally, only combinatorial constraints (that is, the ones which induce the combinatorial structure of your problem) have to be set. All the other constraints can be relaxed as primary objectives in order to be “softly” satisfied (goal programming). LocalSolver offers a feature making this easy to do: lexicographic objectives.

Objectives

At least one objective must be defined using the keyword minimize or maximize. Any expression can be used as objective. If several objectives are defined, they are interpreted as a lexicographic objective function. The lexicographic ordering is induced by the order in which objectives are declared. In this way, expressions frequently encoutered in math programming models like:

maximize 10000 revenues - 100 resources + desiderata;

in order to first maximize revenues, then minimize resources, and ultimately maximize desiderata can be avoided. Indeed, you can directly write:

maximize revenues;
minimize resources;
maximize desiderata;

Table of available operators and functions

  Function Description Arguments type Result type Arity Symb
Decisional bool Boolean decision variable with domain {0,1} none bool 0  
float Float decision variable with domain [a, b] 2 doubles double 2  
int Integer decision variable with domain [a, b] 2 integers int 2  
list Collection of integers within a range [0, n - 1] 1 integer collection 1  
Arithmetic sum Sum of all operands bool, int, double int, double n >= 0 +
sub Substraction of the first operand by the second one bool, int, double int, double 2 -
prod Product of all operands bool, int, double int, double n >= 0 *
min Minimum of all operands bool, int, double int, double n > 0  
max Maximum of all operands bool, int, double int, double n > 0  
div Division of the first operand by the second one bool, int, double double 2 /
mod Modulo: mod(a, b) = r such that a = q * b + r with q, r integers and r < b. bool, int int 2 %
abs Absolute value: abs(e) = e if e >= 0, and -e otherwise bool, int, double int, double 1  
dist Distance: dist(a, b) = abs(a - b) bool, int, double int, double 2  
sqrt Square root bool, int, double double 1  
cos Cosine bool, int, double double 1  
sin Sine bool, int, double double 1  
tan Tangent bool, int, double double 1  
log Natural logarithm bool, int, double double 1  
exp Exponential function bool, int, double double 1  
pow Power: pow(a, b) is equal to the value of a raised to the power of b. bool, int, double double 2  
ceil Ceil: round to the smallest following integer bool, int, double int 1  
floor Floor: round to the largest previous integer bool, int, double int 1  
round Round to the nearest integer: round(x) = floor(x + 0.5). bool, int, double int 1  
scalar Scalar product between 2 arrays. array int, double 2  
piecewise Piecewise linear function product between 2 arrays. array, int double double 3  
Logical not Not: not(e) = 1 - e. bool bool 1 !
and And: equal to 1 if all operands are 1, and 0 otherwise bool bool n >= 0 &&
or Or: equal to 0 if all operands are 0, and 1 otherwise bool bool n >= 0 ||
xor Exclusive or: equal to 0 if the number of operands with value 1 is even, and 1 otherwise bool bool n >= 0  
Relational eq Equal to: eq(a, b) = 1 if a = b, and 0 otherwise bool, int, double bool 2 ==
neq Not equal to: neq(a, b) = 1 if a != b, and 0 otherwise bool, int, double bool 2 !=
geq Greater than or equal to: geq(a, b) = 1 if a >= b, 0 otherwise bool, int, double bool 2 >=
leq Lower than or equal to leq(a, b) = 1 if a <= b, 0 otherwise bool, int, double bool 2 <=
gt Strictly greater than: gt(a, b) = 1 if a > b, and 0 otherwise. bool, int, double bool 2 >
lt Strictly lower than: lt(a, b) = 1 if a < b, and 0 otherwise. bool, int, double bool 2 <
Conditional iif Ternary operator: iif(a, b, c) = b if a is equal to 1, and c otherwise bool, int, double bool, int, double 3 ?:
array + at T[i] returns the i th value in array T. array, int bool, int, double 2 []
Set related count Returns the number of elements in a collection. collection int 1  
indexOf Returns the index of a value in a collection or -1 if the value is not present. collection, int int 2  
contains Returns 1 if the collection contains the given value or 0 otherwise. collection, int bool 2  
partition Returns true if all the operands form a partition of their common domain. collection bool n > 0  
disjoint Returns true if all the operands are pairwise disjoint. collection bool n > 0  
Other call Call an external native function. It can be used to implement your own operator. bool, int, double double n > 0