Of course that is but one example, the next order might realize even more shipping.. and with multiple orders the numbers do add up, saving a couple hundred a year is possible.
If you read the article, the problem is more about the Jet platform having multiple merchants. They’re making their platform more efficient at giving the best price. Doesn’t have anything to do with you.
I'm an intermediate Haskeller and I just started playing around with F# around 2 months ago.
I really like it. It still feels very functional but has escape hatches when I want imperative behavior.
I like that I can still write "beautiful" code which feels high level and is expressed in the language of the problem domain, yet can fall back on idiomatic imperative solutions for certain tight loops or data structures.
F# still feels like a toy sometimes but that might only be cause C# is so polished.
Don Syme was a (if not the) driving force behind .NET going with reified generics, for one. Also, back when I was a "C# by day, F# by night" developer, I really felt like F# was being used as an incubator for ideas that were eventually pulled into C# in some form or another. For example, in some respects async/await feels like a domesticated version of the async computation expression.
I come from a very non-functional background, but I love f#. Or fell in love with it, anyways.
At first I was pretty opposed to both executing functions without using parentheses and also currying as a default. Now I find myself missing those things in the languages I use daily for my job (which sadly, do not include f#).
I got tired of being a cog in the Amazon machine and bought some merchandise from Jet.com last week. It was a sub-optimal experience.
This is what I bought:
-> $4.22 Q-tips Cotton Swabs 500 ct
-> $16.32 iPhone 5/5s, iPhone SE, iPod Touch 5th/6th Gen Adidas Nylon Armband Case - Sports armband for adidas miCoach training system
-> $6.95 iBungee Stretch Laces (26-Inch, Black Laces with Black Race Lock)
-> $4.79 4 Philips AA Zinc Chloride Double A Batteries R6 1.5V Super Heavy Duty Battery
-> $8.10 Monoprice Apple MFi Certified Lightning to USB Charge & Sync Cable, 3ft White
-> $89.96 ASICS Men's GEL-Kayano 23 Running Shoes T646N
The order for the phone arm-band was cancelled and everything else shipped _separately_ - I Literally got 5 different packages in the mail - over a week with different items.
Had I gone with Amazon, I would have received - one, maybe two packages with everything. Infact, Jet probably lost money on most of the items they shipped to me.
Us techies sometimes tend to forget the real world (in this case customer experience) while playing with cool technology.
To me, an old fashioned optimizer running on a 15 year old AMD Opteron that delivers the appropriate real-world result is worth more than that F# and CUDA thing that seems to have over-optimized the problem to create a bad customer experience (getting 5 packages in a haphazard way).
I don't know if this is still the case but Jet doesn't handle fulfillment for all of the items on their store. I've bought stuff on Jet that were shipped from over e-commerce web sites.
Its a little more complex than that. Batteries must be shipped seperately, as per regulations. You are assuming everything shipped form same warehouse.
Have you considered that F# CUDA and the delivery situation are not causally related? Maybe a good optimization system is programmed with bad constraints.
Wow the prices are incredible. At walmart grocery they list 500 swabs for $2. In the store, zinc batteries are $1 for four. However on the site they aren't even shown and want you to buy alkalines for $3. But zinc batteries are 24 for $0 at harbor freight with their regular coupon.
Walmart's online orders come from a million places similar to your Jet experience. I used it all the time, when the online prices were identical to the in-store prices. Spend $6 more to get free shipping! Ok, I'll take 50 pounds of cat litter, hope the UPS finance dept thanks you. I wonder why they put a stop to this :(
That was a pretty fun read. Discrete optimization is still a huge challenge that many companies still face today.
So...is it naive to think that I can create something similar with MiniZinc (or an equivalent package)? Or will it take too long to even get an answer without CUDA? This seems like a pretty fun weekend project!
It really depends on how many constraints and variables you're optimizing for. Because this problem is NP-hard, I'd bet you could make a more naive version that solves some easier ILP problems, but scaling it up probably requires quite a bit of optimization/good heuristics. Definitely seems like a good learning experience if you're interested in algorithms though!
Not sure if I'm missing something but as an industrial engineer who solves these problems onscale via linear programming (X products, Y warehouse locations, Z destinations), most of these issues are not THAT computationally expensive even when talking about combinations of millions of SKUs.
Is it way harder because they provide fulfillment breakdown instantly or something, or because the tech stack is unique?
This deserves some discussion, but alas, I'm not a linear programming expert.
The article implies that the best solution was brute-force, and therefore they use Genetic Algorithms to search for a "pretty good" solution as opposed to the optimal solution.
Linear Programming on the other hand would find PRECISELY the optimal solution. But there are all kinds of constraints on what kinds of programs Linear Programming can solve.
It seems like this constraint problem can be solved through Linear Programming methods, but I'm not an expert in that algorithm. So maybe Jet.Com is being inefficient here with the algorithm (just a little bit inefficient).
If it's strictly a linear program, it's probably fine. You can always find the global optimum. Seems more likely to me that it's non-linear, which then depends on how non-linear (quadratic only?), if it's just the objective or the constraints that are non-linear, is it convex at all, etc.
In my uneducated opinion, it seems like the nonlinearity comes from the shipping options, which can depend on the number of items bought from a vendor in non-obvious ways.
Yes, ILP is NP-hard[1]. I don't know how many constraints Jet's problems require, but I believe there are approximation algorithms that can do quite decently on most problems (perhaps even Simplex might do decently?). Would be interested to hear about this from someone with a strong algorithms background though.
I'm not an expert, but I believe the difficulty in this problem is purely from the integers. The objective is linear, and the constraints are also linear. Most solutions to IPs rely on solutions to LPs (and hence the simplex algorithm), but they try to modify the objective / constraints / output in a clever way.
One approach is to use the simplex algorithm, and then simply round the output. A better approach is a recursive meta-algorithm called "branch and bound." Start with a particular variable, and find the lower bound for total price if it is 0 vs if it is 1 by using the simplex algorithm on each side. Enqueue the branch with lower bound for total price. In the next round dequeue the branch with the lowest lower bound; if all the variables are integers return it, otherwise create two branches for another variable, etc. By changing search strategy from "breadth first" to "depth first" you are guaranteed to find a feasible solution sooner. You can also stop early by bounding how much error you are willing to tolerate compared to the lower bound provided by LP.
This is a very standard algorithm though, so I'm sure Jet have tried it. It seems like the number of variables they have is just too large; in the worst case branch and bound is exponential.
What I would like to know is what cost savings were achieved by this process. I worked in their parent company's supply chain dept. I know for a fact that the shipping data they have does not reflect true costs. It is modified internally as a warehouse management tool (Eg. if you want to drain inventory from a warehouse, you set shipping costs as zero).
There are no true dollar costs anywhere in their databases. Also, instead of evaluating all the parallel combinations, they use a branch and bound heuristics.
46 comments
[ 2.8 ms ] story [ 71.1 ms ] threadI really like it. It still feels very functional but has escape hatches when I want imperative behavior.
I like that I can still write "beautiful" code which feels high level and is expressed in the language of the problem domain, yet can fall back on idiomatic imperative solutions for certain tight loops or data structures.
F# still feels like a toy sometimes but that might only be cause C# is so polished.
Don Syme was a (if not the) driving force behind .NET going with reified generics, for one. Also, back when I was a "C# by day, F# by night" developer, I really felt like F# was being used as an incubator for ideas that were eventually pulled into C# in some form or another. For example, in some respects async/await feels like a domesticated version of the async computation expression.
Lambdas? C# got them later.
Immutable constructor patterns? C# got them later.
A scripting environment? C# is trying.
Pattern matching? C# is trying (but since it's not exhaustive...).
No nulls by default? C# got it later (and less clearly).
It's really impressive how quickly those features have gained mindshare and become 'must haves' despite initial resistance.
Fundamentally, though, the higher order programming features that F# inherits ML give it a maturity and flexibility that C# will just never encompass.
At first I was pretty opposed to both executing functions without using parentheses and also currying as a default. Now I find myself missing those things in the languages I use daily for my job (which sadly, do not include f#).
It might not be do-able in your situation but there are ways you can introduce F# in an incremental, low-risk way. Some ideas here: https://fsharpforfunandprofit.com/posts/low-risk-ways-to-use...
This is also a free resource for learning F# in your browser:
https://notebooks.azure.com/Microsoft/libraries/fsharp/html/...
basically click clone, sign in, run & play around.
Something that glpk/gurobi should be used for?
This is what I bought:
-> $4.22 Q-tips Cotton Swabs 500 ct -> $16.32 iPhone 5/5s, iPhone SE, iPod Touch 5th/6th Gen Adidas Nylon Armband Case - Sports armband for adidas miCoach training system -> $6.95 iBungee Stretch Laces (26-Inch, Black Laces with Black Race Lock) -> $4.79 4 Philips AA Zinc Chloride Double A Batteries R6 1.5V Super Heavy Duty Battery -> $8.10 Monoprice Apple MFi Certified Lightning to USB Charge & Sync Cable, 3ft White -> $89.96 ASICS Men's GEL-Kayano 23 Running Shoes T646N
The order for the phone arm-band was cancelled and everything else shipped _separately_ - I Literally got 5 different packages in the mail - over a week with different items.
Had I gone with Amazon, I would have received - one, maybe two packages with everything. Infact, Jet probably lost money on most of the items they shipped to me.
Us techies sometimes tend to forget the real world (in this case customer experience) while playing with cool technology.
To me, an old fashioned optimizer running on a 15 year old AMD Opteron that delivers the appropriate real-world result is worth more than that F# and CUDA thing that seems to have over-optimized the problem to create a bad customer experience (getting 5 packages in a haphazard way).
Source. Worked on this problem for some years.
Walmart's online orders come from a million places similar to your Jet experience. I used it all the time, when the online prices were identical to the in-store prices. Spend $6 more to get free shipping! Ok, I'll take 50 pounds of cat litter, hope the UPS finance dept thanks you. I wonder why they put a stop to this :(
So...is it naive to think that I can create something similar with MiniZinc (or an equivalent package)? Or will it take too long to even get an answer without CUDA? This seems like a pretty fun weekend project!
Is it way harder because they provide fulfillment breakdown instantly or something, or because the tech stack is unique?
The article implies that the best solution was brute-force, and therefore they use Genetic Algorithms to search for a "pretty good" solution as opposed to the optimal solution.
Linear Programming on the other hand would find PRECISELY the optimal solution. But there are all kinds of constraints on what kinds of programs Linear Programming can solve.
It seems like this constraint problem can be solved through Linear Programming methods, but I'm not an expert in that algorithm. So maybe Jet.Com is being inefficient here with the algorithm (just a little bit inefficient).
[1] https://en.wikipedia.org/wiki/Integer_programming
One approach is to use the simplex algorithm, and then simply round the output. A better approach is a recursive meta-algorithm called "branch and bound." Start with a particular variable, and find the lower bound for total price if it is 0 vs if it is 1 by using the simplex algorithm on each side. Enqueue the branch with lower bound for total price. In the next round dequeue the branch with the lowest lower bound; if all the variables are integers return it, otherwise create two branches for another variable, etc. By changing search strategy from "breadth first" to "depth first" you are guaranteed to find a feasible solution sooner. You can also stop early by bounding how much error you are willing to tolerate compared to the lower bound provided by LP.
This is a very standard algorithm though, so I'm sure Jet have tried it. It seems like the number of variables they have is just too large; in the worst case branch and bound is exponential.
There are no true dollar costs anywhere in their databases. Also, instead of evaluating all the parallel combinations, they use a branch and bound heuristics.
GPU powered algorithm solving is awesome!
But I took a look in Firefox and the site is very informative and the solver is quite snappy.