ROOC ‐ Documentation

Welcome to the ROOC documentation!

What it is

Rooc is a language / solver of mathematical models. Using the rooc syntax you are able to formalize a model and have the compiler automatically create a static model from constants data that you provide. The transformers will then have the job to transform the model into specific formats that can be used by the solvers to find an optimal solution.

How to use it

A problem can be formulated as:

<min/max> <expression>
s.t
   <conditions>
where 
   <declarations>

where the min/max expression and the conditions are required, and the declartions are optional

Declarations

In this part of the formulation you can assign primitive values to variables, below is the syntax and type for each primitive

string = "hello world"
number = 10
boolean = true
array = [1,2,3] //can be an array of any primitive value
nested = [
    [1,2,3],
    [4,5,6],
    [7,8,9] //same as a single array, can be infinitely nested with values
]
graph = Graph {
    A -> [B, C], //implicitly has edge cost of 1
    B -> [C:10], //edge cost can be specified by Name:Value 
    C
}

Other internal primitives are Undefined and Tuple which cannot be (currently) defined manually

Conditions

A condition is in the form

<exp> <relation> <exp> <for_iteration>

where relation can be any of <= >= = and the for iteration is an expansion rule that expands a condition in multiple conditions, it will be explained at the end

Expression

Variables

Declare variables simply by simply writing it's name

x

Compound variables

This is a special type of variable, it uses the special character _ to define indices that will be expanded to form a variable, for this reason, any variable that has one or more _ in it, will be considered a compound variable, look after to see the usage in scopes

x_i

Min / Max

Defines the min and max functions over a set of expressions:

min { x / 6, y * 10, z + 2}

Binary and unary operators

The most common binary operators, the same as any language:

• - minus
• + plus
• * times
• \ divs

Also supports unary operators, currently only -

Mod

mod function, which calculates the absolute value

| x + y - 10 |

Sum

This is the most interesting expression, it calculates the sum over a certain expression, and creates values which are available inside it's scope by using the variables defined inside the sum iterator

sum(i in 0..5) { i }

will be unrolled to:

0 + 1 + 2 + 3 + 4

This is where compound variables are useful, by declaring the variable i inside the sum block, we can define a compound variable x_i which will be flattened to the value of i:

sum(i in 0..3) { x_i }

will be unrolled to:

x_0 + x_1 + x_2

For a compound variable to be flattened, all of it's indices need to be declared in it's scope, and they must be either a string, number, or a named value (like a graph node). sum blocks can iterate over any iterable or iterator in the language. You can define multiple iterators, and they will behave like nested sums:

sum(i in 0..2, j in 0..3) { x_i_j }

will be unrolled to:

x_0_0 + x_0_1 + x_0_2 + x_1_0 + x_1_1 + x_1_2 

Range iterator

Defined as from..to for an exclusive range, or from..=to for an inclusive range, it will create an iterator of numbers going from to to, those values must be numbers or something that has a numeric value:

0..5
0..=3
0..len(C)
0..x

Iterable

Some primitives are iterable, for example arrays or it's rows, for example:

min x
s.t
    sum(i in C) { i } <= x
where 
   C = [1,2,3]

most functions in the language return an iterable, they will be talked about soon

Tuples

Tuples can be used inside sum blocks to destructure a tuple return type of function or spreadable type, for example, the edges(G) function returns a GraphEdge list, where GraphEdge can be destructured to a tuple. Another example is the enumerate(C) function that returns the array value plus it's index:

min sum((el, i) in enumerate(C)) { el * x_i }
s.t
    sum((u, c, _) in edges(G)) { x_u * c }

where 
    C = [1,2,3,4]
    G = Graph {
      a -> [b: 10]
      b
    }

Values inside tuples can be ignored by using the _ identifier

Functions

the language predefines a set of functions to work over the primitives, they accept parameters and have a return value, the current functions are:

• len(C): accepts an array or iterable type and returns it's length
• enumerate(C): accepts an array or iterable type and returns it's elements mapped to their position in the array/iterable, it can be then destructured as: (value, index)
• range(from, to, inclusive): just like the range syntax (they are equivalent), it accepts a number, number and boolean value, returns an iterator over the range
• nodes(G): accepts a graph as parameter and returns a list of it's nodes
• neigh_edges(n): accepts a node and returns a list of it's edges, which can be spread, the edge is spread as (string, number, string) this being (from_node, cost, to_node)
• neighs_of(G, n): accepts a graph and node name (string) and returns the a list of edges which are the neighbours of the node n

For condition

Conditions can also have a for iterator, that will flatten a condition into multiple conditions, iterating over one or more iterators (just like the sum)

    sum((j, jin) in enumerate(C[i])) { j * x_i_jin } <= x_i for i in 0..len(C)
where
    C = [
        [1,0,0],
        [0,1,0], 
        [0,0,1]
    ]

will be flattened to:

1 * x_0_0 + 0 * x_0_1 + 0 * x_0_2 <= x_0
0 * x_1_0 + 1 * x_1_1 + 0 * x_1_2 <= x_1
0 * x_2_0 + 0 * x_2_1 + 1 * x_2_2 <= x_2

Examples

iterating over a bidimensional array:

    sum(row in C, el in row) { el } <= 0
    sum(i in 0..len(C), el in C[i]) { el } <= 0
    sum(i in 0..len(C), j in 0..len(C[i])) { C[i][j] } <= 0
where
    C = [
        [1,0,0],
        [0,1,0], 
        [0,0,1]
    ]

Dominating set

min sum(u in nodes(G)) { x_u }
s.t. 
    x_v + sum((_, _, u) in neigh_edges(v)) { x_u } >= 1    for v in nodes(G)
where
    G = Graph {
        A -> [B, C, D, E, F],
        B -> [A, E, C, D, J],
        C -> [A, B, D, E, I],
        D -> [A, B, C, E, H],
        E -> [A, B, C, D, G],
        F -> [A, G, J],
        G -> [E, F, H],
        H -> [D, G, I],
        I -> [C, H, J],
        J -> [B, F, I]
    }

It is compiled down to:

min x_A + x_B + x_C + x_D + x_E + x_F + x_G + x_H + x_I + x_J
s.t
        x_A + x_B + x_D + x_C + x_F + x_E >= 1
        x_B + x_D + x_E + x_J + x_C + x_A >= 1
        x_C + x_B + x_D + x_I + x_A + x_E >= 1
        x_D + x_E + x_H + x_C + x_A + x_B >= 1
        x_E + x_B + x_D + x_C + x_A + x_G >= 1
        x_F + x_J + x_G + x_A >= 1
        x_G + x_E + x_F + x_H >= 1
        x_H + x_D + x_I + x_G >= 1
        x_I + x_J + x_H + x_C >= 1
        x_J + x_F + x_I + x_B >= 1