How a Bi‑Objective Local Search Improves Contract Ad Inventory Allocation

Abstract

Guaranteed‑delivery (GD) advertising consists of an offline selling phase and an online delivery phase. Existing studies treat these phases separately, ignoring the impact of online delivery on offline allocation. We propose a bi‑objective inventory allocation formulation that (1) maximizes the number of impressions allocated to new orders to improve inventory utilization and (2) balances the distribution of allocated impressions across supply nodes to increase fulfillment rates. Because the problem is high‑dimensional, multi‑objective, and heavily constrained, we design an efficient alternating local‑search algorithm (BOLS). Experiments on real‑world datasets show that BOLS outperforms state‑of‑the‑art multi‑objective evolutionary algorithms (MOEAs) and the commercial optimizer Gurobi.

Background

GD advertising is crucial for precise e‑commerce marketing, aiming to deliver ads to users who satisfy complex demographic and device constraints. Traditional GD allocation methods focus solely on maximizing the sellable volume for new orders based on supply‑demand capacities, neglecting the risk of under‑delivery during the online phase, which can cause contract violations and penalties. Our work introduces a novel bi‑objective GD allocation problem that jointly considers (a) the maximum feasible impressions for new orders and (b) the fulfillment rate during online delivery.

Problem Modeling

2.1 Order‑Level Inventory Allocation

The allocation can be represented as a bipartite graph. Left‑hand nodes are supply nodes, each aggregating inventory characterized by attributes such as city, gender, device, etc. Right‑hand nodes are demand nodes representing ad orders. An adjacency matrix indicates whether a supply node can serve a demand node. Let S be the set of supply nodes, D the set of demand nodes, and x_{ij} the number of impressions assigned from supply i to demand j .

Traditional GD allocation maximizes \(\sum_{i}\!x_{i,new}\) while satisfying existing orders. However, this can lead to supply imbalance and high fulfillment risk. We therefore add a second objective that minimizes the deviation between the proportion of total available supply and the proportion of allocated impressions for each supply node.

Formally, given supply set S , existing demand set D_{old} , and a new demand d_{new} , we seek an allocation X that optimizes:

Objective 1 : Maximize impressions for the new order (implemented as a minimization of the negative value).

Objective 2 : Minimize the imbalance of allocated impressions across supply nodes.

subject to multiple constraints:

Supply capacity limits.

Fulfillment of all existing orders.

Non‑negativity and integrality of x_{ij} .

2.2 Pareto Front

The problem is a multi‑objective integer program. A solution p dominates q if it is no worse in both objectives and strictly better in at least one. The set of non‑dominated feasible solutions forms the Pareto front, which we aim to approximate.

Bi‑Objective Local Search Algorithm (BOLS)

3.1 Algorithm Framework

BOLS starts with a greedy initialization to obtain a feasible (though not necessarily optimal) solution quickly. The main optimization loop consists of two phases: a feasibility‑search phase (lines 3‑5) and an improvement phase (lines 7‑16). The feasibility phase repeatedly applies SatisfyingMove until all constraints are satisfied. The improvement phase alternates between improving each objective using ImproveMove. When no improvement is observed after a predefined number of iterations, the algorithm switches focus to the other objective.

3.2 Initialization

We generate an initial solution by minimizing the imbalance objective (2) while ensuring that the supply‑capacity constraints (4) are satisfied via a simple linear transformation. The initial solution may be infeasible for the first objective, but it provides a good starting point for the alternating search.

3.3 Satisfying Move (Feasibility Phase)

SatisfyingMove

attempts to repair constraint violations by adjusting one or two variables. If a single‑variable adjustment cannot satisfy a violated constraint, a multi‑selection best‑strategy (BMS) is invoked, which samples several random pairs of demand orders, evaluates the resulting balance score, and selects the best move.

3.4 Improve Move (Optimization Phase)

During improvement, ImproveMove alternately optimizes the two objectives. It first tries to improve the currently focused objective by tweaking a randomly selected variable; if no improvement is found after a set number of trials, it attempts a two‑variable adjustment. The algorithm evaluates the change in both objectives and accepts moves that improve the focused objective without worsening the other beyond a tolerance.

3.5 Updating the Pareto Set

After generating a feasible solution, UpdatePareto inserts it into the current Pareto set if it is non‑dominated, and removes any existing solutions that are now dominated. This maintains an up‑to‑date approximation of the Pareto front throughout the search.

Experimental Results

4.1 Evaluation Metrics

We evaluate algorithms using four metrics: (1) the number of instances where the algorithm finds the optimal solution, (2) the number of instances where a feasible solution is found within the time limit, (3) the hyper‑volume of the obtained Pareto set, and (4) a revenue‑based metric (SR) that reflects practical advertising income.

4.2 Comparison with MOEAs

We compare BOLS against four popular multi‑objective evolutionary algorithms (MOEAs): NSGA‑II, NSGA‑III, U‑NSGA‑III, and C‑TAEA. Results on five datasets and three time limits (10 s, 60 s, 300 s) show that while MOEAs excel at quickly finding feasible solutions in small search spaces, BOLS consistently yields higher‑quality Pareto fronts and dominates MOEAs on larger instances.

4.3 Comparison with Gurobi

We also benchmark BOLS against the commercial solver Gurobi using both its exact (Gurobi‑E) and heuristic (Gurobi‑H) modes. Gurobi solves the weighted‑sum single‑objective version of the problem but cannot directly produce a Pareto set. Across the five datasets, BOLS outperforms Gurobi at the 10 s time limit on all instances and remains competitive at longer limits, especially on larger supply‑node datasets.

4.4 Revenue Comparison

Using the SR metric, BOLS achieves a 1.4 %–23.5 % revenue increase over Gurobi‑E and a 3.7 %–19.5 % increase over Gurobi‑H, depending on the dataset. In cases where Gurobi fails to find any feasible solution, BOLS still provides a viable allocation.

Conclusion

We introduced a novel bi‑objective inventory allocation model for guaranteed‑delivery advertising that simultaneously maximizes new‑order impressions and balances supply distribution to improve fulfillment rates. The proposed BOLS algorithm efficiently approximates the Pareto front and outperforms both multi‑objective evolutionary algorithms and the commercial optimizer Gurobi on real‑world datasets. Future work includes parallelizing BOLS for larger scales and extending the framework to other bipartite allocation problems such as communication resource allocation and supply‑chain inventory distribution.

References

Nader Al Theeb et al., "Optimization of vehicle routing with inventory allocation problems in Cold Supply Chain Logistics," Computers & Industrial Engineering, 2020.

Peiji Chen et al., "Ad serving using a compact allocation plan," ACM EC 2012.

Kalyanmoy Deb, "Multi‑objective optimisation using evolutionary algorithms," Springer, 2011.

Andrzej Jaszkiewicz, "Genetic local search for multi‑objective combinatorial optimization," Eur. J. Operational Research, 2002.

Wuyang Mao et al., "End‑to‑End Inventory Prediction and Contract Allocation for Guaranteed Delivery Advertising," KDD 2023.

Hong Zhang et al., "A request‑level guaranteed delivery advertising planning: Forecasting and allocation," KDD 2020.