Description of the Optal Language

Short Tutorial

Describing Optimization Goals

The minimal thing needed to describe a problem is a goal.

minimize 3 + 4

This describes an expression to be minimized. It is also possible to ask for maximization.

maximize 3 + 4

This is a particularily uninteresting problem since the objective is a constant, hence there is nothing to optimize. To define the search space, we need variables.

dvar float x
maximize x

This tells that there is a variable x which has a value in the real set. This won't also provide any insightfull result since there is no maximal value for reals. To limit the search space we can add constraints.

dvar float x
maximize x
constraints {
  x <= 3
}

By constraining x to be lower than 3, the problem has an optimal solution, that appens to be for x = 3. We now have seen the 3 main parts of an optal script: the names declarations, the goal and the constraints. They must appear in that order.

Simple production problem

Giapetto wants to know how many numbers of wooden trains and soldiers he should build each week to maximize its profit.

// Giapetto build and sell wooden trains and soldiers
dvar int soldier
dvar int train

/* He wants to maximize its profit.
   A soldier costs 3¤ and a train 2¤. */
 maximize 3 * soldier + 2 * train

constraints {
  // He builds a positive number of soldiers and trains
  soldier >= 0;
  train >= 0;

  /* He has a finite amount of time: he works 5 days per week
     and works 7 hours per day.
     A train takes 1 hour to build and soldiers, a bit more */
  1.85 * soldier + train <= 5 * 7 ;

  /* A soldier and a train takes 1 unit of wood to build and
     giapetto buys 30 each week */
  soldier + train <= 30;
}

Using iterators

It is possible to use forall and sum keywords to simplify big scripts. forall allows to define a set of constraints, sum simplifies writing big constraints. More details on those syntax is explained later.

dvar int soldier
dvar int train

alias Products = < soldier, train >
// an array containing the variables soldier and train
alias Times = < 1.85, 1 >
alias Wood = < 1, 1 >
alias Profit = < 3, 2 >
alias index = indexOf(Products)
// the array <0, 1>, used to iterates on other arrays

maximize sum(i in index) Profit[i] * Products[i]
// Profit[0] * Product[0] + Profit[1] * Product[1]

constraints {
  forall(prod in Products) prod >= 0;
  // Products[0] >= 0 && Products[1] >= 0
  sum(i in index) Times[i] * Products[i] <= 5 * 7;
  sum(i in index) Wood[i] * Products[i] <= 30;
}

The Optal Language : a Reference

Comments

OPTAL has C style comments with /* */ and //.

/* a comment /* some imbricated comment */ end of the comment */

maximize 1 // the end of the line is a comment

Basic types

The basics types of OPTAL are: bool, int, floats, linear expression and linear constraints.

Integers

Integers expressions are integer constants and operator between integers.

6 * (1 + 3) - 5

Division is not allowed between integers.

Floats

Floats expressions are float constants and operators between floats.

6. * (1.3 + 3.) - 5.2 / 12.2

operators between integers and floats are authorised and behave as operation on floats.

Bool

The basics boolean expressions are the constants true and false, and combinations using not && and ||

true || false && not false

Arithmetic expressions on booleans are authorized and converted to integers, false is converted to 0 and true to 1. Boolean expressions are also the results of comparison between integers, floats and booleans. Those are true expressions

1 <= 2
2 == 2
4 >= 3
3 != 2
3 < 3.1
true > false

Linear expressions

Basic linear expressions are constant integers or floats, or variables declared by

dvar float some_float_var
dvar int some_int_var
dvar bool some_bool_var

arithmetic expressions between linear expression and float or ints are linear expressions.

3 * some_float_var
 2. + some_int_var

Sum and difference between linear expressions are linear expressions.

3 * some_float_var + 2 * some_int_var - some_bool_var

Notice that product of linear expressions are forbidden.

Linear constraints

Linear constraints are the results of comparison between linear expression.

3 * some_float_var <= 2 * some_int_var
3 * some_float_var == 3
3 * some_float_var >= 3

Comparisons using != > and < are not authorised. Linear constraints can be combined using &&

3 * some_float_var <= 2 * some_int_var &&
3 * some_float_var >= 3

symbols

Symbols are names declared by the syntax

`symbol

Structured types

OPTAL has 2 types of structured types, arrays and maps.

Arrays

Arrays are dense integer indexed data. Arrays can be built using the syntax:

< 1, 2, 3 >

Access to array elements is done through the syntax

< 1, 2, 3 >[1]

This returns 2, the first index is 0.

Maps

Maps are sparse data indexed by any value, but are accessible using symbols. Maps indexed by symbols can be declared using the syntax:

{ name1 : 3, name2 : 4 }

Access to symbol indexed maps is done through the syntax

{ name1 : 3, name2 : 4 }.name1

Maps indexed by other types than symbols can be accessed through the [] syntax.

{ name1 : 3, name2 : 4 }[`name1]

For instance if map is indexed by arrays of size 2, it can be accessed using.

map[<1,2>]

Patter operators

Sum

Sum allows to evaluate an expression for each elements of an array or and object and do the sum of the results.

sum(x in <1,2,3>) (x * 3)

or

sum(x in {a:1,b:2,c:3}) (x * 3)

are equivalent to

(1 * 3) + (2 * 3) + (3 * 3)

The parameter of sum is a set of patterns binding variables names to values.

sum(x in <1,2>, y in <3,4>) (x + y)

wich is equivalent to

sum(x in <1,2>) sum(y in <3,4>) (x + y)

or

sum(x, y in <1,2>) (x + y)

is equivalent to

sum(x in <1,2>) sum(y in <1,2>) (x + y)

A single pattern can bind multiple variables:

sum(<x,y> in <<1,3>, <2,4>>) (x + y)

is

sum(x in <1,2>) sum(y in <3,4>) (x + y)

Patterns can be constrained. The expression is evaluated only when the constraint is satisfied.

sum(x in <1,2,3>: x != 2) x * 3

is equivalent to

(1 * 3) + (3 * 3)

It is possible to use implicit equality constraints

sum(x in <1,2>, x <2,3>) (x * 3)

is equivalent to

sum(x in <1,2>, y <2,3>: x == y) (x * 3)

Forall

Forall is like sum but the union operator is && instead of +.

forall(x in <1,2>) (x >= 2)

is

(1 >= 2) && (2 >= 2)

Other functions

range

The range binary operator takes two integers (a,b) and returns the array of integers between a and b.

1 .. 3

is the array

 <1, 2, 3> 

indexOf

The indexOf function takes an array or a map and returns the array of the index. If arr is an array or a map.

sum(x in indexOf(arr)) arr[x]

is equivalent to

sum(x in arr) x

Max

Max returns the biggest value of an integer collection.

Max(<1,2,3>)

is 3

Last

Returns the last index of an array, i.e. the length - 1

Last(<0,0,0>)

is 2

Alias

It is possible to declare some alias for expressions

alias x = 3 * 4

alias y = x + 2

It is not possible to redeclare already declared variables.

Variables

Linear variables can be declared by the dvar keyword with a type associated.

dvar float some_float_var

A set of variables can be declared by the syntax

dvar float var_set[set]

If set is a collection containing integers var_set is an array indexed by the elements of set, otherwise it will be a map. For arrays, index must be consecutive and starting with 0.