An Efficient Local Search Algorithm for Large GD Advertising Inventory Allocation with Multilinear Constraints

The Guaranteed Delivery (GD) advertising is a crucial component of the online advertising industry, and the allocation of inventory in GD advertising is an important procedure that influences directly the ability of the publisher to fulfill the requirements and increase its revenues. Nowadays, as the requirements of advertisers become more and more diverse and fine-grained, the focus ratio requirement, which states that the portion of allocated impressions of a designated contract on focus media among all possible media should be greater than another contract, often appears in business scenarios. However, taking these requirements into account brings hardness for the GD advertising inventory allocation as the focus ratio requirements involve non-convex multilinear constraints. Existing methods which rely on the convex properties are not suitable for processing this problem, while mathematical programming or constraint-based heuristic solvers are unable to produce high-quality solutions within the time limit. Therefore, we propose a local search framework to address this challenge. It incorporates four new operators designed for handling multilinear constraints and a two-mode algorithmic architecture. Experimental results demonstrate that our algorithm is able to compute high-quality allocations with better business metrics compared to the state-of-the-art mathematical programming or constraint based heuristic solvers. Moreover, our algorithm is able to handle the general multilinear constraints and we hope it could be used to solve other problems in GD advertising with similar requirements.