文档

广告流量分发-线性规划

更新时间:

行业背景

智能推送是可以基于用户行为和兴趣的个性化内容进行推送。是通过分析用户的历史行为、关注点和偏好,智能推送系统可以提供给用户最相关、有价值的信息、产品或服务。这个优化问题也可以通过数学规划的方法进行建模和求解。

例如:在很多视频在线流量调控场景,需要在保证每个视频内容播放量的同时,使得播放总量最大化。这种场景可以包括广告、通知、宣发内容推送等各种类型。而线上流量是有限的,且不同的宣发内容对用户的吸引力均不相同。

业务调研、数据量化、数学建模

在使用优化技术的时候,需要更详细的调研业务的需求,整理相关的业务逻辑和数据,并量化表示它。然后采用数学规划的方法进行数学建模。

此部分细节较多,可在案例视频流量调控中查阅细节,此处我们仅列出数学公式如下,参数部分请点击案例链接查看:

image.svg

其中i为视频内容、u为用户群、CTR为预估点击率、VV为内容的播放量保量值。

以上公式对应的约束有:

  • 保证视频的播放总量在范围内

  • 保证每个用户都有视频可以看

源代码

MindOpt支持多种编程语言或者建模语言来调用。此处仅列出一种供参考:

MindOpt APL建模语言调用

MindOpt APL建模语言的源代码(可在视频流量调控上试运行):

##====MindOpt APL 建模语言版本代码====

# LP_4_distribution.mapl

# 声明集合
set USERS := { "user0", "user1" };
set ITEMS := {"item0", "item1", "item2"};
set RANGE := { "lower" };

# 声明参数
param CTR[ITEMS * USERS] := 
         | "user0" , "user1" |
|"item0" | 0.52    , 0.92    |
|"item1" | 0.31    , 0.93    |
|"item2" | 0.82    , 0.91    |;

param Broadcast_Num_Range[RANGE * ITEMS] := 
         |"item0","item1", "item2"|
|"lower" | 0     ,0      ,   1    |;

# 声明变量
var X_Probability[USERS * ITEMS] >= 0;  

# 声明目标
maximize Total_CTR_Reward: sum {<u, i> in USERS * ITEMS} CTR[i, u] * X_Probability[u, i]; 

# 声明约束
subto Each_Item_Broadcast_In_Range: #视频的播放量在范围内
    forall {<i> in ITEMS }
      sum {<u> in USERS} CTR[i, u] * X_Probability[u, i] >= Broadcast_Num_Range["lower",i];

subto Each_User_Total_X_Probability:  #每个用户总有视频看
    forall {<u> in USERS}
      sum {<i> in ITEMS} X_Probability[u, i] == 1; 

#--------------------------

print "-----------------用MindOpt求解---------------";
option solver mindopt;     # (可选)指定求解用的求解器,默认是MindOpt
solve;         # 求解

print "-----------------Display---------------";
display;        # 展示结果

print "目标函数总收益是:", sum {<u, i> in USERS * ITEMS} CTR[i, u] * X_Probability[u, i];

结果和结果用法

不同代码日志打印不一样。部分结果日志打印如下所示:

...
Model summary.
 - Num. variables     : 6
 - Num. constraints   : 5
 - Num. nonzeros      : 12
 - Bound range        : [1.0e+00,1.0e+00]
 - Objective range    : [3.1e-01,9.3e-01]
 - Matrix range       : [3.1e-01,1.0e+00]
...
Simplex method terminated. Time : 0.002s


OPTIMAL; objective 1.75
...
-----------------结果---------------
目标函数总收益是:1.746043956043956

目标的最优解是:1.75。更多解的细节,如决策变量的取值、验证约束是否正确,可以通过print命令打印来显示,变量的取值也可以从程序运行写的.sol文件里面获取,还可以调用display获取所有变量的。

如运行如下指令,验证“保证视频的播放总量在范围内”这个约束:

forall {<i> in ITEMS }
    print ' 保量要求lb为{},优化计算后预估点击量{}为{}'%Broadcast_Num_Range['lower',i],i,sum {<u> in USERS} CTR[i, u] * X_Probability[u, i], 
    sum {<u> in USERS} CTR[i, u] * X_Probability[u, i];

验证结果:

 保量要求lb为0,优化计算后预估点击量item0为0
 保量要求lb为0,优化计算后预估点击量item1为0.746043956043956
 保量要求lb为1,优化计算后预估点击量item2为1

运行如下代码,将输出打印为csv格式,作为广告流量分发问题的解决方案:

print "{}, {}, {}" % "视频", "用户", "播放概率" : "Solution.csv";
close "Solution.csv";

forall {<i,u> in ITEMS*USERS}
    print "{}, {}, {}" % u, i, X_Probability[u, i] >> "Solution.csv";

close "Solution.csv";

结果如下:

image.png

即,将第2号视频播放给第0号用户的概率为1,

将第1号视频播放给第1号用户的概率为0.8,

将第2号视频播放给第1号用户的概率为0.2。

  • 本页导读 (0)