ryan-nextmv

The conference is virtual. It runs Monday, September 18 through Wednesday, September 20. Registration is free.

Even if this paper is correct, the approach is not practical. From table 1 in section 6.2, the LP representation of a 25-city TSP requires 24,580,032 variables and 3,643,825 constraints. Merely formulating that model will require significantly more time than fully optimizing a TSP of that size using an assignment or 2-matching relaxation and adding subtour elimination constraints as they are violated. The former will likely take seconds (or maybe minutes) at that size, while the latter can be accomplished in milliseconds.

I haven't looked at JuMP in a while - the last time I tried it was when I was still doing personal blogging (https://ryanjoneil.github.io/posts/2014-07-18-are-we-getting...).

I remember liking JuMP, but Julia itself didn't feel ready yet. Some of the packages had weird behaviors. For example, Gadfly took several minutes to render some of my charts. IIRC when I looked at the source, it was solving a MIP to compute the best bounding box for display purposes.

I should probably check it out again.

Also: agreed regarding Gurobi licensing.

Yes! MiniZinc is great. It's the only sticker I have on my Linux box.

I like how it targets both MIP and CP solvers. It's actually the tool that first led me to CP and Gecode.

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?

<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?

"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.

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?

Definitely try out the API (https://cloud.nextmv.io/) to get a sense for it. Note that these are canned models, and the systems under the hood are very customizable. You can find some more information in our docs (https://docs.nextmv.io/latest/). If you have another problem or need something specific, reach out to support@nextmv.io.

We haven't published any formal benchmarks yet. We will soon!

I'm not a regular OR-Tools user, but it allows you to call its own CP solver or external MIP solvers. I can provide a few general comments about what you'll find applying different techniques to TSP solving:

1. Nothing beats Concorde for solving pure TSPs: http://www.math.uwaterloo.ca/tsp/concorde.html

2. Mixed integer programming solvers do very well because you can relax the subtour elimination constraints to solve a simpler problem (such as an assignment or a 2-matching), and add them to the problem representation as they are violated in the search tree. With tight bounds the solver can fathom away most of the search space.

3. All of this breaks apart when you need to route multiple vehicles or handle side constraints (precedence, time windows, capacity). This is where CP, DDs, and Hybrid Optimization techniques start to really shine.

It's (3) that we're most interested in because realistic problems tend not follow simple, pure representations like the TSP. So when we do publish benchmarks (and their associated models) it will likely be for problems like the Li & Lim PDPTW instances (https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/).

Another important aspect is time to find high quality solutions. Most people doing on-demand routing need good solutions that are actionable quickly. DDs have already shown a lot of promise in this area.

Thanks for asking!

Value is actually the value of a state itself, and it can increase or decrease from one state to its successors. If the value must increase or decrease monotonically, then that (very useful) information can be given to Hop through a Bounds() method.

In the simplest cases, value is added or subtracted with each state transition, and can be stored in an attribute. However, that isn't required. It's possible to do just about anything in the value function, such as run a simulation to estimate a KPI.

If estimating value is expensive, then it's probably best to keep the diagram width low, and/or use a searcher that dives to high quality solutions before expanding the search. Hop comes with some of these capabilities built in, and most of its solver components are plug-able through interfaces so you can provide your own if you need.

When it comes to scale, we're trying to make it so Hop scales up and down well to different size problems. As you add side constraints such as precedence, time windows, driver hours, capacity, etc., you'll likely find that DDs do better since those constraints tend to support the search.

Dash is a generic discrete event simulation engine that (intentionally) looks a lot like Hop (JSON in/out, runners that package up sims as atomic binaries). Sim actors conform to a simple interface and use an event sourcing architecture to publish events, update state, and record measurements. We should have a blog post about it in the next couple weeks, as well as our docs posted online, so check back!

Awesome! We're very much looking for feedback on how we can improve it.

Thanks for the question!

In sound-byte form, this is for developers to develop algorithms.

What we really mean by that is for developers to easily automate decision making at any scale. Those can be simple rules-based decisions, or complex decisions requiring sophisticated approaches. We believe that the practice and methodology behind the automation are as important as the algorithms themselves.

Regarding your questions of maturity, it depends :). Some algorithms commonly used in decision making, such as linear sum assignment or shortest path algorithms are quite mature and (generally speaking) fast. Others are mature and often fast enough, but sometimes not. Plenty of important problems are more or less unsolvable right now.

Mixed integer programming solvers, for instance, are extremely powerful and handle large general classes of problems. They also require translation of business rules into specialized form by domain experts, and can blow up in terms of optimization time or even time to find a feasible solution.

Complicating this is the fact that most real-world problems have side constraints which may render well-studied algorithms or models useless. We are eternally searching for more flexible, more advanced techniques, and maturity depends a great deal on what you need to accomplish.

I haven't used Choco myself, but I have seen it used quite successfully in some nice hybrid optimization studies. Gecode is awesome, but can be complex to get started with.

Parts of Hop's design are informed by using Gecode and SCIP (https://scip.zib.de/) a lot. They're among the best designed solvers I've seen (for those that you can see the source). Over time I'd like to add in finite domain propagation and canned algorithms from the global constraint catalog.

1-tree on GPUs? That's pretty interesting.

Ping us at tech@nextmv.io if you're seriously interested in talking more.

Sounds familiar!

One thing that's struck us is the lack of accessibility of optimization tools to software engineers. I worked as a developer long before I ever got into OR. When I switched over to being an analyst, it felt like there was an invisible divide between the two worlds.

A great success of the Data Science movement over the last decade seems to be making statistics and visualization easier for and more widely adopted by tech. We think optimization and simulation are about to go through the same thing.

OptaPlanner and Choco are both very cool tech. We've been pretty religious users of Gecode (https://www.gecode.org/) over the last few years, which you should also check out if you are interested in CP and like C++.

There are a few important differences between what we're building and those tools:

A large focus of our tools is on integration with software stacks and data warehouses. They are opinionated about how decision models should read and write data, how they should be deployed and interacted with, and they make those patterns clear and consistent. We refer to this as the "decision engineering" part of the field, which is not often addressed by existing tools.

Decision Diagrams (and thus, Hop) rely on many of the same techniques as MIP or CP (search, inference, and relaxation), but they represent problems in different ways and have their own interesting characteristics. For instance, diagram restriction and reduction are both powerful techniques specific to DDs.

In our systems, we represent models as states and transitions. I believe this makes models easier to unit test and reason about. It also has the interesting side effect of making optimization and simulation look a lot closer to each other than they traditionally have, which is something we'll be exploring more in the coming months.

Take a look at the DD book if you're looking for a thorough treatment: https://www.springer.com/gp/book/9783319428475. It's really interesting stuff! We'll also be updating our blog fairly regularly now that we're launched.

I guess we're a TSaaS company. :)

Thank you so much for sharing this! I will read it.

I suspect there's a lot of potential for these sorts of techniques in production systems, especially combined with decision diagrams. We've been looking at DDs partly because they are capable of optimizing problems without a lot of restrictions on problem type or representation, and also because they seem like a very nice metaheuristic structure.

Thanks for the love! We're learning a lot from the market already and plan to have plenty of interesting new features released in the coming weeks.

Good points! We've definitely seen delivery networks flail under certain conditions, like lack of density. Our hope is that by making both optimization and simulation more accessible to software engineers, we can help organizations understand and preempt problems like that.

Which brings up the answer to your question: We're targeting developers. Companies that build integer programming solvers and similar tech have great tools for PhDs in Operations Research who have a lot of mathematical sophistication. We think there is an underserved market of software engineers who can benefit from different technology.