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.
