linprog
linprog
Idea is to provide wrapper for most performant opensource optimization tools that are available. This shard is about linear and mixed integer optimization. According to http://plato.asu.edu/bench.html CLP is pretty good for linear programming, and other projects of COIN-OR (CBC and IPOPT) are fine for nonlinear.
CoinMP is decribed as simple API for CLP and CBC (just what I need!), but appears to be buggy and obsolete.
SYMPHONY looks easy enough to use and to distribute.
- SYMPHONY works, but require few patches to be easily wrappable (namely
extern C
to disable mangling and#define printf
to disable console spam). I've created fork https://github.com/konovod/SYMPHONY with patches - It is distributed under EPL1.0 that is incompatible with GPL, but otherwise pretty permissive.
Installation
- Install COIN-OR SYMPHONY from package manager to get all dependencies
git clone https://github.com/konovod/SYMPHONY
configure && make
- copy
SYMPHONY/SYMPHONY/src/.libs/libSym.so.0.0.0
to /usr/lib, create symlink/usr/lib/libSym.so.1
pointing to it
Alternatively: you can use installation instructions for the upstream version: https://github.com/coin-or/SYMPHONY Master already has extern C
fix but will spam some messages to console.
Usage
require "linalg"
require "linprog"
# linear programming
# x - solution, f - objective value
x, f = LinProg.solve(
# c - objective function
c: LA::GMat.new([[0, -1]]),
# a_ub - left part of inequalities
a_ub: LA::GMat.new([[-1, 1], [3, 2], [2, 3]]),
# b_ub - right part of inequalities
b_ub: LA::GMat.new([[1, 12, 12]]).t,
# a_eq, b_eq - left and right parts of equalities, can be skipped if empty
# bounds - constraints to variables
bounds: {LinProg::Bound.none, LinProg::Bound.new(-3.0, Float64::INFINITY)})
pp x, f
# bound can be same for all vars
x, f = LinProg.solve(
c: LA::GMat.new([[0, -1]]),
a_ub: LA::GMat.new([[-1, 1], [3, 2], [2, 3]]),
b_ub: LA::GMat.new([[1, 12, 12]]).t,
bounds: LinProg::Bound.positive)
pp x, f
# tasks can use equalities, inequalities or both
x, f = LinProg.solve(
c: LA::Mat.row([1, 7, 4, 2, 3, 5]),
a_eq: LA::GMat.new([
[1, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 1],
[1, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1],
]),
b_eq: LA::Mat.column([30, 20, 15, 25, 10]))
pp x, f
# integer and mixed integer programming
x, f = LinProg.solve(
c: LA::GMat.new([[0, -1]]),
a_ub: LA::GMat.new([[-1, 1], [3, 2], [2, 3]]),
b_ub: LA::GMat.new([[1, 12, 12]]).t,
bounds: {LinProg::Bound.integer, LinProg::Bound.new(0.0, 6.0, integer: true)})
pp x, f
# there is also more complex interface that allows to save\load problems, but it's WIP, check spec dir for it
DSL
There is a dsl for nice creation of problems. It is WIP in a sense that more features will be added (most important is to check how it works with MultiArray to be on par with AMPL features), but right now following works:
# Create a problem
task = LinProg::SymbolProblem.new
# add a vars with (optional) bounds
x = task.create_var(bound: LinProg::Bound.integer)
y = task.create_var(bound: LinProg::Bound.new(0.0, 6.0, true))
# add constraints in a natural way
task.st(x + 1 >= y)
task.st(3*x + 2*y <= 12)
task.st(2*x + 3*y <= 12)
# set objective and direction of optimization
task.maximize(y + 1)
# solve
task.solve
# now vars have values from a solution
x.value.should eq 1
y.value.should eq 2
Roadmap:
- warmstarting
- sensitivity analysis
- access to solver parameters
- way to reset solver properly or otherwise avoid memory leak
- sparse matrix support
- DSL for problems creation
- Check integration with https://github.com/konovod/multiarray
- More fleshy example
- GLPK bindings to provide easy-to-install solution
- CI
linprog
- 2
- 0
- 0
- 0
- 1
- over 2 years ago
- June 27, 2017
MIT License
Fri, 22 Nov 2024 14:02:50 GMT