tkoolen / Parametron.jl

Efficiently solving instances of a parameterized family of (possibly mixed-integer) linear/quadratic optimization problems in Julia

Other

73 stars 7 forks source link

Support higher-dimensional arrays in `dot` #85

Closed timholy closed 6 years ago

timholy commented 6 years ago

I'm implementing the earth mover distance and the most natural representation uses a matrix of Variables and requires taking its dot-product with some weights.

Incidentally, in profiling I'm finding there's still quite a lot of allocation, which I'm guessing is a consequence of this line. Any thoughts on how to get around it? Also this line is insanely slow. Any tips for overcoming such problems?

codecov[bot] commented 6 years ago

Codecov Report

Merging #85 into master will not change coverage. The diff coverage is 100%.

@@           Coverage Diff           @@
##           master      #85   +/-   ##
=======================================
  Coverage   97.86%   97.86%           
=======================================
  Files           9        9           
  Lines         515      515           
=======================================
  Hits          504      504           
  Misses         11       11

Impacted Files	Coverage Δ
src/functions.jl	`99.24% <100%> (ø)`	:arrow_up:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update daca170...e8e591b. Read the comment docs.

tkoolen commented 6 years ago

The MathOptInterface wrappers for Gurobi (and other LQOI-based solvers) currently are just quite inefficient. Again, if your problem doesn't involve integer variables, try OSQP. If not (or maybe, regardless), you'll have to open issues with the MOI wrapper packages. The zero allocation results in the readme are of course predicated on having a solver interface that doesn't allocate when you do problem modification.

timholy commented 6 years ago

Done.

I keep getting fooled by the Q in OSQP, forgetting that of course it can solve linear problems too. It's definitely better than Gurobi or GLPK. Though I've now benchmarked it against https://github.com/robertfeldt/EarthMoversDistance.jl.git and getting results like these:

# bins	time OSQP (μs)	time custom C library (μs)
6	140	3
51	7860	160

So I'll probably be using the dedicated solver.

tkoolen commented 6 years ago

Great, thanks. Yeah, OSQP is definitely best when the cost function Hessian is positive definite, and a proper dedicated LP algorithm is always going to win.

timholy commented 6 years ago

Interestingly, at least for the small number of bins I think OSQP beat the linear solvers. But everyone got beat by the specialized implementation that takes advantage of particular features of "transportation problems."