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 important
for the performance of the underlying algorithms. For example,
in a 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: booleans, 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 (equal to 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
.
// These two formulations are equivalent
constraint knapsackWeight <= 102;
weightCst <- knaspackWeight <= 102;
constraint weightCst;
# These two formulations are equivalent
model.constraint(knapsackWeight <= 102)
weightCst = knaspackWeight <= 102
model.constraint(weightCst)
// These two formulations are equivalent
model.constraint(knapsackWeight <= 102);
weightCst = knaspackWeight <= 102;
model.constraint(weightCst);
// These two formulations are equivalent
model.Constraint(knapsackWeight <= 102);
weightCst = knaspackWeight <= 102;
model.Constraint(weightCst);
// These two formulations are equivalent
model.constraint(knapsackWeight <= 102);
weightCst = model.leq(knaspackWeight, 102);
model.constraint(weightCst);
A good practice in operations research is to only model as constraints requirements that are strictly necessary. If a requirement may be violated in some exceptional cases then it is better modeled as a 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;
model.maximize(revenues)
model.minimize(resources)
model.maximize(desiderata)
model.maximize(revenues);
model.minimize(resources);
model.maximize(desiderata);
model.Maximize(revenues);
model.Minimize(resources);
model.Maximize(desiderata);
model.maximize(revenues);
model.minimize(resources);
model.maximize(desiderata);
Table of available operators and functions¶
In the table below, each operator is identified with its name in the LSP language. Note that in Python, C++, C# or Java these names may slightly differ in order to respect coding conventions and reserved keywords of each language:
- In C++ and Java, decisions are suffixed with “Var” (boolVar, floatVar, intVar, setVar and listVar)
- in C# all functions start with a capital letter
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 | ||
cover | Returns true if all the operands form a cover of their common domain. | collection | bool | n > 0 | ||
Other | call | Call a function. It can be used to implement your own operator. | bool, int, double | double | n > 0 |