[HN Gopher] Ask HN: Do you use an optimization solver? Which one...
___________________________________________________________________
Ask HN: Do you use an optimization solver? Which one? Do you like
it?
We're trying to bring new ideas to the optimization space. We've
used a bunch of technologies over time (CP, MIP, LP, heuristics,
etc.). We've built our own solver (for https://www.nextmv.io) and
learned a lot along the way. Solvers are amazing. MIP solvers, for
example, are some of the fastest and most mature software packages
that exist. They're also wickedly challenging to use effectively.
Do you use optimization solvers? Which ones? Why? Do you like them?
Why or why not?
Author : ryan-nextmv
Score : 56 points
Date : 2022-04-20 16:16 UTC (6 hours ago)
| jvanderbot wrote:
| SCIP, GLPK.
|
| I don't mind the overhead in developer time. Once you 'git gud'
| at translating problems to MIP/ LP, it's just a matter of
| learning syntax. The real trick is in translating problems.
|
| It's a shame more CS courses don't focus on this problem
| translation meta-algorithm. You can get it in tough theory
| courses with problem mapping to prove complexity, but its
| usefulness goes way, way beyond that somewhat niche application.
| Learning to model problems as max flow, graph partitioning /
| matching, LP, MIP, gives you absolute super powers way, way
| beyond what you'd gain by having a solver that's easier to work
| with.
| chime wrote:
| I would love to use one or more but the process to convert
| business logic to solver is painful so I ended up having to write
| a simulated annealing algo in Rust instead. I tried solver.com,
| Google OR-Tools, and a few other utilities.
|
| It was much easier to build a score-calculator for min/max based
| on user-tweaked parameters, then, jiggle the data, re-calculate
| score, and keep doing it until there was significant improvement
| (again, standard SA). I would absolutely love to convert the
| entire production plan logic with material availability, lead-
| times, customer demand, quality control windows etc. to something
| like nextmv.io but looking at your docs, I have no idea where to
| begin.
|
| Cost is a big factor too because 3 years ago I bought 4 old
| 24-core Xeons off eBay and they've been chugging non-stop
| simulating billion+ flops per hour with electricity being the
| only cost. I don't mind paying $50-100/day for cloud if the
| results are great and code is easy to manage. We have the same
| chicken-egg problem everyone in supply chain currently has - we
| don't have enough materials to make everything, don't know when
| we'll get everything, and so don't know the best order to
| buy/make everything in. I would love to write a solver for this
| using our dataset but I kind of don't want to re-invent the
| wheel.
|
| As it stands, every solver I find is one layer of abstraction
| away from what I want to code in. I can explain the problem in
| length if you want but it's honestly nothing unique - just the
| standard MRP/ERP planning with ton of BOM items, PO delays,
| labor/machine capacity constraints etc.
|
| Your existing tutorials explain how I can use your API/SDK to
| perform OR operations. That's great and a necessity. However,
| it's not sufficient for me because my questions are: How do I
| represent my production calendar in the JSON blob for your algo?
| How do I put a constraint of 100hrs/week/machine but also
| 168hrs/week/room full of specific machines. In other words, while
| each machine can run 100hrs/week, if there are 4 of them in the
| same room, only one can run at a time, and so combined machines
| in a given room cannot be over 168hrs/week. Maybe a tutorial or a
| higher-level library to help people like me convert business
| rules into JSON format for your APIs. Because even if I might be
| capable of using your API as-is, I unfortunately don't have the
| time to implement these things myself. Hope this makes sense and
| gives you some insight into at least one of your target use-
| cases.
| jvanderbot wrote:
| Yes, translating the problems is still the hardest part. Once
| you can write down the MIP, it's just syntax to get it into any
| old solver. It took me two - three days to write the I/O to get
| data in, formatted properly, and so on, and about half a day to
| write the MILP to solve ship-design optimization in Highfleet.
|
| https://github.com/jodavaho/highfleet-ship-opt
| ryan-nextmv wrote:
| Thanks for looking at our docs in light of your problem domain.
| That's way beyond what I anticipated, and much appreciated!
|
| We haven't put a lot more examples into our SDK docs lately
| since we've been working more on our routing engine and cloud
| offering. Now we're getting back to more foundational questions
| like "what should our solver be?" and "how should model
| formulation work?"
|
| Hop started off as a decision diagram solver, but even
| internally we strap a lot of different techniques onto it. My
| hope is to support those patterns better, which is really why I
| posed this question.
|
| I'd be interested to know: what made the process of converting
| business logic into solver-speak painful?
| chime wrote:
| > what made the process of converting business logic into
| solver-speak painful?
|
| The fact that every solver doc I found shows me two near
| identical variables and 4 identical constraints. I can solve
| that using Excel Add-In. My problem is mind-numbingly
| complex, like everyone else doing supply-chain optimization.
| So I need examples for each type of constraint I have but
| instead, the tools expect me to figure out everything based
| on very generic examples. Dates are a big deal in what I do.
| I have no idea how to convert "each day the customer order is
| delayed is bad, but I also can't make things 3 months before
| they want it" into solver-speak. Cleaning a machine takes
| time, so it is often better to make similar things in a row
| (campaign-mode). No idea how to convert that to solver-speak.
|
| The good thing is that once I understand how to convert my
| data into solver-speak, I can keep it updated on the fly
| since business logic doesn't change daily, just the data-set.
|
| Feel free to contact me directly and/or we can Zoom etc. if
| you wish to discuss further. Wish you the best of luck either
| way!
| shoo wrote:
| > I need examples for each type of constraint I have but
| instead, the tools expect me to figure out everything based
| on very generic examples
|
| if your problems can be attacked by LP / MIP type stuff,
| there's a book "model building in mathematical programming"
| by Williams that has a couple dozen different optimisation
| problems for a range of applications, with worked examples
| of how to formulate a model to solve each of them. each
| problem will be much less complex than your real-world
| optimisation puzzle but if you browse through the problem
| descriptions you might be able to match some against parts
| of your situation & get ideas for how Williams would model
| and optimise it.
| ryan-nextmv wrote:
| "My problem is mind-numbingly complex, like everyone else
| doing supply-chain optimization" brings me joy. I'll
| definitely reach out - would love to get your reaction to
| some of our new ideas.
| bjourne wrote:
| What you are describing is a scheduling problem. It is not
| _that_ difficult to solve using standard CP techniques. Create
| an Nx168 matrix of natural numbers for each room containing N
| machines, where each column represents the activity for a
| machine for a week. Constrain the sum of the rows to <= 1.
| Constrain the sum of the columns to <= 100. CP is all about
| "tricks" like these and takes a while to get used to. I can
| recommend the Python interface to OR-tools which I found very
| easy to work with.
| huevosabio wrote:
| I used to have to solve a ton of LPs or MILPs and rather quickly.
|
| After trying different stuff, and under different platforms (e.g.
| Matlab + CPLEX, Python + GLPK, etc), I settled first on Python
| or-tools with COIN-LP (about 100x faster than GLPK). Later we got
| access to FICO Xpress solver which in turn gave us some other
| gains.
|
| I really liked this benchmarking website:
| http://plato.asu.edu/bench.html
|
| It seems like they got into some trouble, so I don't know if they
| are still tracking the main commercial solvers.
| arsenide wrote:
| The only optimisation solver I use is Excel Solver Add-In.
|
| It's great, but you have to be able to put your problem into
| Excel to use it which does not work for all use cases.
|
| In cases where I'm trying to optimise something that doesn't
| quite fit into Excel cleanly I'll usually do some sort of hand-
| rolled Monte Carlo optimisation. This generally works for me in
| the types of problems I most often solve.
| ryan-nextmv wrote:
| Is it safe to say those optimizations are performed ad hoc?
| That is, you're manually in control of the optimization process
| instead of wiring it up to some kind of automation?
| arsenide wrote:
| Yes! In particular, it is usually to create some concrete
| data/parameters to be used towards creating the final
| product.
|
| In the usual Excel Solver case, for a simplified example, I
| want to create a biased coin where getting heads doubles your
| money and tails loses your money, with expected payout 90% in
| the long run. The parameters to change are heads/tails coin
| weighting, to target a value 90%. A fair coin gives a long
| run payout of 100%. It turns out that if a biased coin hits
| heads 45% of the time and tails 55% of the time, we end up
| with this 90% payout. Excel solver can come up with these two
| values.
|
| In this example, we can come up with these 45% and 55% values
| theoretically. With more complex systems, we may want to see
| the effects of changing a subset of parameters that have an
| indirect effect on payout.
|
| For example, if we extend the "biased coin game" to instead
| be "win your money back, 2, or 3 times your wager each with
| some probability" on a heads result, there are more
| parameters (and many solutions!) to get to 90% payout.
| Changing the heads probability has a further, second-order
| effect on the payout. Using Excel solver it's straightforward
| to fix some parameters (heads/tails probability) and allow
| others to change (1x/2x/3x odds) to get desired results (90%
| payout).
|
| If we further extend this methodology for a biased coin game,
| we can end up with a coin game that pays with distribution
| exactly like a slot machine in a casino, though it would not
| look like one!
| escot wrote:
| CPLEX (by IBM). The documentation can be a bit thin sometimes.
| But its fast. Most benchmarks place it ahead of the google cloud
| products.
|
| For fun I made this Golomb ruler solver using cplex:
| https://github.com/strateos/golomb-solver
| shoo wrote:
| The last time I tried to optimise something I ended up with a
| column generation formulation. I.e. I was wanting to rapidly
| iterate between LP solves of the (restricted) master problem &
| solves of auxiliary problems through hand written problem-
| specific algorithms taking shadow prices from the master problem
| dual solution as inputs. Then the auxiliary solution would
| contribute new variables into the master problem & we'd iterate
| until hitting a fixed point.
|
| I needed shadow prices defined using the master problem dual
| solution. In my problem instances I would very often run into
| scenarios where the primal (and hence also dual) master LP
| problem had a unique objective value but the dual solutions at
| which that maxima was attained were non-unique. I learned that it
| only makes sense to talk about shadow prices in some allowable
| range for each dual decision variable, but LP solvers generally
| don't give you an API to extract much information about this from
| the current internal state of the simplex algorithm [0]. I read a
| bunch of LP solver documentation and the best one I found
| discussing this kind of stuff was the section in MOSEK's manual
| about sensitivity analysis[1]. This was for a hobby project, not
| business, so I didn't try out MOSEK, even though it is looks very
| modestly priced compared to other commercial packages.
|
| What I did find, however, was that some time during the last few
| years, scipy.optimize grew an LP solver interface, and even
| better, Matt Haberland contributed a python implementation of an
| interior-point LP solver straight into scipy [2][3]. I found that
| Haberland & co's open source interior point LP solver produced
| dual solutions that tended to be more stable and more useful for
| shadow prices in my problems than a bunch of the other open
| source LP solvers I tried (including the various other LP
| backends exposed by scipy.optimize.linprog).
|
| [0] a paper I found very helpful in understand what was going on
| was Jansen, de Jong, Roos, Terlaky (1997) "Sensitivity analysis
| in linear programming: just be careful!". In 1997 they got 5
| commercial LP solvers to perform a sensitivity analysis on an
| illustrative toy problem, and although the solvers all agreed on
| the optimal objective value, none of them agreed with each other
| on the sensitivity analysis.
|
| [1] https://docs.mosek.com/9.2/pythonapi/sensitivity-shared.html
|
| [2] https://github.com/scipy/scipy/pull/7123
|
| [3]
| https://docs.scipy.org/doc/scipy/reference/generated/scipy.o...
| mulmboy wrote:
| I've been using CBC via python-mip (https://github.com/coin-
| or/python-mip). It's great because it's got a super clean
| interface (milp variables/expressions/constraints), the code is
| quite accessible, and it's low overhead which makes it good for
| solving many very small problems.
|
| Community sentiment seems to be beginning to shift toward
| favouring the HiGHS solver (https://github.com/ERGO-Code/HiGHS)
| over CBC. Something I'm keeping a close eye on.
|
| nextmv seems to pitch itself as a generic solving ("decision
| automation") platform or something (unclear). But it seems that
| the only fleshed out product offering is for vehicle routing,
| based on the docs. Are there plans to offer, for instance, a
| solver binary that can be used to solve generic problems?
|
| Also all the github repos under https://github.com/nextmv-io are
| private, so links from docs are 404.
| philip1209 wrote:
| I loved the JuMP package in Julia for being able to write models
| once, then swap in different solvers.
|
| Most open-source solvers don't handle parallelization well, and
| they lack the latest research on techniques like branch-cutting
| and heuristics that can speed things up significantly.
|
| In my experience, Gurobi is still leader for linear and MiP
| solving. But, it's really expensive and the licensing terms seem
| anachronistic.
|
| SimpleRose.com was a startup working on a new solver, too - I'm
| curious if anybody has tried it yet?
| cadr wrote:
| I have nothing to add except to say the illustration on your page
| of the mad scientist rabbit with the carrot is fantastic :)
| aurelian15 wrote:
| I have been using OSQP [1] quite a bit in a project where I
| needed to solve many quadratic programs (QPs). When I started
| with the project back in early 2017, OSQP was still in early
| stages. I ended up using both cvxopt and MOSEK; both were
| frustratingly slow.
|
| After I picked up the project again a year later (around
| 2019ish), I stumbled across OSQP again. OSQP blew both cvxopt and
| MOSEK out of the water in terms of speed (up to 10 times faster)
| and quality of the solutions (not as sensitive to bad
| conditioning). Plus the C interface was quite easy to use and
| super easy (as far as numerics C code goes) to integrate into my
| larger project. I particularly liked that the C code has no
| external dependencies (more precisely: all external dependencies
| are vendored).
|
| [1] https://osqp.org/
| michaelrpeskin wrote:
| We have complex non-linear stuff that maps really well to the
| meta heuristic approach that OptQuest uses
| (https://www.opttek.com/products/optquest/). It's not free and
| has only a Java API but the time it saves us is worth it. I hear
| Python bindings are coming this spring.
| version_five wrote:
| I used to use Matlab's fminsearch a lot. In retrospect I barely
| understood how it worked and I should have taken much more time
| to understand it rather than just throwing it at stuff. But I
| ended up getting some good results with it (some antenna design
| stuff).
| shoo wrote:
| If I were doing another serious large-scale commercial
| optimisation application where it was more valuable to get a
| pretty good feasible solution rapidly rather than potentially
| wait a long time attempting to find a provably optimal solution,
| I would be very interested in seeing how localsolver performs.
|
| Often the mathematical model of the real world problem or the
| input data used to parametrise the model has a fair bit of
| approximation error (e.g. assuming parameters are deterministic
| when actually they are uncertain, linearising things to bash them
| into the MIP modelling framework, etc) , so pragmatically it
| doesn't often seem useful to be too bothered about getting an
| optimal solution to an approximate problem vs getting an
| approximate solution to perhaps a better model approximation of
| the true situation.
|
| https://www.localsolver.com/
| anoncept wrote:
| After several years of exploring, my current gotos are:
|
| * Minion for IP for scheduling + edge crossing minimization.
|
| * cvxpy (wrapping ECOS, OSQP, and SCS by default) for convex
| optimization for making nice geometry.
|
| * Z3 and STP for SAT/SMT for program analysis.
|
| All are FLOSS, which is my main criterion in many situations.
|
| Beyond that, I like minion for its focus on only providing
| efficiently implementable primitives, cvxpy for the awesome
| lectures and documentation the folks behind it have produced, and
| z3 + stp for their use in tools I like, such as klee.
| swanson wrote:
| I used OR-Tools via the Python bindings a few years ago. It was
| nice to work with once I got setup but it was a pain to get it
| installed (both locally and when deploying to a cloud server).
|
| I would have liked some kind of API that I could call out to
| instead but nothing existed at the time: you pass in the inputs
| to construct the linear equations and then you get back the
| results.
| freemint wrote:
| I use JuMP as modeling language. For MILP i am usually using
| Gurobi or SCIP. For ILP problems have have been looking in to the
| exact solver https://gitlab.com/JoD/exact which seems quiet
| promising.
|
| For NLP i usually go with either https://worhp.de/ or just IpOpt.
| ryan-nextmv wrote:
| <3 SCIP. About a dozen years ago I used to write the python-
| zibopt library (now defunct and rendered moot by the far
| superior PySCIPOpt).
|
| Hadn't heard of JoD - that looks really interesting. What are
| your experiences so far?
| freemint wrote:
| JoD is Jakob Nordstrom. He gave a talk on the predecessor of
| Exact here: https://www.youtube.com/watch?v=yvXy7Nzn-IA
|
| My experience so far: Quiet good at finding feasible
| solutions when constraints are complex. Really young code
| with a lot of potential. Not that good at finding optimas.
| zokier wrote:
| Optaplanner facinates me, but I have no idea what I could be
| using it for and the learning curve seems quite heavy
|
| https://www.optaplanner.org/
| eduardosalaz wrote:
| For MIP and LP I have used CPLEX, Gurobi and to a lesser extent
| Cbc. I used those three using JuMP (Julia package for
| mathematical programming) and Gurobi via pulp and pyomo. Of all
| three, I think Gurobi has a very accessible documentation, note
| that I am not saying better or more complete which in that case
| it would go to CPLEX, and the integration with Python straight
| out of the box is very useful. Cbc is a lifesaver when we
| couldn't access the academic licenses of the other two. Overall,
| I think CPLEX/Gurobi are my favorites with a slight edge to
| Gurobi. I have tried formulating problems using .lp and GAMS but
| JuMP is so much more ergonomic even if it's strictly tied to
| Julia (which I find to be a good thing).
| wombatpm wrote:
| I used Gurobi for logistics routing problems years ago and
| loved it. Especially loved that I could get a fully functional
| trial that was limited by total variables to develop my problem
| and use the license version for the production problems
___________________________________________________________________
(page generated 2022-04-20 23:00 UTC)