10 ms·
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 us
by 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 agoIf 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 agoIn 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.