{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 广告投放问题\n", "\n", "**类别：** 非线性优化\n", "\n", "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n", "\n", "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/advertising-campaign-problem)。\n" ] }, { "cell_type": "markdown", "id": "d31cb6b7", "metadata": {}, "source": [ "## 问题描述\n", "\n", "在**广告投放问题**中,一组广告可以在各个时间段上播出。每条广告在触达目标受众(例如特定年龄段)时会产生预期的营销收益。当一条广告被分配到某个时间段时,它会以给定的概率触达其目标受众。如果该广告在多个时间段播出,该概率会增大。目标是为每个时段分配一条广告,以使整个广告活动的总预期收益最大化。\n", "\n", "该问题也被称为武器目标分配问题(Weapon Target Assignment Problem, WTA)。关于该问题的更多细节,请参阅[维基百科](https://en.wikipedia.org/wiki/Weapon_target_assignment_problem)。\n", "\n", "### 学习要点\n", "\n", "- 使用 OptAgent 的 `set` 建模分配给每个广告的时段\n", "- 使用 `array` 和 `partition` 确保每个时段恰好分配给一条广告\n", "- 使用 `prod` 和 `lambda_function` 构建每条广告的非线性预期收益\n" ] }, { "cell_type": "markdown", "id": "d5679723", "metadata": {}, "source": [ "## 数据\n", "\n", "本算例是对 [GitHub](https://github.com/tuliotoffolo/wta/tree/main/data) 上提供的武器目标分配算例的略微修改版本。数据格式如下:\n", "\n", "- 第一行:时段数量,广告数量\n", "- 接下来每一行对应一条广告的营销收益\n", "- 之后的每一行包含:\n", "\n", "- 时段的索引\n", "- 广告的索引\n", "- 该广告在该时段触达目标受众的概率\n" ] }, { "cell_type": "markdown", "id": "21cd591a", "metadata": {}, "source": [ "## 建模思路\n", "\n", "广告投放问题的 OptAgent 模型使用集合决策变量。我们通过 `set` 为每条广告定义一个集合,其中包含分配给该广告的所有时段；再用 `array` 将这些集合组成一等数组,并施加 `partition` 约束,确保每个时段恰好被分配一条广告。\n", "\n", "对于每条广告,我们用 `lambda_function` 表达各个已分配时段的未触达概率,再用集合聚合 `prod` 计算整场活动均未触达的概率。用 1 减去该乘积并乘以营销收益,即可得到广告的预期收益。最后对所有广告的预期收益求和并最大化。\n" ] }, { "cell_type": "markdown", "id": "798d3a77", "metadata": {}, "source": [ "## Python 实现\n" ] }, { "cell_type": "code", "execution_count": null, "id": "advertising-model", "metadata": {}, "outputs": [], "source": [ "from pathlib import Path\n", "\n", "from optagent import OptModel, solve\n", "\n", "\n", "def read_instance(instance_filename):\n", " with open(instance_filename, encoding=\"utf-8\") as f:\n", " lines = f.readlines()\n", "\n", " nb_slots = int(lines[0].split()[0])\n", " nb_ads = int(lines[0].split()[1])\n", " ad_profits = [int(lines[i]) for i in range(1, nb_ads + 1)]\n", " probabilities_data = [[0.0 for _ in range(nb_ads)] for _ in range(nb_slots)]\n", " for line in lines[nb_ads + 1 :]:\n", " values = line.split()\n", " s = int(values[0])\n", " a = int(values[1])\n", " probabilities_data[s][a] = float(values[2])\n", " return nb_slots, nb_ads, ad_profits, probabilities_data\n", "\n", "\n", "def main(input_file, output_file=None, time_limit=60):\n", " _, _, ad_profits, probabilities_data = read_instance(input_file)\n", " nb_slots = len(probabilities_data)\n", " nb_ads = len(ad_profits)\n", " model = OptModel()\n", "\n", " # assignments[a] is the set of slots assigned to ad a.\n", " assignments = [model.set(nb_slots) for a in range(nb_ads)]\n", " assignments_array = model.array(assignments)\n", "\n", " # Every slot must be assigned to exactly one ad.\n", " model.constraint(model.partition(assignments_array))\n", "\n", " # The empty product is 1, so an ad with no slots contributes zero profit.\n", " probabilities = model.array(probabilities_data)\n", " ad_profit_expressions = []\n", " for a in range(nb_ads):\n", " ad_index = a\n", " miss_probability = model.prod(\n", " assignments[a],\n", " model.lambda_function(\n", " lambda slot: 1 - model.at(probabilities, slot // 1, ad_index)\n", " ),\n", " )\n", " ad_profit_expressions.append(ad_profits[a] * (1 - miss_probability))\n", " total_profit = model.sum(ad_profit_expressions)\n", "\n", " model.maximize(total_profit)\n", " solution = solve(model, time_limit_s=float(time_limit))\n", " result_values = {'total_profit': total_profit.value, **{f'ad_{a}': assignment.value for a, assignment in enumerate(assignments)}}\n", "\n", " lines = [\n", " f\"Nb slots = {nb_slots}; Nb ads = {nb_ads}; \"\n", " f\"Total profit = {result_values['total_profit']}\"\n", " ]\n", " for a in range(nb_ads):\n", " assigned_slots = result_values[f\"ad_{a}\"]\n", " if assigned_slots:\n", " slots = \", \".join(f\"slot {slot}\" for slot in sorted(assigned_slots))\n", " lines.append(f\"Ad {a} assigned to {slots}\")\n", "\n", " result_text = \"\\n\".join(lines)\n", " print(result_text)\n", " if output_file is not None:\n", " Path(output_file).write_text(result_text + \"\\n\", encoding=\"utf-8\")\n", " return solution\n" ] }, { "cell_type": "markdown", "id": "advertising-runs", "metadata": {}, "source": [ "## 本地运行\n", "\n", "Notebook 直接调用 `main` 并显式传入实例路径。以下代码格相互独立，可以按需要单独运行；调整 `time_limit` 可以控制每个实例的求解时间。\n" ] }, { "cell_type": "code", "execution_count": null, "id": "advertising-instance-dir", "metadata": {}, "outputs": [], "source": [ "from pathlib import Path\n", "\n", "INSTANCE_DIR = Path.cwd() / \"instances\"\n", "print(\"Instances:\", INSTANCE_DIR)\n" ] }, { "cell_type": "code", "execution_count": null, "id": "advertising-run-small", "metadata": {}, "outputs": [], "source": [ "solution_50x100 = main(\n", " INSTANCE_DIR / \"ad_campaign_50x100.txt\",\n", " time_limit=1,\n", ")\n" ] }, { "cell_type": "code", "execution_count": null, "id": "advertising-run-medium", "metadata": {}, "outputs": [], "source": [ "solution_100x200 = main(\n", " INSTANCE_DIR / \"ad_campaign_100x200.txt\",\n", " time_limit=1,\n", ")\n" ] }, { "cell_type": "code", "execution_count": null, "id": "advertising-run-large", "metadata": {}, "outputs": [], "source": [ "solution_150x300 = main(\n", " INSTANCE_DIR / \"ad_campaign_150x300.txt\",\n", " time_limit=1,\n", ")\n" ] } ], "metadata": { "kernelspec": { "display_name": ".venv", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.14.6" } }, "nbformat": 4, "nbformat_minor": 5 }