Efficient Local Search for Guaranteed Display Advertising Inventory Allocation with Multilinear Constraints

Guaranteed Delivery (GD) advertising inventory allocation often involves media‑preference requirements that introduce non‑convex multilinear constraints. Existing mathematical programming solvers and heuristic methods cannot reliably produce high‑quality solutions within strict time limits. This paper proposes a two‑stage local‑search framework (LS‑IMP) that incorporates four novel operators designed specifically for handling such nonlinear constraints. Experiments on real‑world GD data demonstrate that LS‑IMP consistently yields superior solution quality and speed compared with commercial solvers and constraint‑programming heuristics, and the work has been accepted at KDD 2024.

Background: GD contracts pre‑lock impression counts for advertisers. Over‑selling incurs penalties, while under‑selling reduces platform revenue. Traditional allocation methods only address linear or convex constraints. Modern business scenarios demand media‑specific preferences (e.g., a skincare product should receive a larger share on a beauty app than headphones), which translate into non‑convex multilinear constraints.

Problem Modeling: The allocation problem is formulated as an integer multilinear programming (IMP) problem on a bipartite graph linking supply nodes (city‑media‑OS) to demand nodes (contracts). Three constraint families are defined: (1) supply capacity, (2) demand fulfillment, and (3) focus constraints that enforce relative media preferences between contracts of the same advertiser. Multilinear constraints are expressed via adjacency matrices.

Solution: LS‑IMP adopts a double‑mode search. In the infeasible mode, four new neighborhood operators—critical move, boundary move, reduction move, and push move—are applied to satisfy violated constraints. Once all constraints are satisfied, the algorithm switches to feasible mode, where operators aim to reduce the objective (maximizing allocated impressions). Weighted scoring and mode‑switching mechanisms guide the search toward high‑quality solutions.

Experiments: LS‑IMP is benchmarked against Gurobi 10.0.0, SCIP 8.0.1, and the heuristic solver Yuck on five real GD datasets. Evaluation metrics include inventory utilization (#UR), fulfillment rate (#FR), winning solutions (#win), feasible solutions (#feas), and solving time. Within a 60‑second budget, LS‑IMP achieves higher #UR and #FR, more #win and #feas, and converges faster than the baselines. Longer time limits (300 s, 1000 s) confirm its rapid convergence.

Conclusion: The proposed local‑search algorithm effectively solves GD inventory allocation with multilinear constraints, outperforms state‑of‑the‑art solvers, and is applicable to other contract‑allocation problems requiring nonlinear constraint handling.