Dantzig - Linear programming for Elixir (using the open source HiGHS solver)

Your Libraries & OS Mentoring Libraries
,
1

I’ve written a wrapper for the HiGHS solver (currently only supports linux; the linux executable is bundled with the source in the /priv directory) to help with a data visualization library I’m building. It’s really helpful to be able to specify the relationships between objects in a drawing as declarative constraints and let the system solve everything before drawing. Plotting data is a case where there is a big mix of variable and constant terms, and most interesting constraints are linear or quadratic.

Source code here: GitHub - tmbb/dantzig: (Integer) linear (and quadratic) programming for Elixir (using the HiGHS solver)

You can find an example there in the README.

A simple example showing a very easy case of quadratic programming (which can be solved by hand very easily) is this:

defmodule Dantzig.Instances.ClosedFormQuadraticTest do
  use ExUnit.Case, async: true
  require Dantzig.Problem, as: Problem
  use Dantzig.Polynomial.Operators

  test "closed form quadratic: x - x*x" do
    problem = Problem.new(direction: :maximize)

    {problem, x} = Problem.new_variable(problem, "x", min: -2.0, max: 2.0)
    {problem, _obj} = Problem.increment_objective(problem, x - x*x)

    solution = Dantzig.solve(problem)

    assert solution.model_status == "Optimal"
    assert solution.feasibility == "Feasible"
    # There are no constraints
    assert solution.constraints == %{}
    # Only a single variable is created
    assert Solution.nr_of_variables(solution) == 1
    # The solution is correct (within a margin of error)
    assert_in_delta(Solution.evaluate(solution, x), 0.5, 0.0001)
    # The objective value is correct (within a margin of error)
    assert_in_delta(solution.objective, 0.5, 0.0001)
  end
end

The problem above can be written using an “implicit problem” macro like this:

  test "closed form quadratic: x - x*x (implicit problem)" do
    problem = Problem.new(direction: :maximize)

    Problem.with_implicit_problem problem do
      # Define a variable in the current problem
      v!(x, min: -2.0, max: 2.0)
      
      # x is a polynomial (actually a monomial, since it has only one term)
      %Polynomial{} = x
      # The objective function is also a polynomial (of degree 2 with 2 terms)
      %Polynomial{} = x - x*x
      
      _obj = Problem.increment_objective(x - x*x)
    end

    solution = Dantzig.solve(problem)
  end

The package (not yet published on hex) contains a library to define polynomials and algebraic operations on polynomials. We support polynomials of arbitrarily high degree, but only polynomials of degree < 3 can be used for constraints and for the objective function in the solver.

4 Likes