How Jet Built a GPU-Powered Fulfillment Engine with F# and CUDA

[jjaredsimpson]

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.

[bunderbunder]

FWIW, you can thank F# for C#'s level of polish.

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.

[dvlsg]

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#).

[binarysolo]

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?

[dragontamer]

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

[rkwasny]

+1 this looks like a integer programming problem that can be just solved exactly without brute forcing the solution.

[Nelkins]

BTW, if you're feeling like you want to learn more about F#, this year's F# advent calendar is just getting started: https://sergeytihon.com/2017/10/22/f-advent-calendar-in-engl... . Previous years have been pretty good.

[smortaz]

Nice!

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.

[sdsdsdsdsds]

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.

[hildaman]

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

[sdsdsdsdsds]

Its a little more complex than that. Batteries must be shipped seperately, as per regulations. You are assuming everything shipped form same warehouse.

Source. Worked on this problem for some years.

[djchen]

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.

[visarga]

Have you considered that F# CUDA and the delivery situation are not causally related? Maybe a good optimization system is programmed with bad constraints.

[kw71]

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 :(

[rkwasny]

Isn't this just a simple integer linear programming optimization problem?

Something that glpk/gurobi should be used for?

[scott00]

The discounts on shipping you can get for buying multiple items from a single vendor make the objective function non-linear.

[cm2187]

Integer programming. Which makes it a lot more complex.

[santaclaus]

Gurobi is sloooooooooooow, and scales pretty badly.

[pbreit]

I’m sure this is a great system but lousy fulfillment is the singular reason I do not shop with Jet.

[daenz]

Shameless self-promotion, I built a Travelling Salesman solver that runs in the GPU inside WebGL in the browser: https://amoffat.github.io/held-karp-gpu-demo/

GPU powered algorithm solving is awesome!

[eindiran]

Just so you know, I couldn't get the site to work in Chromium: "Uncaught ERROR: too many uniforms".

But I took a look in Firefox and the site is very informative and the solver is quite snappy.

[berbec]

The solve times certainly show how much better GPGPU problem solving can be for problems that can be massively threaded.

[syntaxing]

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!

[rishabhparikh]

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!

[jhiska]

.

[skellera]

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.

[SirFatty]

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.

[stanmancan]

What a conceited answer.