# Optal

A language for linear optimization.

Optal is a language designed to easily describe linear optimisation problems.

We provide a compiler to translate this language into an LP file, when given a set of data in the JSON format. The LP file can be used by many optimization engines to solve the problem.

Our compiler is free-software (GPLv3).

Current version: 0.1 (Dec 4, 2013)

## Language

We provide a short description of the Optal language.

The benefits of using Optal are:

• A more expressive language for constraints
• A separation of the problem and the data
• Data files are in JSON format

## A Simple Example

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

This problem can be described with the following Optal program (that we store in test.opl):

dvar int Production[Products]

maximize sum(p in Products) Profit[p] * Production[p]

constraints {
forall(prod in Production) prod >= 0;
sum(p in Products) Need[p].time * Production[p] <= 5 * 7;
sum(p in Products) Need[p].wood * Production[p] <= 30;
}

We can provide a JSON data file in test.json:

{ "Products" : [ "soldier", "train" ],
"Profit" : { "soldier" : 3, "train" : 2 },
"Need" : { "soldier" : { "wood" : 1, "time" : 1.85 },
"train" :   { "wood" : 1, "time" : 1 } } }

We can now use the optal compiler to generate an LP file for our solver:

% optal test.json test.opl  > test.lp

The generated file looks like:

Maximize
3. Production_soldier + 2. Production_train

Subject to
Production_train >= 0
Production_soldier >= 0
1.85 Production_soldier + Production_train <= 35.
Production_soldier + Production_train <= 30.

Integer
Production_train
Production_soldier

End

Finally, we can call a solver (here, glpsol provided by the Debian glpk package):

glpsol --lp test.lp -o test.result

The output is:

GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
--lp test.lp -o test.result
4 rows, 2 columns, 6 non-zeros
2 integer variables, none of which are binary
GLPK Integer Optimizer, v4.45
4 rows, 2 columns, 6 non-zeros
2 integer variables, none of which are binary
Preprocessing...
2 rows, 2 columns, 4 non-zeros
2 integer variables, none of which are binary
Scaling...
A: min|aij| =  1.000e+00  max|aij| =  1.850e+00  ratio =  1.850e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 2
Solving LP relaxation...
GLPK Simplex Optimizer, v4.45
2 rows, 2 columns, 4 non-zeros
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
*     3: obj =   6.588235294e+01  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     5: >>>>>   6.500000000e+01 <=   6.500000000e+01   0.0% (5; 0)
+     5: mip =   6.500000000e+01 <=     tree is empty   0.0% (0; 9)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.1 Mb (64671 bytes)
Writing MIP solution to `test.result'...

and the solution, available in test.result:

Problem:
Rows:       4
Columns:    2 (2 integer, 0 binary)
Non-zeros:  6
Status:     INTEGER OPTIMAL
Objective:  obj = 65 (MAXimum)

No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
1 r.5                        22             0
2 r.6                         7             0
3 r.7                     34.95                          35
4 r.8                        29                          30

No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
1 Production_soldier
*              7             0
2 Production_train
*             22             0

Integer feasibility conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality

End of output

## Compilation and Installation

First, we need to install the dependencies, using the OPAM package manager:

opam install uutf jsonm menhir
opam install ocp-build

Now, we can compile optal:

ocp-build -init
ocp-build

We can now install the binary:

cp _obuild/optal/optal.asm /usr/local/bin/optal

## Resources

 Optal on GitHub Git Repository of the Optal compiler on GitHub Optal Issues Optal Bug Tracker Optal Releases Optal Source Archives