README.md

ONumerical

OCaml library featuring:

• Sparse Linear Expressions

  Functorized module for dealing with linear expressions over any number type and over any variable type (Zarith rationals, floats, integers for numbers and strings for variables are supported out-of-the-box):

       module Expression = Expression_f.Make(Str_var)(Float_number);;
       let a = Expression.of_assoc_list_and_const
           [("x", 1.0), ("y", 1.0)] 0.0;;
       let b = Expression.of_assoc_list_and_const
           [("x", -1.0), ("z", 3.0)] 5.0;;
       Expression.(to_string (a ++ b));;
       (* Output: 1 (y) + 3 (z) + 5 *)
   

• Generic vectors, represented using arrays:

       module Vector = Vector_f.Make(Float_number);;
       let a = [| 0.0; 3.0; 4.0 |];;
       let b = [| 2.0; 8.0; 2.0 |];;
       Vector.(to_string (a -- b));;
       (* Output: [-2.0    -5.0    2.0] *)
   

• Generic matrixes represented using arrays:

       module Matrix = Matrix_f.Make(Float_number);;
       let a = [|
           [|2.0; 3.0; 4.0|];
           [|1.0; 9.0; 1.0|];
           [|0.5; -1.0; 0.0|];
       |];;
        let b = [|
           [|2.0; 3.0; 4.0|];
           [|3.0; 6.0; 3.0|];
           [|0.5; -1.0; 3.0|];
       |];;
       Matrix.(to_string (a *** b))
       (* Output:
       | 15.0    20.0    29.0|
       | 29.5    56.0    34.0|
       |-2.0     -4.5     1.0|
       *)
   

• Dual Simplex Solver on expressions:

  Solves linear optimization problems which are dual-feasible.

       module Solver = Opt_solver_f.Make(Str_var)(Float_number)
       module Expression = Solver.Expression
       let constraints = [
           ([("x1", -1.0); ("x2", -1.0); ("x3", 2.0)], 3.0);
           ([("x1", -4.0); ("x2", -2.0); ("x3", 1.0)], 4.0);
           ([("x1", 1.0); ("x2", 1.0); ("x3", -4.0)], -2.0);
       ];;
       let opt_problem = Solver.of_constraints_and_objective
           (List.map constraints ~f:(fun (coeffs, const) -> (
               Opt.LessThanZero,
                   (Expression.of_assoc_list_and_const coeffs const)
           )))
           (Opt.Maximize
               Expression.of_assoc_list_and_const
                   [("x1", -4.0); ("x2", -2.0); ("x3", -1.0)]
                   0.0
           );;
       let Opt.Solution solution = Opt.solve opt_problem;;
       solution.primal_var_assignment
       (* output: [("x1", 0.0); ("x2", 4.0, "x3", 0.5)] *)
   

Sample Application: Balancing Chemical Equations

There is a typical problem in high-school chemistry: balance (add coefficients to) a reaction equation. For example we start with a simple equation

H2S + O2 -> H2O + SO2

And we wish to obtain the balanced version

2 H2S + 3 O2 -> 2 H2O + 2 SO2

While for the simple reactions the problem is trivial enough to be given as a homework, the solution in the general case requires the application of a simplex method (minimize the sum of all constraints subject to balancing atoms on left and right hand side and subject to the strict positivity constraint).

Moreover, since we want to minimize the quantity with no negative coefficients the problem is dual-feasible. The solution is implemented as a sample application of ONumerical, and can be launched as a standalone executable:

    echo "H2S + O2 -> H2O + SO2" | ./chem_balancer.native
    2H2S + 3O2 -> 2H2O + 2SO2

Compiling and Installation

Compiling:

$ make

Installation:

$ make install

To remove:

$ make remove

Running tests:

$ make run_test

Compiling the balancer:

$ make chem_balancer
$ ./chem_balancer # to run

Dependencies

• Dolog
• OCamlbuild for complilation
• Core
• Re2
• OUnit if you want to run unit tests

NOTE

Dual Simplex uses a very inefficient dense representation and is not optimized for performance. So are the linear algebra primitives, as they re-create the data-structure after each operation.