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