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