4 ms·

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 d

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 9y ago
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).
- frankc 9y ago
  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.
  - vladTheInhaler 9y ago
    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.
rkwasny 9y ago
+1 this looks like a integer programming problem that can be just solved exactly without brute forcing the solution.
- bulldoa 9y ago
  isn't integer programming way harder than normal class of convex optimization problems like quadratic, second order cone or semidefinite?
  - rishabhparikh 9y ago
    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 https://en.wikipedia.org/wiki/Integer_programming
    - maksimum 9y ago
      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.

dragontamer 9y ago

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

frankc 9y ago
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.
- vladTheInhaler 9y ago
  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.

rkwasny 9y ago

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

bulldoa 9y ago
isn't integer programming way harder than normal class of convex optimization problems like quadratic, second order cone or semidefinite?
- rishabhparikh 9y ago
  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 https://en.wikipedia.org/wiki/Integer_programming
  - maksimum 9y ago
    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.