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.
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?
> 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!
> 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.
In a previous life, when I worked with solvers a lot, this was exactly my problem too: the examples in the documentation are always way too simple.
What I saw often, and this was in finance, that one or two developers gain proficiency in converting problems to a specific solver tool, and then we could never move to a different library because it would have been so much effort to relearn.
"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.
> "each day the customer order is delayed is bad, but I also can't make things 3 months before they want it
This would be something in the objective function, I think? Assign some daily cost to having stock in inventory and a penalty per day that the "supply delivery to customer" task completes after the deadline.
IIRC ILOG solver used to have a lot of constraints that made implementing that kind of thing easier.
Reading this from the perspective of a naive outside observer, I'm wondering (just thinking out loud) about the potential value of a hybrid approach of a) providing customers who know what they want a self-service API, b) supporting customers who just want their problems solved with consulting, and a+b) offering joint R&D scenarios in select circumstances that would progressively add support for novel workloads over time (like what's described here) in the pursuit of differentiation. Obviously this would be aligned with use cases that don't require immediate solutions/consulting. The resulting data might be worth it. And this all obviously depends on where ease-of-use sits, given that's basically NP-hard to resolve fully in this domain.
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.
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.
You raise a very good point in that the "formulate the problem the way the solver wants" step is legitimately difficult and full of pitfalls. Simply figuring out the translation can be hard, and even then there are many ways to formulate a problem which are mathematically equivalent but have drastically different performance when fed to the solver.
It really feels like a tools or language problem. Heck, we used to have to manually work out derivatives for continuous optimization problems, but nowadays programming languages with performant built-in autodiff often make this trivial. Removing the manual derivation hassle let loose a flood of cool ideas and applications, even though there was no technical hurdle preventing them in the first place.
Alternate problem specifications is a well-explored area (what is Prolog if not a way of describing problems for a constraint satisfier?), but I wonder how many other neat things are dammed up behind usability problems.
Certainly but I didn't and still don't have the resources to write solving algo on top of the business logic that goes into the algo. I would much rather user my 20+ manufacturing ERP experience to setup the problem specific to our use-case than read research papers and implement generic CS algos.
Genetic algorithms are known to produce quasi-optimal results in a short time, if set up accordingly. They can be also applied to problems where constraints are very complex to explicitly formulate. Designing one is no picnic, though, and always problem-specific.
Quasi-optimal means you can't prove that the algorithm will always find the optimal solution, though for all practical purposes, the algorithm will find it for over 99% of the time.
Honestly that constraint is pretty straightforward to formulate as a MILP. Four machines, each has a starting and ending time as decision variables. Total duration by machine <= 100 hours, and add non-overlapping constraints between the machines. Each machine's start time >= 0, each machine's end time <= 168 hours.
I'm doing almost exactly this right now on a client project (I consult in supply chain optimization)
curious to know - how do you solve this today ? what is your abstraction/solver-speak today ?
I also have faced this (though im not a power user like you) - so im curious what did u end up using today ?
I have a niggling feeling somewhere that JSON is the wrong language for this. Something like cue lang may be the right thing. (https://www.sobyte.net/post/2022-04/cue/)
I don't 'solve' it using linear optimization today. I use https://en.wikipedia.org/wiki/Simulated_annealing which basically amounts to (1) calculate score based on the dataset (2) randomly change some data that affects the score (3) discard the score if it much worse, keep if slightly better or worse (4) repeat until new score is much better than original score. I allow it to get a little worse over time but if it is much worse, I basically restart from the last-best score.
The nice thing about scoring with SA is that I don't need to think like an operations research student. I just think in code with if/then/else and the number of dimensions don't matter. The code is working fine for now but now the problem is a business requirement to make it MUCH more complex and factor in a whole new set of constraints. SA will straight up not work with it because the scoring itself can take tens of seconds now. So I need to come up with a new 'proper' way, hence my renewed interest in solvers.
Sounds like you have a good solution for your problem. Whatever solves the problem and is already done is naturally a good solution!
From my experience, the most important thing to get right in any local search algorithm is the state representation and the moves generated. If those work well, then any combination of metheuristics like simulated annealing, tabu search, population based search, restarts, parallel exploration, portfolio methods, and so on. Quite often the literature focuses only on the meta heuristic, but not so much on the representation, which IMHO can be an issue.
As an example, for some problems that I have solved with local search, the most impact in improving performance of the algorithms have been in improving the base. Making moves and score updates fast, and making the moves generated meaningful in the context.
this is super interesting - what is a "Score" ? i'm trying to model your problem as a neural net problem in my mind.
how do you transform a classic linear optimization problem (which is a bunch of equations) into a score ?
pretty sure there's heuristics at play...but how would you do it ? take your own example of
>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
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.