This library helps the modeling of Linear Programming (LP) and Mixed Integer Programming (MIP) in OCaml. It supports the model with not only linear terms, but also quadratic terms. The model can be imported-from / exported-to CPLEX LP file format, which can be loaded by various solvers. It also has direct interfaces to some solvers. Currently supported are GLPK (GNU Linear Programming Kit), HiGHS, and Gurobi.

The recommended way to install this library is with opam. Pinning the dev-repo is optional but recommended.

opam pin lp --dev-repo
opam pin lp-glpk --dev-repo
# If your application is based on js_of_ocaml:
opam pin lp-glpk-js --dev-repo
# If you want to use HiGHS (build and install it first as described below):
opam pin lp-highs --dev-repo
# If you have access to Gurobi:
opam pin lp-gurobi --dev-repo

If opam pin <package-name> --dev-repo does not work, you can also try:

opam pin add <package-name> git+https://github.com/ktahar/ocaml-lp.git

For development, clone this repository and use local path pins:

# 1. Install dependencies from local opam files:
opam install . --deps-only --with-test --with-dev-setup
# 2. Pin packages you want to develop to the current checkout:
opam pin add lp .
opam pin add lp-glpk .
opam pin add lp-glpk-js .
opam pin add lp-highs .
opam pin add lp-gurobi .
# 3. Build and run tests:
# If HiGHS is installed under `~/.local`, export `HIGHS_INCLUDE_DIR` and `HIGHS_LIB_DIR` first.
# (See "Build and install HiGHS" below.)
make # dune build
make test # dune runtest
# 4. Run optional solver-specific tests:
make test-glpk-js # dune build @runtest_glpk_js
make test-highs # dune build @runtest_highs
# 5. Run examples:
dune exec examples/lp-glpk/knapsack.exe
# 6. After editing, rebuild local packages from the current working-directory source:
# (When you want to update installed packages, e.g., to test them in REPL.)
opam install lp --working-dir # or opam reinstall lp --working-dir

For many OS distributions, binary packages for the HiGHS solver are not yet available. So, if you want to use it, the most reliable approach is to clone the Git repository and build it manually as described in the documentation.

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX="$HOME/.local"
cmake --build build --parallel
cmake --install build

Then set environment variables:

export HIGHS_INCLUDE_DIR="${HOME}/.local/include/highs"
export HIGHS_LIB_DIR="${HOME}/.local/lib"
export LD_LIBRARY_PATH="${HIGHS_LIB_DIR}:${LD_LIBRARY_PATH}"
export PATH="${HOME}/.local/bin:${PATH}"

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel
sudo cmake --install build
sudo ldconfig

In this case, HIGHS_INCLUDE_DIR / HIGHS_LIB_DIR are usually not necessary.

Since lp-glpk is tested only with GLPK version 4.65 and 5+, it may fail on older versions.

lp-glpk-js is another interface to GLPK through glpk.js, that is useful for applications based on js_of_ocaml.

The tests for lp-glpk-js are optional and not part of the default dune runtest. For local development, install the JS dependency outside dune with make setup-glpk-js and then run make test-glpk-js or dune build @runtest_glpk_js. The current test setup pins glpk.js to version 5.0.0.

For compatibility, Lp_glpk_js.require_glpk_async supports both the legacy 4.x module shape and the 5.x async constructor, while require_glpk remains available for synchronous 4.x initialization. Likewise, Lp_glpk_js.solve_async supports both synchronous and Promise-based glpk.solve.

The test of lp-highs is optional and not part of default dune runtest. For local development, build/install HiGHS as above, install lp-highs, and then run make test-highs or dune build @runtest_highs.

lp-gurobi is an interface to the commercial solver Gurobi. To use it, compile your application with -cclib -lgurobiXY flags, where XY is the version of Gurobi (e.g. 91). The test of lp-gurobi is disabled by default. To enable this, follow test/lp-gurobi/README.md.

A minimal example is shown below. A more detailed description can be found on the wiki.

let x = Lp.var "x"
let y = Lp.var "y"

let problem =
  let open Lp in
  let obj = maximize (x ++ y) in
  let c0 = x ++ (c 1.2 *~ y) <~ c 5.0 in
  let c1 = (c 2.0 *~ x) ++ y <~ c 1.2 in
  make obj [c0; c1]

let write () = Lp.write "my_problem.lp" problem

let solve () =
  (* For other interfaces, use Lp_glpk_js or Lp_gurobi instead *)
  match Lp_glpk.solve problem with
  | Ok (obj, xs) ->
      Printf.printf "Objective: %.2f\n" obj ;
      Printf.printf "x: %.2f y: %.2f\n"
        (Lp.PMap.find x xs) (Lp.PMap.find y xs)
  | Error msg ->
      print_endline msg

let () =
  if Lp.validate problem then (write () ; solve ())
  else print_endline "Oops, my problem is broken."

The examples directory contains more usage examples. To compile and execute, you can use dune exec:

dune exec examples/lp-glpk/knapsack.exe

High-level APIs include comments for odoc (or ocamldoc). Generated docs can be found online or in the docs directory.

Development is not very active now because the basic features are complete. However, there are several TODOs. Bug reports, requests, or patches are always welcome via GitHub issues and pull requests.

Currently, only the basic features of the LP file format are supported. Advanced features, which are typically available on commercial solvers, are not yet supported. (There is no standard LP file format, though.)

• Single objective (linear and quadratic)
• Constraints (linear and quadratic)
• Bounds
• Variable types (general and binary integers)

• Semi-continuous variables
• Multi-objective
• Lazy constraint
• Special ordered set (SOS)
• Piecewise-linear (PWL) objective and constraint
• General Constraint
• Scenario

Some references to the LP file format:

• CPLEX
• Gurobi
• GLPK manual

MIT