How Jet Built a GPU-Powered Fulfillment Engine with F# and CUDA | Hacker News Reader

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

devblogs.nvidia.com

203 pointskungfudoi44 comments

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.

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.

Compare where the two languages were, and look where we are now..

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.

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

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

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.

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

isn't integer programming way harder than normal class of convex optimization problems like quadratic, second order cone or semidefinite?

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.

[1] https://en.wikipedia.org/wiki/Integer_programming

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.

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.

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.

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.

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

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.

I'm not aware of, and could not find, any such regulations that apply to non-lithium dry cell batteries.

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.

Amazon does the same thing, but since it is primarily a fulfillment company, it does end up doing most of that itself.

Correct, many third party sellers ship things on Jet (just like on Amazon). Unlike Amazon, it is less clear who is shipping a given item.

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

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

Something that glpk/gurobi should be used for?

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

Integer programming. Which makes it a lot more complex.

Gurobi is sloooooooooooow, and scales pretty badly.

What's better than Gurobi? I used it at a previous job and we weren't aware of anything better (but it also seemed slow and not great at scaling).

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

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!

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.

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

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!

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.

People should read the article before commenting but they rarely do.

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.