线上运筹优化公式推导

营销本质是个预算分配问题，即如何在有限资源约束下实现收益最大化。当用户进入营销场景时，我们需要确定是否给该用户发放红包以及发放红包的面额。

选择发放用户和发放面额是一个典型的分组背包问题(MCKP, Multiple Choice Knapsack Problem)，在成本约束下的的券核销率最大化。

问题定义

$$min -\sum_{i,j} x_{ij}p_{ij} \\ \begin{aligned} \text { s.t. } x_{ij} & \in \{0, 1\} \\ \sum_{j} x_{ij} &= 1 \\ \sum_{i,j} x_{ij} c_{ij} &\leq C \\ \end{aligned}$$

• $x_{ij}$ 表示是否给用户$i$发放红包$j$
• $p_{ij}$ 表示用户$i$在红包$j$下的核销率，由量价模型预估产生
• $c_{ij}$ 表示给用户$i$发放红包$j$的成本，即红包$j$的面额
• $C$ 表示总成本

构造拉格朗日对偶函数

$$\begin{aligned} L(x, \lambda, u) & =-\sum_{i, j} x_{ij}p_{ij}+ \lambda\left(\sum_{i,j} x_{ij}c_{ij}-C\right) \\ & =\sum_{i,j} x_{ij}\left(-p_{ij}+ \lambda c_{ij}\right) - \lambda C \\ \text { s.t. } &\lambda \geq 0, \ u_i \geq 0, \ \sum_{j} x_{ij} = 1 \end{aligned}$$ $$\begin{aligned} D(\lambda, u) & =\max _{\lambda, u} \min _x L(x, \lambda, u) \\ & =\max _{\lambda, u} \min _x\left(\sum_{i,j} x_{ij}\left(-p_{ij}+ \lambda c_{ij}\right) - \lambda C \right) \\ \text { s.t. } &\lambda \geq 0, \ u_i \geq 0, \ \sum_{j} x_{ij} = 1 \end{aligned}$$

如果给每个用户都发券，即$x_{ij}=1$，则$D(\lambda, u) = \max _{\lambda, u} \min _x\left(\sum_{i,j} -p_{ij}+ \lambda (c_{ij}-avg_{ij}) \right)$，$avg_{ij}$表示单均约束，$\sum_{ij} avg_{ij} = C$。

求解最优解

针对上述经典优化问题，每条样本的最优解满足如下条件：

$$\forall i,j, \quad x_{ij} = 1 \Longleftrightarrow j = argmin_j -p_{ij^{\prime}}+ \lambda c_{ij^{\prime}}$$

假设给定用户$i$，以及确定发放红包$j^{\prime}$，为了使$-p_{ij^{\prime}}+ \lambda c_{ij^{\prime}}$最小，则有：

$$\begin{aligned} j^{\prime} &= argmin_{j} -p_{ij}+ \lambda c_{ij} \\ &= argmax_{j} p_{ij} - \lambda c_{ij} \\ \end{aligned}$$

线上运筹的时候，选择发放$j^{\prime}$红包。