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).

Download Current version: 0.1 (Dec 4, 2013)

Language

We provide a short description of the Optal language.

The benefits of using Optal are:

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
Reading problem data from `test.lp'...
4 rows, 2 columns, 6 non-zeros
2 integer variables, none of which are binary
14 lines were read
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...
+     3: mip =     not found yet <=              +inf        (1; 0)
+     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