Mathematical modeling features

Decision variables

Hexaly Optimizer 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 Hexaly Optimizer 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](values[i] * x[i]) is a typical intermediate expression: its value can be deduced from decision variables.

There are six kinds of decisions in Hexaly Optimizer: booleans, floating quantities, integer quantities, intervals, 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.

Interval decisions

Interval decisions are used to model the time range of an event. They are declared using the built-in function interval(minStart, maxEnd), where the bounds are integers representing the minimum start and the maximum end of the decision. The start is inclusive and the end is exclusive.

Constraints

A constraint is a kind of tag put on an expression that enforces it to be true (equal to 1). In Hexaly Optimizer, 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, Hexaly Optimizer 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). Hexaly Optimizer 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 Hexaly Modeler. 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

interval

Interval decision variable with domain [minStart, maxEnd)

2 integers

interval

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. Takes value 1 when applied to an empty collection.

bool

bool

n >= 0

&&

or

Or: equal to 0 if all operands are 0, and 1 otherwise. Takes value 0 when applied to an empty collection.

bool

bool

n >= 0

||

xor

Exclusive or: equal to 0 if the number of operands with value 1 is even, and 1 otherwise. Takes value 0 when applied to an empty collection.

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. In case of intervals: gt(a, b) = 1 if start(a) >= end(b), and 0 otherwise.

bool, int, double, interval

bool

2

>

lt

Strictly lower than: lt(a, b) = 1 if a < b, and 0 otherwise. In case of intervals: lt(a, b) = 1 if end(a) <= start(b), and 0 otherwise.

bool, int, double, interval

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

?:

Set related

count

Returns the number of elements in a collection.

collection, interval, array

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 or interval, 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

array

Creates an array of fixed or variadic size.

bool, int, double, array, list, set

array

n >= 0

stepArray

Creates an stepArray of fixed size.

bool, int, double

array

n >= 1

at

Returns the value in an array or a list at a specified position.

array, list, int

bool, int, double

n >= 2

[]

find

Returns the position of the first collection containing the given element in the array, or -1 if the value is not present.

array, int

int

2

sort

Returns the array sorted in ascending order. When used with two arguments, the array is sorted based on the values returned by the lambda.

array, lambda

array

1 or 2

distinct

Returns the unordered set of distinct values in an array. When used with two arguments, the distinct values are based on the values returned by the lambda applied to the iterable.

array, list, set, interval, lambda

set

1 or 2

intersection

Returns the unordered set of values present in both iterables.

array, list, set

set

2

Interval related

start

Returns the start of a non-void interval.

interval

int

1

end

Returns the end of a non-void interval.

interval

int

1

length

Returns the length of a non-void interval, equivalent to end(interval) - start(interval).

interval

int

1

hull

Returns the smallest interval including all the intervals given in operands.

interval

interval

n >= 0

Other

call

Call a function. It can be used to implement your own operator.

bool, int, double

double

n > 0