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 five kinds of decisions in LocalSolver. You have already seen booleans in the previous pages. The four other kinds of decisions are floating quantities, integer quantities, set variables and list variables.
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+1, 2^63-1], which is roughly
[-10^18, 10^18].
Set and list decisions¶
Set and list decisions allow defining decision variables whose value is a
collection of integers within a domain [0, n-1]
where n is the unique
operand of the operator. See our documentation
on collection variables for details.
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 | Ordered collection of integers within a range [0, n - 1] | 1 integer | collection | 1 | ||
set | Unordered 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 a function. It can be used to implement your own operator. | bool, int, double | double | n > 0 |