Matching demand to supply in internet marketplaces (e-commerce, ride-sharing, food delivery, professional services, advertising) is a global inference problem that can be formulated as a Linear Program (LP) with (millions of) coupling constraints and (up to a billion) non-coupling polytope constraints. Until recently, solving such problems on web-scale data with an LP formulation was intractable. Recent work (Basu et al., 2020) developed a dual decomposition-based approach to solve such problems when the polytope constraints are simple. In this work, we motivate the need to go beyond these simple polytopes and show real-world internet marketplaces that require more complex structured polytope constraints. We expand on the recent literature with novel algorithms that are more broadly applicable to global inference problems. We derive an efficient incremental algorithm using a theoretical insight on the nature of solutions on the polytopes to project onto any arbitrary polytope, that shows massive improvements in performance. Using better optimization routines along with an adaptive algorithm to control the smoothness of the objective, improves the speed of the solution even further. We showcase the efficacy of our approach via experimental results on web-scale marketplace data.
翻译:互联网市场(电子商务、搭便车、食品供应、专业服务、广告)的需求匹配是一个全球性的推论问题,可以作为线性方案(LP)来制定,同时有(百万)连带制约和(高达10亿)非连带的多功能制约。直到最近,用LP的配方解决网络规模数据中的这类问题是难以解决的。最近的工作(Basu等人,2020年)发展了一种双分解法,以便在多功能制约简单时解决这类问题。在这项工作中,我们提出需要超越这些简单的多功能平台,并展示需要更复杂结构化多功能制约的现实世界互联网市场。我们利用新的算法来扩展最近的文献,这些新的算法更广泛地适用于全球推论问题。我们利用对多功能解决方案的性质的理论洞察来获得高效的递增算法,以投射到任意的多功能上,这显示出巨大的绩效改进。我们利用更好的优化程序来控制目标的平滑度,并通过进一步展示我们的实验市场结果。