O&SCM运营与供应链管理知识库

LATEST RESEARCH FRONTIERS / 最新研究前沿

即时零售 · 品类优化 · 整数规划

门店该备哪些货,
线上又该向谁推荐?

An Integer Programming Approach for Quick-Commerce Assortment Planning

481 个原生公式 20:30 视频 14:14 音频

CHINESE LECTURE VIDEO / 中文讲解视频

即时零售品类规划

从线下备货与线上推荐的关系出发,介绍消费者选择模型、整数规划重构与割平面算法。

20 分 30 秒 · 854×480
CHINESE AUDIO SUMMARY / 中文音频总结

30分钟送达背后的货架算法

为什么门店不一定应该只选线下销量最高的商品?从半小时送达的场景理解全渠道选品。

14 分 14 秒 · 单声道 AAC
FULL PAPER SUMMARY / 完整论文总结

即时零售品类规划的整数规划方法:全文总结与理论解析

《An Integer Programming Approach for Quick-Commerce Assortment Planning》
全文深度总结与理论解析

——文献概览、核心贡献、模型函数解析、命题推论算例详解与经管启示

一、 文献基本信息与全文核心总结

1.1 论文与出版信息

项目 详细内容
论文题目 An Integer Programming Approach for Quick-Commerce Assortment Planning(即时零售品类规划的整数规划方法)
作者姓名(不翻译) Yajing Chen, Taotao He (通讯作者), Ying Rong, Yunlong Wang
作者署名单位 Antai College of Economics and Management & Data-Driven Management Decision Making Lab, Shanghai Jiao Tong University(上海交通大学安泰经济与管理学院)
发表期刊 Management Science(管理科学顶刊,UTD-24 / FT-50)
出版卷期与页码 2026年10月,第72卷第10期(Vol. 72, No. 10),第8789–8809页
DOI 标识 https://doi.org/10.1287/mnsc.2023.02996
核心关键词 Quick commerce(即时零售);Assortment optimization(品类优化);Multinomial logit model(多项式Logit模型);Mixed-integer nonlinear programming(混合整数非线性规划);Convexification(凸化);Cutting plane(割平面)

1.2 全文脉络与核心内容总结

(1)研究背景与问题提出:近年来,传统线下实体零售增速放缓,但餐饮、生鲜食品、日常杂货和鲜花等具有高度时效性的商品品类(Time-sensitive products),由于消费者要求在1小时甚至30分钟内即时送达,传统电商提供的“次日达”服务难以满足需求。为此,实体门店一方面与 DoorDash、Delivery Hero、Grab 等第三方即时配送平台合作,另一方面以阿里巴巴旗下的“盒马鲜生(Hema Fresh)”以及亚马逊收购“全食超市(Whole Foods)”为代表,直接依托本地实体门店服务周边3公里内的线上与线下消费者,由此催生了预计2029年全球市场规模达2650亿美元的即时零售(Quick Commerce)商业模式。在即时零售模式下,为了利用店员就地快速拣货以兑现极速达承诺,推荐给任意线上细分客群的个性化商品品类,必须实际备货并存在于线下实体门店的库存品类中。这一独特的“物理联动约束(Physical linkage constraint)”将线下门店品类决策与线上多客群个性化品类推荐紧密耦合在一起。

(2)模型框架与计算挑战:文章正式定义了即时零售品类规划问题(Quick-Commerce Assortment Problem, 简称 QAP)。假设市场上共有 nn 种备选商品(集合 N:={1,…,n}N\ : = \ \left\{ 1,\ \ldots,\ n \right\}),线下门店面对1类常规客群 {0}\left\{ 0 \right\},线上渠道借助浏览与购买大数据将消费者细分为 mm 类客群(集合 M:={1,…,m}M\ : = \ \left\{ 1,\ \ldots,\ m \right\}),全体客群集合记为 M+={0}∪MM^{+}\ = \ \left\{ 0 \right\}\ \cup \ M。各类消费者的选择行为均遵循各自独立的多项式 Logit(MNL)模型(或能刻画零概率支配关系的两阶段 Luce 模型,2SLM)。零售商需要联合决策线下实体门店的备货品类 𝐱0\mathbf{x}_{0} 以及针对每类线上客群的个性化推荐品类 𝐱i\mathbf{x}_{i},在满足物理联动约束 𝐱0≥𝐱i\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i} 及各类运营约束 ℱi⊆{0,1}n\mathcal{F}_{i}\ \subseteq \ \left\{ 0,\ 1 \right\}^{n} 的前提下,最大化全渠道期望总收益。作者证明,即便没有任何运营约束、仅有单一线上客群且线上线下商品价格完全一致,QAP 依然是 NP-hard 问题;同时,先独立优化线下品类再从中筛选线上品类的“两步收益排序启发式策略(2-STEP-RO)”由于忽视了线上消费者的差异化偏好,会导致显著的收益损失与品类多样性缩水。

(3)核心方法论——部分凸松弛与多面体凸化:为了将这一非凸、非可分的混合整数非线性规划(MINLP)问题求解至全局最优,作者提出了一套极具创新性的整数规划重构框架。首先,通过 Charnes-Cooper(CC)变换将分式收益目标转化为关于“选择概率变量” (yi0,𝐲i)\left( y_{i0},\ \mathbf{y}_{i} \right) 的线性函数,并消去线上二元品类变量 𝐱i\mathbf{x}_{i},使原问题含有的二元整数变量数量从 mn+nmn\ + \ n 大幅缩减至 nn。其次,利用物理联动约束定义可行域支撑面的几何性质,作者证明了将每类线上客群的选择概率集合 Πi(ℱi)\Pi_{i}\left( \mathcal{F}_{i} \right) 替换为其紧凸松弛(即凸包 conv(Πi(ℱi))\text{conv}\left( \Pi_{i}\left( \mathcal{F}_{i} \right) \right))可得完全等价的精确重构模型(QAP-RLX)。接着,作者从几何上将选择概率集分解为“概率归一化超平面 HH”与“IIA-品类锥 KK”的交集,证明了只要线上运营约束的凸包 conv(ℱi)\text{conv}\left( \mathcal{F}_{i} \right) 具有紧致扩展表述(Compact extended formulation),则选择概率集的凸包 conv(Πi(ℱi))\text{conv}\left( \Pi_{i}\left( \mathcal{F}_{i} \right) \right) 也具有紧致多面体扩展表述(例如利用链多面体紧致表述精确处理 2SLM 模型)。最后,针对线下门店决策 𝐱0\mathbf{x}_{0} 与各客群选择概率 (yi0,𝐲i)\left( y_{i0},\ \mathbf{y}_{i} \right) 之间的双线性耦合约束(OFF-BI 与 LINK-BI),鉴于全商品联合双线性集的分离问题是 NP-hard,作者聚焦于单商品混合整数双线性集 ℬj\mathcal{B}_{j},构造了无需引入任何额外辅助变量的指数级线性有效不等式族 (UNDER)与(OVER),并设计了复杂度仅为 𝒪(n log n)\mathcal{O}\left( n\text{ log }n \right) 的改进选择概率排序分离算法(Algorithm 1),严格证明了(UNDER)与(OVER)完全刻画了单商品双线性集 ℬj\mathcal{B}_{j} 的凸包。

(4)割平面实现、数值实验与多元应用拓展:基于上述凸包理论,作者构建了精确求解 QAP 的混合整数规划模型 CH(针对标准 MNL)与 CH-Chain(针对 2SLM),并结合强化版 McCormick 基础模型(CH-0)与两轮割平面迭代(K=2K\ = \ 2,Algorithm 2)开发了 CH-2 与 CH-Chain-2 算法。在大规模数值实验中(商品数达200、线上客群达100),CH-2 与 CH-Chain-2 在500秒内成功求解了95%以上的算例,计算速度、搜索节点数和鲁棒性全面碾压最先进的二阶锥整数规划方法(Conic, Sen et al. 2018)与传统大M混合整数线性规划(MILP)。此外,文章第7节展示了该理论框架的四大拓展应用:① 导出一般线性约束下 MNL 品类规划的紧致 LP 表述(推广了全单模矩阵 TU 约束并涵盖平衡矩阵覆盖约束与 2SLM);② 利用单商品凸包几何性质设计随机舍入算法,证明了当线上客群服从独立需求模型(IDM)且线下存在先行约束(Precedence constraints)时,问题可转化为多项式时间可解的线性规划(推广了 Cao et al. 2023 的混合模型结果);③ 通过简单调整模型参数,将 QAP 无缝拓展至“城市前置仓模式(如叮咚买菜)”与“门店前店后仓专供模式”;④ 结合加权价格舍入策略,将 QAP 最优选择概率转化为可落地的日度整数库存补货决策。

二、 文章的核心贡献

本文在运筹学整数规划理论(分式规划凸化、混合整数双线性规划多面体理论)与全渠道/即时零售品类管理两个维度均取得了突破性进展,全文的核心贡献可高度凝练为以下三个方面:

核心贡献一:线上客群选择概率集的凸包精确性证明与多面体紧致扩展刻画(Theorem 1 & Theorem 2)

1. 非可分联动问题下的精确凸松弛(Theorem 1):尽管即时零售品类规划问题(QAP)因存在跨渠道物理联动约束 𝐱0≥𝐱i\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i} 而不可按客群直接分解,本文首次证明了将每个线上细分客群的选择概率集合替换为其最紧凸松弛(即凸包 conv(Πi(ℱi))\text{conv}\left( \Pi_{i}\left( \mathcal{F}_{i} \right) \right)),同时保持线下门店品类变量为二元整数,所得松弛模型(QAP-RLX)与原问题具有完全相同的全局最优目标值。这一结论直接将模型中的二元决策变量维度从 mn+nmn\ + \ n 降至 nn,消除了线上客群规模 mm 带来的组合爆炸。

2. 基于 Luce 选择公理几何结构的紧致多面体表示(Theorem 2):通过挖掘 Luce 选择公理背后的几何结构,将选择概率集分解为“概率归一化超平面 HH”与“无关备选项独立性(IIA)品类锥 KK”的交集,证明了只要运营约束集 ℱi\mathcal{F}_{i} 的凸包 conv(ℱi)\text{conv}\left( \mathcal{F}_{i} \right) 具有多项式规模的紧致多面体扩展表述,则选择概率集的凸包 conv(Πi(ℱi))\text{conv}\left( \Pi_{i}\left( \mathcal{F}_{i} \right) \right) 也必然具有紧致的多面体扩展表述。

3. 对复杂选择模型与经典文献的统一推广:作为典型示范,本文结合链多面体(Chain polytope)的紧致扩展形式,首次给出了两阶段 Luce 模型(2SLM,可刻画现实中普遍存在的零概率支配选择行为)下选择概率集凸包的 𝒪(n2)\mathcal{O}\left( n^{2} \right) 紧致线性描述;同时在第 7.1 节将该凸包定理应用于受约束单渠道 MNL 品类优化,当约束退化为全单模(TU)矩阵时,直接恢复并推广了 Avadhanula et al. (2016) 与 Sumida et al. (2021) 的著名线性规划结论,并将多项式可解边界推进至平衡矩阵(Balanced matrices)覆盖约束。

核心贡献二:品类决策与选择概率间双线性关系的单商品凸包刻画及随机舍入算法(Theorem 3–6)

1. 揭示全商品联合双线性集的复杂性边界(Proposition 3):本文严格证明了刻画线下全部商品品类决策 𝐱0\mathbf{x}_{0} 与选择概率 (y0,𝐲)\left( y_{0},\ \mathbf{y} \right) 之间双线性关系集合 conv(ℬ)\text{conv}(\mathcal{B}) 与 conv(ℬ≤)\text{conv}\left( \mathcal{B}^{\leq} \right) 的分离问题是 NP-hard,从理论上阐明了直接求解全商品联合凸包的不可行性。

2. 无需辅助变量的单商品双线性集凸包完全刻画(Theorem 3–5):针对单商品混合整数双线性集 ℬj\mathcal{B}_{j},本文构造性地推导出了两组指数级数量的线性有效不等式族(UNDER)与(OVER)。不同于传统析取规划(Disjunctive programming)必须引入 𝒪(mn2)\mathcal{O}(mn^{2}) 个额外连续变量、也不同于二阶锥松弛(Sen et al. 2018)无法达到紧凸包,本文证明了(UNDER)与(OVER)在不增加任何额外变量的原变量空间中,精确且完全地刻画了 ℬj≥\mathcal{B}_{j}^{\geq}、ℬj≤\mathcal{B}_{j}^{\leq} 以及 ℬj\mathcal{B}_{j} 的凸包,且其特例(MCCORMICKPLUS)严格强于经典的 McCormick 包络不等式。

3. 改进的选择概率排序快速分离与多项式时间随机舍入(Theorem 4 & Theorem 6):设计了时间复杂度仅为 𝒪(n log n)\mathcal{O}\left( n\text{ log }n \right) 的改进选择概率排序分离算法(Algorithm 1)以高效求解分离问题;并在第 7.2 节利用该单商品凸包的几何极点分解性质,设计了多项式时间随机舍入(Randomized rounding)算法,证明了当线上客群遵循独立需求模型(IDM)且线下门店面临有向图先行约束(Precedence constraints)时,(UNDER)不等式给出了原 NP-hard 变体问题的精确多项式时间可解 LP 表述,实质性地推广了 Cao et al. (2023) 关于混合独立需求与 MNL 模型的研究成果。

核心贡献三:QAP 高效割平面求解框架、卓越的计算优势与全场景商业模式拓展(Algorithm 2 & Section 6–7)

1. 计算效率显著超越现有最优基准:将上述凸包结果与两轮改进选择概率排序割平面算法(Algorithm 2,CH-2 与 CH-Chain-2)相结合,在 Gurobi 求解器上实现了数量级的计算加速。在 200 种商品、100 个线上客群的大规模算例中,CH-2 与 CH-Chain-2 能在 500 秒内解决 95% 的算例(许多算例仅需探索 1 个分支定界节点),而最先进的锥整数规划(Conic)与大 M 线性化(MILP)在相同时间内最多只能解决不到 60% 的算例,且在 2SLM 模型下近乎失效。

2. 证明全渠道联合优化对收益与消费者福利的双重帕累托改进(Proposition 2):从理论上证明了当各客群商品价格排序一致时,QAP 全局最优解在所有渠道提供的商品集合均包含两步收益排序启发式解(𝐱RO≤𝐱QAP\mathbf{x}^{\text{RO}}\ \leq \ \mathbf{x}^{\text{QAP}}),揭示了联合优化不仅提升企业总收益,还同时提高了线上与线下所有消费者的总效用(消费者满意度)。

3. 高度灵活的即时零售商业构型与库存落地整合(Section 7.3 & 7.4):展示了如何通过参数重构,使 QAP 模型直接涵盖“纯线上城市前置仓模式(如叮咚买菜)”以及“实体门店后仓线上专供模式(サブ吸纳了 El Housni and Topaloglu 2023 的个性化价值评估模型)”,并结合考虑缺货动态替代的加权价格舍入规程,打通了从“品类规划”到“日度整数库存补货”的运营闭环。

三、 模型构建与核心函数、集合详解

为了清晰理解论文的数学建模逻辑,本节首先梳理模型的基础符号体系,随后对全文中出现的每一个目标函数、约束函数、变换映射及辅助优化函数进行逐项拆解与经济含义阐释。

3.1 基础集合、下标与决策变量定义

数学符号 名称与定义 经济与运营管理含义
N:={1,…,n}N\ : = \ \left\{ 1,\ \ldots,\ n \right\} 候选商品全集 零售商可选择上架或推荐的全部 nn 种备选商品的集合。
M:={1,…,m}M\ : = \ \left\{ 1,\ \ldots,\ m \right\} 线上消费者细分客群集 借助线上浏览与购买历史数据,将线上消费者划分为 mm 个具有同质偏好的细分客群。
{0}\left\{ 0 \right\} 与 M+M^{+} 线下客群与全体客群集 {0}\left\{ 0 \right\} 代表线下实体门店的单一汇总客群;M+={0}∪MM^{+}\ = \ \left\{ 0 \right\}\ \cup \ M 代表线上与线下所有客群的并集。
αi\alpha_{i} 第 ii 类客群到达概率 到达系统的消费者属于类型 i∈M+i\ \in \ M^{+} 的外生概率,满足归一化条件 ∑i∈M+αi=1\sum_{i \in M^{+}}^{}\alpha_{i}\ = \ 1。
rijr_{ij} 差异化单位商品收益 向第 ii 类消费者售出第 jj 种商品所获得的单位收益(支持模拟 VIP 会员折扣或 App 专属优惠券)。
uiju_{ij} 与 ui0u_{i0} MNL 偏好权重 类型 ii 消费者对商品 jj 的偏好权重 uij≥0u_{ij}\ \geq \ 0,以及对“不购买(外部选项)”的偏好权重 ui0>0u_{i0}\ > \ 0。
𝐱i=(xi1,…,xin)∈{0,1}n\mathbf{x}_{i}\ = \ \left( x_{i1},\ \ldots,\ x_{in} \right)\ \in \ \left\{ 0,\ 1 \right\}^{n} 品类决策二元向量 xij=1x_{ij}\ = \ 1 表示向第 ii 类客群提供/展示商品 jj,xij=0x_{ij}\ = \ 0 表示不提供;𝐱0\mathbf{x}_{0} 为线下门店备货品类,𝐱i\mathbf{x}_{i}(i∈Mi\ \in \ M)为线上个性化品类。
ℱi⊆{0,1}n\mathcal{F}_{i}\ \subseteq \ \left\{ 0,\ 1 \right\}^{n} 可行品类约束集合 第 ii 类渠道/客群需满足的运营规则(如货架容量限制、分类覆盖约束、全单模约束或两阶段非支配集)。

3.2 核心函数与优化模型深度解释

(1)多项式 Logit(MNL)期望收益函数 RiMNL(𝐱i)R_{i}^{\text{MNL}}\left( \mathbf{x}_{i} \right)

当企业向第 i∈M+i\ \in \ M^{+} 类消费者提供商品子集(由二元向量 𝐱i\mathbf{x}_{i} 表示)时,根据随机效用最大化理论下的 MNL 模型,该类消费者购买商品 j∈Nj\ \in \ N 的选择概率为 uijxijui0+∑j∈Nuijxij\frac{u_{ij}x_{ij}}{u_{i0}\ + \ \sum_{j \in N}^{}{u_{ij}x_{ij}}},选择不购买(离开系统)的概率为 ui0u_{i0} 除以同一分母。由此,从单个第 ii 类消费者身上获得的期望收益函数定义为:

RiMNL(𝐱i):=∑j∈Nrijuijxijui0+∑j∈Nuijxij.R_{i}^{\text{MNL}}\left( \mathbf{x}_{i} \right)\ : = \ \frac{\sum_{j \in N}^{}{r_{ij}u_{ij}x_{ij}}}{u_{i0}\ + \ \sum_{j \in N}^{}{u_{ij}x_{ij}}}.

函数结构解释:该函数是一个典型的0-1线性分式函数(Linear fractional function)。分子是所有被提供商品(xij=1x_{ij}\ = \ 1)的“单位收益乘以偏好权重(rijr_{ij}uiju_{ij})”之和;分母是“不购买偏好权重 ui0u_{i0}”与所有上架商品偏好权重之和(即总吸引力)。这体现了零售品类管理的核心权衡(蚕食效应 Cannibalization Effect):增加一个新商品(将某个 xijx_{ij} 从0变为1)虽然会增加分子并提高总购买转化率,但同时也会增大分母,从而稀释已在架高毛利商品被选中的概率。如果新加入商品的价格 rijr_{ij} 低于当前品类的期望收益水平,反而会拉低整体期望收益 RiMNL(𝐱i)R_{i}^{\text{MNL}}\left( \mathbf{x}_{i} \right)。

(2)即时零售全渠道联合品类优化模型(QAP)

零售商的目标是联合决定线下实体门店备货品类 𝐱0\mathbf{x}_{0} 与各个线上细分客群的个性化展示品类 𝐱i\mathbf{x}_{i}(i∈Mi\ \in \ M),最大化按客群到达概率 αi\alpha_{i} 加权的全系统期望总收益:

max∑i∈M+αiRiMNL(𝐱i)s.t. 𝐱0≥𝐱i for i∈M, 𝐱i∈ℱi⊆{0,1}n for i∈M+. (QAP)\begin{array}{r} max\ \ \ \sum_{i \in M^{+}}^{}{\alpha_{i}R_{i}^{\text{MNL}}\left( \mathbf{x}_{i} \right)} \\ \text{s.t. }\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i}\text{ for }i\ \in \ M, \\ \text{ }\mathbf{x}_{i}\ \in \ \mathcal{F}_{i}\ \subseteq \ \left\{ 0,\ 1 \right\}^{n}\text{ for }i\ \in \ M^{+}. \end{array}\text{ (QAP)}

函数与约束解释:目标函数是 mm 个线上客群与1个线下客群的期望收益加权和。第一组约束 𝐱0≥𝐱i\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i}(即对任意商品 jj 有 xijx_{ij} 不超过线下备货变量)刻画了即时零售的核心物理联动要求(Physical linkage constraint):只有当某件商品实际存放在线下实体店(𝐱0\mathbf{x}_{0} 对应分量为1)时,店员才能在30分钟内拣货配送,因此线上推荐给任何客群的品类都必须是线下门店品类的子集;但反过来,线下门店备货的某件低价引流品可以选择只展示给部分价格敏感的线上客群,而对高支付意愿的线上客群隐藏(即允许严格不等号成立),从而通过线上个性化屏蔽蚕食效应。第二组约束 ℱi⊆{0,1}n\mathcal{F}_{i}\ \subseteq \ \left\{ 0,\ 1 \right\}^{n} 刻画各渠道的业务规则:模型仅要求线下可行域 ℱ0\mathcal{F}_{0} 为任意二元多面体集(可表達货架空间、预算、供应商协议等任意复杂线性整数约束),而要求线上可行域 ℱi\mathcal{F}_{i} 能够构造紧凸包 conv(ℱi)\text{conv}\left( \mathcal{F}_{i} \right)。

(3)两阶段 Luce 模型(2SLM)的非支配商品筛选函数 ci(S)c_{i}(S) 与(UNDOMINATED)集合

在真实电商场景中(如淘宝数据集仅1.25%的非零交互),许多消费者在同一品类中存在严格偏好支配关系:例如某消费者绝对偏爱可口可乐胜过百事可乐,只要货架上有可口可乐,其购买百事可乐的概率严格为0;只有当可口可乐缺货时,他才会以正概率购买百事可乐。标准 MNL 模型要求所有在架商品选择概率均大于0,无法刻画这种“零概率支配现象”。为此,文章引入 Echenique and Saito (2019) 的两阶段 Luce 模型(2SLM):设偏序集 𝒫i\mathcal{P}_{i} 上的严格偏序关系 a1≺ia2a_{1}\ \prec_{i}\ a_{2} 表示对第 ii 类客群而言商品 a1≺ia2a_{1}\ \prec_{i}\ a_{2}(即 a2a_{2} 严格支配/优于 a1a_{1})。给定展示商品集 S⊆NS\ \subseteq \ N,消费者在第一阶段会自动剔除所有被支配的商品,仅保留非支配商品子集(Undominated products) ci(S)c_{i}(S):

ci(S):={j∈S|∄k∈S s.t. j≺ik}.c_{i}(S)\ : = \ \left\{ j\ \in \ S\ |\ \nexists k\ \in \ S\text{ s.t. }j\ \prec_{i}\ k \right\}.

随后在第二阶段,消费者仅在剩余的非支配商品集 ci(S)c_{i}(S) 上按照标准 MNL 模型做出购买选择。从优化建模角度看,企业向第 ii 类线上客群提供任意品类并经第一阶段自我筛选后,等价于直接在该偏序集的所有反链(Antichains,即不存在任意两件商品互相支配的子集)构成的二元可行域(UNDOMINATED)上最大化 RiMNL(𝐱i)R_{i}^{\text{MNL}}\left( \mathbf{x}_{i} \right):

{𝐱i∈{0,1}n|0≤xia1+⋯+xiak≤1for chains a1≺i⋯≺iak in 𝒫i}. (UNDOMINATED)\left\{ \mathbf{x}_{i}\ \in \ \left\{ 0,\ 1 \right\}^{n}\ |\ 0\ \leq \ x_{ia_{1}}\ + \ \cdots\ + \ x_{ia_{k}}\ \leq \ 1\ \ \text{for chains }a_{1}\ \prec_{i}\ \cdots\ \prec_{i}\ a_{k}\text{ in }\mathcal{P}_{i} \right\}.\text{ (UNDOMINATED)}

集合与函数解释:在偏序集 𝒫i\mathcal{P}_{i} 中,任意一条全序链 a1≺i⋯≺iaka_{1}\ \prec_{i}\ \cdots\ \prec_{i}\ a_{k} 代表一串存在严格优劣递进关系的商品(如同一品牌的低配、中配、高配型号)。约束要求在同一条支配链上至多只能有1个商品在第二阶段被激活参与 MNL 竞争,这完美等价于消费者在第一阶段剔除所有劣势商品的筛选机制。

(4)两步收益排序启发式策略函数(2-STEP-RO)

在无运营约束(ℱi\mathcal{F}_{i} 为全集)时,业界最直观的基准做法是分两步先后决策(2-STEP-RO):第一步仅根据线下客群的收益最大化确定门店备货品类;第二步在门店已备货商品中分别为各线上客群挑选最优子集:

𝐱0RO∈arg max{R0MNL(𝐱0)|𝐱0∈{0,1}n},𝐱iRO∈arg max{RiMNL(𝐱i)|𝐱i∈{0,1}n,𝐱0RO≥𝐱i} for i∈M. (2-STEP-RO)\begin{array}{r} \mathbf{x}_{0}^{\text{RO}}\ \in \ \text{arg max}\left\{ R_{0}^{\text{MNL}}\left( \mathbf{x}_{0} \right)\ |\ \mathbf{x}_{0}\ \in \ \left\{ 0,\ 1 \right\}^{n} \right\}, \\ \mathbf{x}_{i}^{\text{RO}}\ \in \ \text{arg max}\left\{ R_{i}^{\text{MNL}}\left( \mathbf{x}_{i} \right)\ |\ \mathbf{x}_{i}\ \in \ \left\{ 0,\ 1 \right\}^{n},\ \mathbf{x}_{0}^{\text{RO}}\ \geq \ \mathbf{x}_{i} \right\}\text{ for }i\ \in \ M. \end{array}\text{ (2-STEP-RO)}

函数解释:根据经典 MNL 理论(Talluri and Van Ryzin 2004),单客群无约束最优品类必然遵循按价格从高到低截断的“收益排序(Revenue-Ordered, RO)”结构。然而,(2-STEP-RO)在第一步确定 𝐱0\mathbf{x}_{0} 时完全无视了线上客群的需求偏好,若线下客群只偏爱高价品而线上某主力客群偏爱中低价品,第一步就会把中低价品拒之门外,导致第二步线上客群“无货可推”。

(5)Charnes-Cooper(CC)变换映射 Πi\Pi_{i} 与选择概率集 Πi(ℱi)\Pi_{i}\left( \mathcal{F}_{i} \right)

为了消除分式目标函数 RiMNL(𝐱i)R_{i}^{\text{MNL}}\left( \mathbf{x}_{i} \right) 的非线性分母,文章引入 Charnes-Cooper 变换 Πi\Pi_{i},将二元品类向量 𝐱i\mathbf{x}_{i} 一一映射为连续的选择概率变量向量 (yi0,𝐲i)\left( y_{i0},\ \mathbf{y}_{i} \right):

yi0=1ui0+∑j∈Nuijxij and yij=xijui0+∑j∈Nuijxij for j∈N.y_{i0}\ = \ \frac{1}{u_{i0}\ + \ \sum_{j \in N}^{}{u_{ij}x_{ij}}}\text{ and }y_{ij}\ = \ \frac{x_{ij}}{u_{i0}\ + \ \sum_{j \in N}^{}{u_{ij}x_{ij}}}\text{ for }j\ \in \ N.

在该变换下,可行品类集 ℱi\mathcal{F}_{i} 的像集被称为选择概率集(Choice probability set) Πi(ℱi)\Pi_{i}\left( \mathcal{F}_{i} \right):

Πi(ℱi):={(yi0,𝐲i)|ui0yi0+∑j∈Nuijyij=1,𝐲i∈yi0⋅ℱi,yi0>0}.\Pi_{i}\left( \mathcal{F}_{i} \right)\ : = \ \left\{ \left( y_{i0},\ \mathbf{y}_{i} \right)\ |\ u_{i0}y_{i0}\ + \ \sum_{j \in N}^{}{u_{ij}y_{ij}}\ = \ 1,\ \ \mathbf{y}_{i}\ \in \ y_{i0}\ \cdot \ \mathcal{F}_{i},\ \ y_{i0}\ > \ 0 \right\}.

变换与概率含义解释:这里 yi0y_{i0} 代表总效用分母的倒数(即基准单位效用对应的概率尺度),乘积 ui0yi0u_{i0}y_{i0} 恰好是第 ii 类消费者选择外部不购买选项的概率,而乘积 uijyiju_{ij}y_{ij} 恰好是该消费者购买商品 jj 的概率。若商品 jj 上架(xij=1x_{ij}\ = \ 1),则 yijy_{ij} 等于 yi0y_{i0};若商品 jj 不上架(xij=0x_{ij}\ = \ 0),则 yijy_{ij} 等于 0。通过这一变换,原本非线性的分式期望收益直接变成了关于 yijy_{ij} 的纯线性函数!

(6)消元重构模型与精确凸松弛模型(QAP-RLX)

利用关系式 𝐱i\mathbf{x}_{i} 等于 yi0y_{i0} 分之 (yi0,𝐲i)\left( y_{i0},\ \mathbf{y}_{i} \right),可以将所有线上二元变量 𝐱i\mathbf{x}_{i}(i∈Mi\ \in \ M)从模型中投影消去,并将线上选择概率集合 Πi(ℱi)\Pi_{i}\left( \mathcal{F}_{i} \right) 松弛为其凸包 conv(Πi(ℱi))\text{conv}\left( \Pi_{i}\left( \mathcal{F}_{i} \right) \right),得到核心松弛模型(QAP-RLX):

max∑i∈M+αi(∑j∈Nrijuijyij)s.t. (yi0,𝐲i)∈conv(Πi(ℱi)) for i∈M (凸化 CHOICE) 𝐲0=y00𝐱0 and (y00,𝐲0)∈Π0(ℱ0) (OFF-BI) 𝐲i≤yi0𝐱0 for i∈M (LINK-BI). (QAP-RLX)\begin{array}{r} max\ \ \ \sum_{i \in M^{+}}^{}{\alpha_{i}\left( \sum_{j \in N}^{}{r_{ij}u_{ij}y_{ij}} \right)} \\ \text{s.t. }\left( y_{i0},\ \mathbf{y}_{i} \right)\ \in \ \text{conv}\left( \Pi_{i}\left( \mathcal{F}_{i} \right) \right)\text{ for }i\ \in \ M\text{ (凸化 CHOICE)} \\ \text{ }\mathbf{y}_{0}\ = \ y_{00}\mathbf{x}_{0}\text{ and }\left( y_{00},\ \mathbf{y}_{0} \right)\ \in \ \Pi_{0}\left( \mathcal{F}_{0} \right)\text{ (OFF-BI)} \\ \text{ }\mathbf{y}_{i}\ \leq \ y_{i0}\mathbf{x}_{0}\text{ for }i\ \in \ M\text{ (LINK-BI).} \end{array}\text{ (QAP-RLX)}

三类核心约束函数的物理意义:① (CHOICE)及其凸化刻画每个线上客群的选择概率分布在满足运营约束下的可行空间;② (OFF-BI)线下双线性等式约束表明线下消费者直接面对门店物理货架,凡是门店备货的商品(𝐱0\mathbf{x}_{0} 分量为1),线下顾客都能看到并按 MNL 概率购买(因此 y0jy_{0j} 严格等于 y00y_{00} 乘以 𝐱0\mathbf{x}_{0} 对应分量);③ (LINK-BI)跨渠道双线性联动不等式将原物理联动约束 𝐱0≥𝐱i\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i} 同乘正数 yi0y_{i0} 转化而来,表示若某商品未在线下门店备货(𝐱0\mathbf{x}_{0} 分量为0),则任何线上客群选中该商品的概率 yijy_{ij} 必须被强制压制为0;若线下已备货(分量为1),则线上可自由决定是否推荐(yijy_{ij} 可在 0 到 yi0y_{i0} 之间取值)。

(7)概率归一化超平面 HH 与 IIA-品类锥 KK

在研究单个客群的选择概率集 Π(ℱ)\Pi(\mathcal{F})(省略客群下标 ii)时,文章将其分解为超平面 HH 与锥 KK 的交集:

H:={(y0,𝐲)|u0y0+∑j∈Nujyj=1} and K:={(y0,𝐲)|𝐲∈y0⋅ℱ,y0>0}.H\ : = \ \left\{ \left( y_{0},\ \mathbf{y} \right)\ |\ u_{0}y_{0}\ + \ \sum_{j \in N}^{}{u_{j}y_{j}}\ = \ 1 \right\}\text{ and }K\ : = \ \left\{ \left( y_{0},\ \mathbf{y} \right)\ |\ \mathbf{y}\ \in \ y_{0}\ \cdot \ \mathcal{F},\ \ y_{0}\ > \ 0 \right\}.

几何与公理含义解释:这两个几何对象精确对应 Luce (1959) 选择公理体系的两大基石!超平面 HH 称为概率归一化超平面(Probability normalization hyperplane),强制所有备选商品被选中的概率与不购买概率之和等于1;射线集合 KK 称为IIA-品类锥(IIA-assortment cone),其中每一条射线对应一个可行品类组合,且锥上任意一点自动满足无关备选项独立性公理(Independence of Irrelevant Alternatives, IIA)——即任意两个同在货架上的商品 aa 和 bb,其购买概率之比恒等于偏好权重之比:

uayaubyb=uay0uby0=uaub.\frac{u_{a}y_{a}}{u_{b}y_{b}}\ = \ \frac{u_{a}y_{0}}{u_{b}y_{0}}\ = \ \frac{u_{a}}{u_{b}}.

(8)聚合效用函数 U(S)U(S)、基准比例函数 α(S)\alpha(S) 与分离优化目标(SEP-UNDER / SEP-OVER)

为刻画单商品双线性集 ℬj\mathcal{B}_{j} 的凸包,对任意商品子集 S⊆NS\ \subseteq \ N,定义子集总偏好权重函数 U(S)U(S) 及其倒数基准不购买比例函数 α(S)\alpha(S):

U(S):=u0+∑i∈Sui and α(S):=1U(S) for every S⊆N.U(S)\ : = \ u_{0}\ + \ \sum_{i \in S}^{}u_{i}\text{ and }\alpha(S)\ : = \ \frac{1}{U(S)}\text{ for every }S\ \subseteq \ N.

当给定一个待检验的松弛分数解点时,为了从指数级数量的(UNDER)和(OVER)不等式中找出违背最严重的割平面,文章构造了如下两个组合分离优化问题(SEP-UNDER)与(SEP-OVER):

maxS⊆N∖{j}{xj¯U(S∪{j})−∑t∉(S∪j)ut⋅yt¯U(S∪{j})} (SEP-UNDER)minS⊆N∖{j}{xj¯U(S∪{j})+∑t∈Sut⋅(y0¯−yt¯)U(S∪{j})} (SEP-OVER)\begin{array}{r} \max_{S \subseteq N\backslash\left\{ j \right\}}\left\{ \frac{\overline{x_{j}}}{U\left( S\ \cup \ \left\{ j \right\} \right)}\ - \ \frac{\sum_{t \notin (S \cup j)}^{}{u_{t}\ \cdot \ \overline{y_{t}}}}{U\left( S\ \cup \ \left\{ j \right\} \right)} \right\}\text{ (SEP-UNDER)} \\ \min_{S \subseteq N\backslash\left\{ j \right\}}\left\{ \frac{\overline{x_{j}}}{U\left( S\ \cup \ \left\{ j \right\} \right)}\ + \ \frac{\sum_{t \in S}^{}{u_{t}\ \cdot \ \left( \overline{y_{0}}\ - \ \overline{y_{t}} \right)}}{U\left( S\ \cup \ \left\{ j \right\} \right)} \right\}\text{ (SEP-OVER)} \end{array}

分离函数的直观经济解释:可以把 SS 并上商品 jj 想象成零售商提供给消费者的一个“假想参考品类(Imaginary assortment)”。如果真实提供的品类恰好就是这个假想品类,那么商品 jj 的选择概率尺度 yjy_{j} 应当恰好等于第一项 α(S∪{j})\alpha\left( S\ \cup \ \left\{ j \right\} \right) 乘以 xjx_{j}。但在分数松弛解中,实际选择概率可能偏离假想品类:① 在(SEP-UNDER)中,如果消费者选择了假想品类之外的商品(即对假想品类外的 tt 有正的购买概率),则会分流消费需求,因此必须按偏好权重将 yjy_{j} 的理论下界向下修正(减去第二项),最大化该式旨在寻找最紧的下界;② 在(SEP-OVER)中,如果假想品类内部的某些商品 tt 被选中的程度低于预期(即其概率尺度小于基准 y0y_{0}),说明内部竞争减弱,因此需要将 yjy_{j} 的理论上界向上修正(加上第二项),最小化该式旨在寻找最紧的上界。

(9)独立需求模型期望收益函数 RiIDM(𝐱i)R_{i}^{\text{IDM}}\left( \mathbf{x}_{i} \right) 与混合需求目标函数(MIXTURE)

在第 7.2 节中,考虑到线上点击访问成本极低、不购买率往往很高,消费者对不同商品的购买决策可视为互不干扰(无替代效应),即遵循独立需求模型(Independent Demand Model, IDM)。设第 i∈Mi\ \in \ M 类线上消费者独立购买商品 jj 的概率为 θij>0\theta_{ij}\ > \ 0,则提供品类 𝐱i\mathbf{x}_{i} 时的线上期望收益函数 RiIDM(𝐱i)R_{i}^{\text{IDM}}\left( \mathbf{x}_{i} \right) 以及单渠道混合 MNL 与 IDM 模型(MIXTURE, Cao et al. 2023)的目标函数分别为:

RiIDM(𝐱i):=∑j∈Nrijθijxij,max{∑i∈Nri(αvixiv0+∑l∈Nvlxl+(1−α)θixi)|𝐱∈ℱ⊆{0,1}n} (MIXTURE).\begin{array}{r} R_{i}^{\text{IDM}}\left( \mathbf{x}_{i} \right)\ : = \ \sum_{j \in N}^{}{r_{ij}\theta_{ij}x_{ij}}, \\ max\ \left\{ \sum_{i \in N}^{}{r_{i}\left( \alpha\frac{v_{i}x_{i}}{v_{0}\ + \ \sum_{l \in N}^{}{v_{l}x_{l}}}\ + \ (1\ - \ \alpha)\theta_{i}x_{i} \right)}\ |\ \mathbf{x}\ \in \ \mathcal{F}\ \subseteq \ \left\{ 0,\ 1 \right\}^{n} \right\}\text{ (MIXTURE).} \end{array}

函数解释:RiIDM(𝐱i)R_{i}^{\text{IDM}}\left( \mathbf{x}_{i} \right) 是关于二元决策变量 xijx_{ij} 的纯线性可加函数,每多上架一件非负毛利商品都会单调增加线上收益;而线下门店依然遵循具有替代蚕食效应的分式函数 R0MNL(𝐱0)R_{0}^{\text{MNL}}\left( \mathbf{x}_{0} \right)。两者的结合精确捕捉了“线下货架存在强替代竞争、线上精准流量近似独立购买”的跨渠道行为差异。

四、 全文命题、引理、定理与推论详解(结合具体算例,略去证明)

本节对论文中出现的全部 3 个命题(Propositions)、2 个引理(Lemmas)、6 个定理(Theorem 1–6)与 4 个推论(Corollary 1–4)进行逐一解析。遵照要求,我们略去繁琐的数学证明推导过程,重点阐述每个结论的数学本质,并全部配以直观的数值算例或业务场景实例来透彻说明其内在含义。

4.1 命题 1(Proposition 1):即时零售品类规划问题的 NP-hard 复杂性

【命题 1 原文核心表述】 即使在线上仅有 1 类消费者(mm = 1)、线下与线上均无任何运营约束(可行域均为全集)、且线上与线下各商品的销售价格完全相同(𝐫0=𝐫1\mathbf{r}_{0}\ = \ \mathbf{r}_{1})的最简情形下,最大化即时零售品类规划问题(QAP)依然是 NP-hard 问题。

【核心含义解析】 在经典单渠道无约束 MNL 模型中,人们只需将商品按价格从高到低排序,依次测试至多 nn 个“收益排序(Revenue-Ordered)”集合即可在多项式时间内找到最优解。然而在即时零售(QAP)中,由于存在物理联动约束 𝐱0≥𝐱i\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i},线下门店备货一件低价商品虽然会蚕食线下高价品的销售,但却能在线上渠道产生可观的增量收益。这种“线下受损、线上受益”的跨渠道权衡打破了线下品类的单调收益排序结构,使得枚举候选集的数量呈指数级爆炸。

【命题 1 直观数值算例:为什么简单的收益排序在 QAP 中失效并导致组合爆炸?】

算例设定:假设某生鲜门店有 3 种商品:商品 1(精品和牛,价格 10 元)、商品 2(有机牛排,价格 9 元)、商品 3(特价鸡蛋,价格 8 元)。线下客群(类型 0,占比 50%)极度偏爱商品 1 和 3,偏好权重为 (u01,u02,u03)=(10,1,10)(u_{01},\ u_{02},\ u_{03})\ = \ (10,\ 1,\ 10),不购买权重 u00=1u_{00}\ = \ 1;线上客群(类型 1,占比 50%)偏爱商品 2 和 3,偏好权重为 (u11,u12,u13)=(1,10,20)(u_{11},\ u_{12},\ u_{13})\ = \ (1,\ 10,\ 20),不购买权重 u10=1u_{10}\ = \ 1。

算例演算:若只看线下渠道,按价格从高到低排序的候选集只有 {1}、{1, 2}、{1, 2, 3}。在集合 {1} 下线下期望收益为 10×10/(1+10) = 9.09 元;若按价格顺序加入商品 2 变成 {1, 2},线下收益降至 (100+9)/12 = 9.08 元;但如果我们跳过价格为 9 元的商品 2,直接在门店备货 {1, 3}(违反了线下价格排序!),此时线下期望收益为 (100+80)/21 = 8.57 元,但线上可以向客群 1 推荐 {3}(甚至 {1, 3}),获得高达 (10×1+8×20)/(1+1+20) = 7.73 元的收益!

核心启示:当存在几十上百种中低价引流商品时,为了决定究竟应该把哪几个低价商品放进线下门店以支援线上客群,零售商面临类似于“0-1 背包/集合划分”的组合权衡,无法通过按价格排序求解,这就是 Proposition 1 揭示的 NP-hard 本质。

4.2 命题 2(Proposition 2):全局最优解对两步启发式解的包含关系与福利双赢

【命题 2 原文核心表述】 假设所有商品在不同消费者类型之间的价格高低次序是一致的(即对任意 i∈M+i\ \in \ M^{+} 均满足 ri1≥ri2≥⋯≥rinr_{i1}\ \geq \ r_{i2}\ \geq \ \cdots\ \geq \ r_{in})。设 𝐱RO\mathbf{x}^{\text{RO}} 为两步收益排序策略(2-STEP-RO)给出的解,𝐱QAP\mathbf{x}^{\text{QAP}} 为(QAP)全局最优解(若存在多重最优解,取激活商品数最多的最优解),则恒有包含关系:

𝐱RO≤𝐱QAP (即对所有 i∈M+ 和 j∈N,均有 xijRO≤xijQAP).\mathbf{x}^{\text{RO}}\ \leq \ \mathbf{x}^{\text{QAP}}\text{ (即对所有 }i\ \in \ M^{+}\text{ 和 }j\ \in \ N\text{,均有 }x_{ij}^{\text{RO}}\ \leq \ x_{ij}^{\text{QAP}}\text{).}

【核心含义解析】 该命题表明:相比于先顾线下、再顾线上的分步决策(2-STEP-RO),全渠道联合优化(QAP)不仅能带来更高的总期望收益,而且在线下门店和每一个线上细分渠道中提供的商品种类都只会增加、绝不会减少。根据 MNL 模型的消费者剩余理论(总效用越大,消费者满意度越高),这意味着联合优化能够实现企业总收益与全体消费者满意度的帕累托双赢(Simultaneous increase in revenue and consumer satisfaction)。

【命题 2 直观数值算例(对应原文 Example 1 & Table 1)】

算例设定:考虑 3 种商品,各客群下商品收益均为 (ri1,ri2,ri3)=(10,9,8)\left( r_{i1},\ r_{i2},\ r_{i3} \right)\ = \ (10,\ 9,\ 8)(满足价格排序一致)。三类客群(线下客群 0、线上普通客群 1、线上高价值客群 2)的到达率分别为 𝛂=(0.4,0.4,0.2)\mathbf{\alpha}\ = \ (0.4,\ 0.4,\ 0.2),不购买权重均为 ui0=1u_{i0}\ = \ 1。各客群偏好权重分别为:线下客群 0 为 (100, 100, 1);线上客群 1 为 (1, 1, 100)(极度偏爱 8 元的实惠商品 3);线上客群 2 为 (100, 1, 1)(只偏爱 10 元的精品商品 1)。

分步策略(2-STEP-RO)结果:第一步只算线下客群 0:提供 {1} 时收益为 10×100/101 = 9.90 元;提供 {1, 2} 时收益降至 (1000+900)/201 = 9.45 元,故线下只备货 x0RO={1x_{0}^{\text{RO}}\ = \ \{ 1}。第二步线上只能从 {1} 中选:线上客群 1 被迫只能看到不喜欢的商品 {1},其购买概率仅为 1/(1+1)=50%,期望收益暴跌至 5.00 元;线上客群 2 看到 {1},期望收益 9.90 元。全渠道总期望收益 = 0.4×9.90 + 0.4×5.00 + 0.2×9.90 = 7.94 元。

全局联合优化(QAP)结果:线下门店主动扩充备货至 x0QAP={1,3x_{0}^{\text{QAP}}\ = \ \{ 1,\ 3}!此时线下客群 0 期望收益仅微降 0.02 元(变为 (1000+8)/102 = 9.88 元);但线上客群 1 可以获得推荐 x1QAP={1,3x_{1}^{\text{QAP}}\ = \ \{ 1,\ 3},其期望收益从 5.00 元飙升至 (10×1+8×100)/102 = 7.94 元;同时利用个性化能力,对线上客群 2 隐藏商品 3,仅展示 x2QAP={1x_{2}^{\text{QAP}}\ = \ \{ 1},保持 9.90 元的高收益!全渠道总收益跃升至 0.4×9.88 + 0.4×7.94 + 0.2×9.90 = 9.11 元(提升达 14.7%)。

对比验证:对比两者的品类集合:线下 {1}⊂{1,3\{ 1\}\ \subset \ \{ 1,\ 3},线上客群 1 的 {1}⊂{1,3\{ 1\}\ \subset \ \{ 1,\ 3},线上客群 2 的 {1}⊆{1\{ 1\}\ \subseteq \ \{ 1},完美验证了 𝐱RO≤𝐱QAP\mathbf{x}^{\text{RO}}\ \leq \ \mathbf{x}^{\text{QAP}}!所有渠道的消费者都拥有了更多或至少相同的选择,无人受损而整体大获全胜。

4.3 引理 1(Lemma 1)与定理 1(Theorem 1):线上选择概率集的精确凸松弛

【引理 1 原文核心表述】 设集合 SS 是欧氏空间中的子集,超平面 HH 定义为满足线性等式 αi\alpha_{i} 内积等于常数 kk 的点集,且集合 SS 中的所有点均位于该超平面的一侧(即满足小于等于不等式)。则先取凸包再与超平面求交,完全等价于先与超平面求交再取凸包:

conv(S)∩H=conv(S∩H).\text{conv}(S)\ \cap \ H\ = \ \text{conv}(S\ \cap \ H).

【定理 1 原文核心表述】 原即时零售品类规划问题(QAP)与将其所有线上客群的选择概率集 Πi(ℱi)\Pi_{i}\left( \mathcal{F}_{i} \right) 松弛为凸包 conv(Πi(ℱi))\text{conv}\left( \Pi_{i}\left( \mathcal{F}_{i} \right) \right) 后的问题(QAP-RLX)具有完全相同的全局最优目标值。

【引理 1 与定理 1 直观几何与数值算例(对应原文 Figure 1)】

1. 引理 1 的几何直观算例:设二维平面上有 3 个离散整数点构成的集合 S={(0,0),(1,0),(1,1)S\ = \ \{(0,\ 0),\ (1,\ 0),\ (1,\ 1)},其凸包 conv(S)\text{conv}(S) 是以这三点为顶点的实心三角形。情况 A(超平面定义 S 的一个支撑面/边界):考虑水平直线 H1:x1=1H_{1}\ :\ x_{1}\ = \ 1(由于 S 中所有点都满足 x1≤1x_{1}\ \leq \ 1,故 H1H_{1} 是有效支撑超平面)。此时 S∩H1={(1,0),(1,1)S\ \cap \ H_{1}\ = \ \{(1,\ 0),\ (1,\ 1)},其凸包是连接 (1, 0) 与 (1, 1) 的竖直线段;而先取三角形 conv(S)\text{conv}(S) 再与直线 H1H_{1} 相交,得到的也是同一条线段,即 conv(S)∩H1=conv(S∩H1)\text{conv}(S)\ \cap \ H_{1}\ = \ \text{conv}(S\ \cap \ H_{1})。情况 B(反例:超平面穿过内部而非支撑面):若取直线 H2:x1=0.5H_{2}\ :\ x_{1}\ = \ 0.5(穿过 S 内部),则 S∩H2=⌀S\ \cap \ H_{2}\ = \ \varnothing(空集),conv(S∩H2)=⌀\text{conv}(S\ \cap \ H_{2})\ = \ \varnothing,但 conv(S)∩H2\text{conv}(S)\ \cap \ H_{2} 却是一条长度为 0.5 的线段,两者完全不等!

2. 定理 1 的业务算例解释:为什么在(QAP-RLX)中把线上客群的 0-1 离散决策松弛成连续凸组合(例如“50% 概率推品类 A + 50% 概率推品类 B”)不会产生虚高的分数最优解?假设线下门店最终确定的备货为 x0=(1,0)x_{0}\ = \ (1,\ 0)(只备货商品 1,不备货商品 2)。此时跨渠道联动约束(LINK-BI)要求线上商品 2 的选择概率满足 yi2≤yi0⋅x02=0y_{i2}\ \leq \ y_{i0}\ \cdot \ x_{02}\ = \ 0。因为选择概率天然非负(yi2≥0y_{i2}\ \geq \ 0),所以超平面 yi2=0y_{i2}\ = \ 0 恰好构成了线上选择概率集的一个边界支撑面(满足引理 1 的条件)!根据引理 1,在这个支撑面上,凸包上的任何极点都必然是原本满足 yi2=0y_{i2}\ = \ 0 的真实离散品类点。换言之,只要线下门店备货 𝐱0\mathbf{x}_{0} 是 0-1 整数,每个线上客群在线性目标函数最大化下,都会自动收敛到某个满足 𝐱0≥𝐱i\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i} 的纯 0-1 整点个性化品类,绝不会停留在无法落地的分数混合品类上!

4.4 引理 2(Lemma 2)与定理 2(Theorem 2):超平面-锥分解与紧致多面体扩展表述

【引理 2 原文核心表述】 对于任意可行品类子集 ℱ\mathcal{F},其选择概率集 Π(ℱ)\Pi(\mathcal{F}) 的凸包等于概率归一化超平面 HH 与 IIA-品类锥 KK 凸包的交集,且锥的凸包直接由 conv(ℱ)\text{conv}(\mathcal{F}) 生成:

conv(Π(ℱ))=H∩conv(K) and conv(K)={(y0,𝐲)|𝐲∈y0⋅conv(ℱ),y0>0}.\text{conv}\left( \Pi(\mathcal{F}) \right)\ = \ H\ \cap \ \text{conv}(K)\text{ and }\text{conv}(K)\ = \ \left\{ \left( y_{0},\ \mathbf{y} \right)\ |\ \mathbf{y}\ \in \ y_{0}\ \cdot \ \text{conv}(\mathcal{F}),\ \ y_{0}\ > \ 0 \right\}.

【定理 2 原文核心表述】 设线性不等式系统 AA 乘以 𝐱0\mathbf{x}_{0} 加 BB 乘以 𝐳i∈ℝn\mathbf{z}_{i}\ \in \ {\mathbb{R}}^{n} 小于等于 bb 是可行品类凸包 conv(ℱ)\text{conv}(\mathcal{F}) 的一个扩展表述(Extended formulation):

若 conv(ℱ)={𝐱|∃𝐳 s.t. 𝐀𝐱+𝐁𝐳≤𝐛},则 conv(Π(ℱ)) 的扩展表述为:{(y0,𝐲,𝐳)|𝐀𝐲+𝐁𝐳≤𝐛y0,(y0,𝐲)∈H,y0≥0}.\text{若 }\text{conv}(\mathcal{F})\ = \ \left\{ \mathbf{x}\ |\ \exists\mathbf{z}\text{ s.t. }\mathbf{A}\mathbf{x}\ + \ \mathbf{B}\mathbf{z}\ \leq \ \mathbf{b} \right\}\text{,则 }\text{conv}\left( \Pi(\mathcal{F}) \right)\text{ 的扩展表述为:}\left\{ \left( y_{0},\ \mathbf{y},\ \mathbf{z} \right)\ |\ \mathbf{A}\mathbf{y}\ + \ \mathbf{B}\mathbf{z}\ \leq \ \mathbf{b}y_{0},\ \ \left( y_{0},\ \mathbf{y} \right)\ \in \ H,\ \ y_{0}\ \geq \ 0 \right\}.

此外,若 conv(ℱ)\text{conv}(\mathcal{F}) 具有多项式规模的紧致扩展表述(Compact extended formulation),则 conv(Π(ℱ))\text{conv}\left( \Pi(\mathcal{F}) \right) 也必然具有紧致扩展表述。

【引理 2 与定理 2 直观算例解释(对应原文 Example 2、Figure 2 与 Remark 1)】

算例设定:考虑 n=2n\ = \ 2 种商品,偏好权重为 (u0,u1,u2)=(1,1,2)(u_{0},\ u_{1},\ u_{2})\ = \ (1,\ 1,\ 2)。此时概率归一化超平面为 H={(y0,y1,y2)|y0+y1+2y2=1H\ = \ \{(y_{0},\ y_{1},\ y_{2})\ |\ y_{0}\ + \ y_{1}\ + \ 2y_{2}\ = \ 1}。我们假设存在货架容量约束:至多只能展示 1 种商品,即 ℱ={(0,0),(1,0),(0,1)\mathcal{F}\ = \ \{(0,\ 0),\ (1,\ 0),\ (0,\ 1)}。

直接计算 Π(ℱ)\Pi(\mathcal{F}) 的极点:当 x=(0,0)x\ = \ (0,\ 0) 时,分母为 1,得概率点 P0=(1,0,0)P_{0}\ = \ (1,\ 0,\ 0);当 x=(1,0)x\ = \ (1,\ 0) 时,分母为 1+1=2,得概率点 P1=(1/2,1/2,0)P_{1}\ = \ (1/2,\ 1/2,\ 0);当 x=(0,1)x\ = \ (0,\ 1) 时,分母为 1+2=3,得概率点 P2=(1/3,0,1/3)P_{2}\ = \ (1/3,\ 0,\ 1/3)。由于不同品类的分母各不相同(1、2、3),直接对这三个点求凸包看似需要处理复杂的非线性分式变换。

应用定理 2 一键生成凸包:注意到离散集 ℱ={(0,0),(1,0),(0,1)\mathcal{F}\ = \ \{(0,\ 0),\ (1,\ 0),\ (0,\ 1)} 的凸包 conv(ℱ)\text{conv}(\mathcal{F}) 极其简单,就是线性不等式组:x1≥0,x2≥0,x1+x2≤1x_{1}\ \geq \ 0,\ x_{2}\ \geq \ 0,\ x_{1}\ + \ x_{2}\ \leq \ 1!根据定理 2,我们只需把不等式右侧的常数 1 乘以 y_0,把 x 替换为 y,再联立超平面 H,立刻得到 conv(Π(ℱ))\text{conv}\left( \Pi(\mathcal{F}) \right) 的精确线性表述:{(y0,y1,y2)|y1≥0,y2≥0,y1+y2≤y0,y0+y1+2y2=1\{(y_{0},\ y_{1},\ y_{2})\ |\ y_{1}\ \geq \ 0,\ y_{2}\ \geq \ 0,\ y_{1}\ + \ y_{2}\ \leq \ y_{0},\ y_{0}\ + \ y_{1}\ + \ 2y_{2}\ = \ 1}!读者可以验证,该多面体的三个极点恰好就是 P0(1,0,0)P_{0}(1,0,0)、P1(1/2,1/2,0)P_{1}(1/2,1/2,0) 和 P2(1/3,0,1/3)P_{2}(1/3,0,1/3)!

在两阶段 Luce 模型(2SLM)中的威力(Remark 1):当线上客群具有支配偏序关系(例如商品 1 ≺i\prec_{i} 商品 2 ≺i\prec_{i} 商品 3)时,虽然反链多面体在原空间可能有指数级约束,但借助定理 2 和链多面体的提升变量 𝐳i∈ℝn\mathbf{z}_{i}\ \in \ {\mathbb{R}}^{n},只需写出 0≤zi1≤zi2≤zi3≤yi00\ \leq \ z_{i1}\ \leq \ z_{i2}\ \leq \ z_{i3}\ \leq \ y_{i0}} 以及 yi1=zi1,yi2≤zi2−zi1,yi3≤zi3−zi2y_{i1}\ = \ z_{i1},\ y_{i2}\ \leq \ z_{i2}\ - \ z_{i1},\ y_{i3}\ \leq \ z_{i3}\ - \ z_{i2}},就能用 𝒪(n2)\mathcal{O}\left( n^{2} \right) 个线性不等式精确刻画 2SLM 的选择概率凸包!

4.5 命题 3(Proposition 3):全商品联合双线性集凸包分离问题的 NP-hard 性质

【命题 3 原文核心表述】 记无约束选择概率凸包为 Y=conv(Π({0,1}n))Y\ = \ \text{conv}\left( \Pi\left( \left\{ 0,\ 1 \right\}^{n} \right) \right)。定义全商品联合双线性等式集与不等式集分别为:

ℬ:={(𝐱,y0,𝐲)∈{0,1}n×Y|yj=y0xj for all j∈N} 及 ℬ≤:={(𝐱,y0,𝐲)∈{0,1}n×Y|yj≤y0xj for all j∈N}.\mathcal{B}\ : = \ \left\{ \left( \mathbf{x},\ y_{0},\ \mathbf{y} \right)\ \in \ \left\{ 0,\ 1 \right\}^{n}\ \times \ Y\ |\ y_{j}\ = \ y_{0}x_{j}\text{ for all }j\ \in \ N \right\}\text{ 及 }\mathcal{B}^{\leq}\ : = \ \left\{ \left( \mathbf{x},\ y_{0},\ \mathbf{y} \right)\ \in \ \left\{ 0,\ 1 \right\}^{n}\ \times \ Y\ |\ y_{j}\ \leq \ y_{0}x_{j}\text{ for all }j\ \in \ N \right\}.

则多面体凸包 conv(ℬ)\text{conv}(\mathcal{B}) 和 conv(ℬ≤)\text{conv}\left( \mathcal{B}^{\leq} \right) 的分离问题(Separation problems)均为 NP-hard。

【命题 3 直观算例与理论意义解释】

算例与直觉解释:根据组合优化著名的等价性定理(Grötschel et al. 1981),在多面体上最大化线性目标函数能够在多项式时间内求解,当且仅当该多面体的分离问题能在多项式时间内求解。假定我们能够高效地完整写出或分离出同时包含所有 n 个商品双线性约束 yj≤y0xjy_{j}\ \leq \ y_{0}\ x_{j} 的联合凸包 conv(ℬ≤)\text{conv}\left( \mathcal{B}^{\leq} \right),那么我们只需直接在这个凸包上最大化 QAP 的线性目标函数 ∑rijuijyij\sum\ r_{ij}\ u_{ij}\ y_{ij}},就能在多项式时间内求出 QAP 的精确最优解!

然而,Proposition 1 已经证明了即使只有 1 个线上客群,QAP 也是 NP-hard 问题。例如在有 100 种商品时,x1,x2,…,x100x_{1},\ x_{2},\ \ldots,\ x_{100}} 的同时取整通过分母 y0=1/(u0+∑ujxj)y_{0}\ = \ 1/(u_{0}\ + \ \sum\ u_{j}\ x_{j}) 产生了高阶全局耦合。因此,企图一次性把所有商品的二元变量 x=(x1,…,xn)x\ = \ (x_{1},\ \ldots,\ x_{n}) 与选择概率 yy 联合凸化是不可能获得易解表述的。这一结论为全文后续的研究指明了唯一正确的突围方向:放弃全商品联合双线性集 ℬ\mathcal{B},转而攻克单商品双线性集 ℬj\mathcal{B}_{j} 的精确凸包!

4.6 定理 3(Theorem 3)与推论 1(Corollary 1):单商品双线性集的有效不等式(UNDER / OVER)与强化 McCormick 包络

【定理 3 原文核心表述】 固定单个商品 j∈Nj\ \in \ N,考虑仅关联单个二元变量 xjx_{j} 与全部选择概率向量 (y0,𝐲)\left( y_{0},\ \mathbf{y} \right) 的单商品双线性集 ℬj\mathcal{B}_{j}:

ℬj:={(xj,y0,𝐲)∈{0,1}×Y|yj=y0xj}.\mathcal{B}_{j}\ : = \ \left\{ \left( x_{j},\ y_{0},\ \mathbf{y} \right)\ \in \ \left\{ 0,\ 1 \right\}\ \times \ Y\ |\ y_{j}\ = \ y_{0}x_{j} \right\}.

对于任意不包含 jj 的参考商品子集 S⊆N∖{j}S\ \subseteq \ N\ \backslash\ \left\{ j \right\},以下两组线性不等式(UNDER)与(OVER)对 ℬj\mathcal{B}_{j} 恒有效(其中 α(S∪{j})\alpha\left( S\ \cup \ \left\{ j \right\} \right) 简记为 α(S∪j)\alpha(S\ \cup \ j)):

yj≥α(S∪j)⋅xj−∑t∈N∖(S∪{j})ut⋅α(S∪j)⋅yt (UNDER)yj≤α(S∪j)⋅xj+(1−(u0+uj)⋅α(S∪j))⋅y0−∑t∈Sut⋅α(S∪j)⋅yt (OVER).\begin{array}{r} y_{j}\ \geq \ \alpha(S\ \cup \ j)\ \cdot \ x_{j}\ - \ \sum_{t \in N\backslash\left( S \cup \left\{ j \right\} \right)}^{}{u_{t}\ \cdot \ \alpha(S\ \cup \ j)\ \cdot \ y_{t}}\text{ (UNDER)} \\ y_{j}\ \leq \ \alpha(S\ \cup \ j)\ \cdot \ x_{j}\ + \ \left( 1\ - \ \left( u_{0}\ + \ u_{j} \right)\ \cdot \ \alpha(S\ \cup \ j) \right)\ \cdot \ y_{0}\ - \ \sum_{t \in S}^{}{u_{t}\ \cdot \ \alpha(S\ \cup \ j)\ \cdot \ y_{t}}\text{ (OVER).} \end{array}

【推论 1(Corollary 1)原文核心表述】 在定理 3 中,仅取两个极端参考集合 SS = ⌀\varnothing(空集)和 SS = NN \ {jj}(除 jj 外的全集),(UNDER)和(OVER)即特化为如下 4 条线性不等式(MCCORMICKPLUS),且它们严格蕴含(Tighter than)传统的 McCormick 不等式:

yj≥α(N)⋅xj,yj≥α(⌀)⋅xj+y0−α(⌀),yj≤α(j)⋅xj,yj≤α(N∖j)⋅xj+y0−α(N∖j). (MCCORMICKPLUS)\begin{array}{r} y_{j}\ \geq \ \alpha(N)\ \cdot \ x_{j},\ \ \ \ \ \ y_{j}\ \geq \ \alpha(\varnothing)\ \cdot \ x_{j}\ + \ y_{0}\ - \ \alpha(\varnothing), \\ y_{j}\ \leq \ \alpha(j)\ \cdot \ x_{j},\ \ \ \ \ \ y_{j}\ \leq \ \alpha(N\ \backslash\ j)\ \cdot \ x_{j}\ + \ y_{0}\ - \ \alpha(N\ \backslash\ j). \end{array}\text{ (MCCORMICKPLUS)}

【定理 3 与推论 1 直观数值算例(对应原文 Example 3 & Figure 3)】

算例设定:设 n=2n\ = \ 2 种商品,偏好权重为 (u0,u1,u2)=(1,1,2)(u_{0},\ u_{1},\ u_{2})\ = \ (1,\ 1,\ 2)。我们考察商品 j=1j\ = \ 1 的双线性关系 y1=y0x1y_{1}\ = \ y_{0}\ x_{1}。先计算各子集的 α(S)\alpha(S):α(⌀)=1\alpha(\varnothing)\ = \ 1;α({1})=1/2\alpha(\{ 1\})\ = \ 1/2;α({2})=1/3\alpha(\{ 2\})\ = \ 1/3;α({1,2})=1/4\alpha(\{ 1,\ 2\})\ = \ 1/4。

1. 用定理 3 写出商品 1 的全部(UNDER)与(OVER)不等式:因为 j = 1,故 S ⊆ {2} 只有两种选择:S = ∅ 或 S = {2}。① 当 S = ∅ 时,S ∪ {1} = {1},α({1}) = 1/2,集合外元素 t = 2(u_2 = 2)。代入(UNDER)得:y_1 ≥ (1/2) x_1 - 2×(1/2) y_2,即 y_1 ≥ 0.5 x_1 - y_2(整理得 2y_1 + 2y_2 - x_1 ≥ 0)!代入(OVER)得:y_1 ≤ 0.5 x_1 + (1 - 2×0.5) y_0 - 0 = 0.5 x_1。② 当 S = {2} 时,S ∪ {1} = {1, 2},α({1, 2}) = 1/4,集合外无元素。代入(UNDER)得:y_1 ≥ 0.25 x_1(即 4y_1 - x_1 ≥ 0)!代入(OVER)得:y1≤0.25x1+0.5y0−0.5y2y_{1}\ \leq \ 0.25\ x_{1}\ + \ 0.5\ y_{0}\ - \ 0.5\ y_{2}。

2. 为什么推论 1(MCCORMICKPLUS)严格强于传统 McCormick?在传统 McCormick(式 MCCORMICK)中,只知道整个集合 Y 上 y_0 的全局上下界是 y_0^L = α(N) = 1/4 和 y_0^U = α(∅) = 1,因此传统 McCormick 给出的上界是 y_1 ≤ y_0^U x_1 = 1 · x_1 以及 y_1 ≤ 0.25 x_1 + y_0 - 0.25。然而,推论 1 注意到:一旦商品 1 被提供(x_1 = 1),分母至少是 u_0 + u_1 = 2,此时 y_0 绝不可能达到 1,最大只能是 α({1}) = 1/2!同理,当商品 1 不提供(x_1 = 0)时,y_0 的最小可能值是 α(N \ {1}) = α({2}) = 1/3(而非 1/4)!因此(MCCORMICKPLUS)给出的上界是 y_1 ≤ 0.5 x_1 和 y_1 ≤ (1/3) x_1 + y_0 - 1/3,直接把传统 McCormick 的松弛上界削掉了一半!

4.7 定理 4(Theorem 4)与定理 5(Theorem 5):O(n log n) 快速分离算法与单商品凸包完全刻画

【定理 4 原文核心表述】 改进的选择概率排序算法(Algorithm 1)能够在 𝒪(n log n)\mathcal{O}\left( n\text{ log }n \right) 时间复杂度内精确求解(UNDER)和(OVER)不等式族的分离问题(即判断当前分数解是否满足全部 2n−12^{n - 1}} 条不等式,若不满足则直接输出违背最严重的那条割平面)。

【定理 5 原文核心表述】 对于任意给定的商品 j∈Nj\ \in \ N,不等式族(UNDER)完全刻画了下半双线性集 ℬj≥\mathcal{B}_{j}^{\geq} 的凸包 conv(ℬj≥)\text{conv}\left( \mathcal{B}_{j}^{\geq} \right);不等式族(OVER)完全刻画了上半双线性集 ℬj≤\mathcal{B}_{j}^{\leq} 的凸包 conv(ℬj≤)\text{conv}\left( \mathcal{B}_{j}^{\leq} \right);且(UNDER)与(OVER)合在一起,在不引入任何额外变量的情况下,完全刻画了单商品双线性集 ℬj\mathcal{B}_{j} 的凸包 conv(ℬj)\text{conv}\left( \mathcal{B}_{j} \right)。

【定理 4 与定理 5 直观算例:如何用排序法在 1 秒内从指数级不等式中抓出违背割平面?】

1. 定理 4(Algorithm 1 快速分离)算例:假设有 n=4n\ = \ 4 种商品,偏好权重为 u0=1u_{0}\ = \ 1, (u1,u2,u3,u4)=(1,2,1,2)(u_{1},\ u_{2},\ u_{3},\ u_{4})\ = \ (1,\ 2,\ 1,\ 2)。现在我们检验商品 j=1j\ = \ 1,共有 23=82^{3}\ = \ 8 个子集 S⊆{2,3,4S\ \subseteq \ \{ 2,\ 3,\ 4} 对应 16 条(UNDER/OVER)不等式。假设当前 LP 松弛解给出:x¯1=0.8{\overline{x}}_{1}\ = \ 0.8,y¯0=0.4{\overline{y}}_{0}\ = \ 0.4,且各商品选择概率变量为 (y¯1,y¯2,y¯3,y¯4)=(0.15,0.30,0.20,0.05)({\overline{y}}_{1},\ {\overline{y}}_{2},\ {\overline{y}}_{3},\ {\overline{y}}_{4})\ = \ (0.15,\ 0.30,\ 0.20,\ 0.05)。

第一步(排序):将除 j=1j\ = \ 1 外的其余商品 {2,3,4\{ 2,\ 3,\ 4} 按 y¯t{\overline{y}}_{t} 从大到小排序:因为 y¯2=0.30≥y¯3=0.20≥y¯4=0.05{\overline{y}}_{2}\ = \ 0.30\ \geq \ {\overline{y}}_{3}\ = \ 0.20\ \geq \ {\overline{y}}_{4}\ = \ 0.05,得到排列 σ=(2,3,4)\sigma\ = \ (2,\ 3,\ 4)。

第二步(构造候选集 S*S^{*} 和 T*T^{*}):对于(UNDER),挑选所有满足 y¯t≥y¯1=0.15{\overline{y}}_{t}\ \geq \ {\overline{y}}_{1}\ = \ 0.15 的商品组成 S*={2,3S^{*}\ = \ \{ 2,\ 3};对于(OVER),挑选所有满足 y¯t≥y¯0−y¯1=0.25{\overline{y}}_{t}\ \geq \ {\overline{y}}_{0}\ - \ {\overline{y}}_{1}\ = \ 0.25 的商品组成 T*={2T^{*}\ = \ \{ 2}。

第三步(代入检验):将 S*={2,3S^{*}\ = \ \{ 2,\ 3} 代入(UNDER)右侧:此时 U(S*∪{1})=u0+u1+u2+u3=5U(S^{*}\ \cup \ \{ 1\})\ = \ u_{0}\ + \ u_{1}\ + \ u_{2}\ + \ u_{3}\ = \ 5,α=0.2\alpha\ = \ 0.2,集合外仅有 t=4t\ = \ 4(u4=2,y¯4=0.05u_{4}\ = \ 2,\ {\overline{y}}_{4}\ = \ 0.05)。计算(UNDER)右侧下界为 0.2×0.8−2×0.2×0.05=0.140.2\ \times \ 0.8\ - \ 2\ \times \ 0.2\ \times \ 0.05\ = \ 0.14。由于 y¯1=0.15≥0.14{\overline{y}}_{1}\ = \ 0.15\ \geq \ 0.14,故(UNDER)未被违背!再将 T*={2T^{*}\ = \ \{ 2} 代入(OVER)右侧:U(T*∪{1})=u0+u1+u2=4U(T^{*}\ \cup \ \{ 1\})\ = \ u_{0}\ + \ u_{1}\ + \ u_{2}\ = \ 4,α=0.25\alpha\ = \ 0.25。计算(OVER)右侧上界为 0.25×0.8+0.5×0.4−2×0.25×0.30=0.250.25\ \times \ 0.8\ + \ 0.5\ \times \ 0.4\ - \ 2\ \times \ 0.25\ \times \ 0.30\ = \ 0.25。由于 y¯1=0.15≤0.25{\overline{y}}_{1}\ = \ 0.15\ \leq \ 0.25,故(OVER)也未被违背!Algorithm 1 仅靠一次排序和两次四则运算,就严格证明了该点满足全部 16 条不等式!

2. 定理 5(比二阶锥 Conic 更紧的凸包证明)算例(对应原文 Remark 3 & Figure 3):在 n=2n\ = \ 2, (u0,u1,u2)=(1,1,2)(u_{0},\ u_{1},\ u_{2})\ = \ (1,\ 1,\ 2) 的例子中,考虑分数点 (x¯1,y¯0,y¯1,y¯2)=(0.95,0.35,0.25,0.20)({\overline{x}}_{1},\ {\overline{y}}_{0},\ {\overline{y}}_{1},\ {\overline{y}}_{2})\ = \ (0.95,\ 0.35,\ 0.25,\ 0.20)。Sen et al. (2018) 提出的二阶锥松弛(Conic)要求 wy1≥x12w\ y_{1}\ \geq \ x_{1}^{2} 且 wy0≥1w\ y_{0}\ \geq \ 1(其中 w=1+x1+2x2w\ = \ 1\ + \ x_{1}\ + \ 2x_{2})。取 x¯2=0.83{\overline{x}}_{2}\ = \ 0.83 时 w¯=3.61\overline{w}\ = \ 3.61,此时 w¯y¯1=0.9025≥x¯12=0.9025\overline{w}\ {\overline{y}}_{1}\ = \ 0.9025\ \geq \ {\overline{x}}_{1}^{2}\ = \ 0.9025,完全通过了二阶锥检验!但是,将该点代入定理 5 的(UNDER)不等式 2y1+2y2−x1≥02y_{1}\ + \ 2y_{2}\ - \ x_{1}\ \geq \ 0:左边 2(0.25)+2(0.20)−0.95=−0.05<02(0.25)\ + \ 2(0.20)\ - \ 0.95\ = \ - 0.05\ < \ 0,当场被判定为非法并切掉!这直观说明了定理 5 给出的是真正的最紧多面体凸包,严格优于二阶锥松弛。

4.8 推论 2(Corollary 2):基础模型 CH-0 的精确性与割平面序列 CH-K 的有限步收敛性

【推论 2 原文核心表述】 仅使用(MCCORMICKPLUS)中的 4n(m+1)4n(m + 1) 条基础线性不等式构建的基础混合整数规划模型 CH-0 已经是原问题(QAP)的一个精确重构(Exact formulation);并且随着割平面迭代轮数 KK 的增加,由 Algorithm 2 生成的模型序列 CH-K 的连续松弛最优目标值将在有限步内收敛至完整凸包模型 CH 的连续松弛最优值。

【推论 2 直观算例与工程实现意义】

算例解释:为什么 CH-0 只用了每个商品 4 条不等式(而非全部 2n−12^{n - 1}} 条),就能保证求出 QAP 的精确整数最优解?假设线下备货决策 xjx_{j} 取定了 0 或 1 的整数值:① 若 xj=0x_{j}\ = \ 0(门店不备货商品 jj),CH-0 中的不等式 yij≤αi(j)xjy_{ij}\ \leq \ \alpha_{i}(j)\ x_{j} 立刻变为 yij≤0y_{ij}\ \leq \ 0,结合 yij≥0y_{ij}\ \geq \ 0 强制得出 yij=0y_{ij}\ = \ 0(线上线下无人能买到未备货商品);② 若 xj=1x_{j}\ = \ 1(门店备货商品 jj),CH-0 中的线下不等式 y0j≥α0(⌀)xj+y00−α0(⌀)y_{0j}\ \geq \ \alpha_{0}(\varnothing)\ x_{j}\ + \ y_{00}\ - \ \alpha_{0}(\varnothing) 立刻变为 y0j≥y00y_{0j}\ \geq \ y_{00}},结合 y0j≤y00y_{0j}\ \leq \ y_{00}} 强制得出 y0j=y00y_{0j}\ = \ y_{00}},同时约束 (1e) 强制分母倒数 yi0y_{i0} 准确等于 MNL 分母!

管理与计算价值:这意味着我们在工程实现时,根本不需要把指数级数量的不等式全部塞进求解器,甚至不需要在分支定界树的每个节点上通过复杂的 Callback 动态加割平面!只需在根节点前先跑 K=2K\ = \ 2 轮 Algorithm 2(即生成 CH-2),把连续松弛间隙(LP Relaxation Gap)收紧到接近 0%,然后直接交给 Gurobi 求解一次 MIP,就能保证 100% 得到全局最优整数解!

4.9 推论 3(Corollary 3):一般受约束单渠道 MNL 品类规划的紧致线性规划(LP)表述

【推论 3 原文核心表述】 考虑单渠道受线性约束的 MNL 品类优化问题(CONS-MNL):

max{∑j∈Nrjujxju0+∑j∈Nujxj|𝐂𝐱≤𝐝,𝐱∈{0,1}n} (CONS-MNL).max\ \left\{ \frac{\sum_{j \in N}^{}{r_{j}u_{j}x_{j}}}{u_{0}\ + \ \sum_{j \in N}^{}{u_{j}x_{j}}}\ |\ \mathbf{C}\mathbf{x}\ \leq \ \mathbf{d},\ \ \mathbf{x}\ \in \ \left\{ 0,\ 1 \right\}^{n} \right\}\text{ (CONS-MNL).}

若 AA 乘 𝐱0\mathbf{x}_{0} 加 BB 乘 𝐳i∈ℝn\mathbf{z}_{i}\ \in \ {\mathbb{R}}^{n} 小于等于 bb 是可行域整数集凸包的紧致线性描述,则(CONS-MNL)可直接转化为如下纯线性规划(LP)精确求解:

max{∑j∈Nrjujyj|𝐀𝐲+𝐁𝐳≤𝐛y0,y0≥0,u0y0+∑j∈Nujyj=1}.max\ \left\{ \sum_{j \in N}^{}{r_{j}u_{j}y_{j}}\ |\ \mathbf{A}\mathbf{y}\ + \ \mathbf{B}\mathbf{z}\ \leq \ \mathbf{b}y_{0},\ \ y_{0}\ \geq \ 0,\ \ u_{0}y_{0}\ + \ \sum_{j \in N}^{}{u_{j}y_{j}}\ = \ 1 \right\}.

【推论 3 直观算例:突破全单模(TU)限制,用纯 LP 求解平衡矩阵覆盖约束】

背景与算例:早期文献(Avadhanula et al. 2016, Sumida et al. 2021)证明了当约束矩阵 C 是全单模矩阵(TU matrix)时,受约束 MNL 品类优化可写成 LP。但在零售实践中,品类覆盖约束(Covering constraints,如要求每个商品大类至少选 1 件以保障品类丰富度)对应的矩阵往往不是全单模矩阵!

具体数值例子:假设有 4 种商品,划分为 3 个重叠的功能标签组:C1={1,2C_{1}\ = \ \{ 1,\ 2}(早餐类)、C2={2,3C_{2}\ = \ \{ 2,\ 3}(乳制品)、C3={1,3,4C_{3}\ = \ \{ 1,\ 3,\ 4}(高蛋白),要求每组至少上架 1 件商品:x1+x2≥1,x2+x3≥1,x1+x3+x4≥1x_{1}\ + \ x_{2}\ \geq \ 1,\ x_{2}\ + \ x_{3}\ \geq \ 1,\ x_{1}\ + \ x_{3}\ + \ x_{4}\ \geq \ 1。如果考察前三个变量的子矩阵 [[1, 1, 0], [0, 1, 1], [1, 0, 1]],其行列式等于 2(不等于 0, ±1),说明它不是全单模(TU)矩阵,或者是更一般的不含奇圈关联结构的平衡矩阵(Balanced matrix,Berge 1972)!

应用推论 3:组合数学定理表明,当覆盖右端项 lk=1l_{k}\ = \ 1 且系数矩阵为平衡矩阵时,其整数可行域的凸包依然等于其自身的 LP 松弛!因此根据推论 3,我们根本不需要动用整数规划或近似算法(如 Housni et al. 2024),直接写出线性约束 y1+y2≥y0,y2+y3≥y0,y1+y3+y4≥y0,0≤yj≤y0y_{1}\ + \ y_{2}\ \geq \ y_{0},\ y_{2}\ + \ y_{3}\ \geq \ y_{0},\ y_{1}\ + \ y_{3}\ + \ y_{4}\ \geq \ y_{0},\ 0\ \leq \ y_{j}\ \leq \ y_{0} 并求解一个纯线性规划(LP),就能在多项式时间内直接得到精确的 0-1 最优品类!

4.10 定理 6(Theorem 6)与推论 4(Corollary 4):混合独立需求模型与先行约束下的多项式时间 LP 表述

【定理 6 原文核心表述】 考虑线下客群服从 MNL 模型、线上各细分客群服从独立需求模型(IDM),且线下门店备货需满足有向图 G=(N,E)G\ = \ (N,\ E) 上的先行约束(Precedence constraints) x0j≥x0k ((j,k)∈E)x_{0j}\ \geq \ x_{0k}\text{ (}(j,\ k)\ \in \ E\text{)} 的即时零售品类规划问题(QAP-IDM):

maxα0R0MNL(𝐱0)+∑i∈MαiRiIDM(𝐱i)s.t. 𝐱i∈{0,1}n for i∈M+,𝐱0≥𝐱i for i∈M,x0j≥x0k for (j,k)∈E. (QAP-IDM)\begin{array}{r} max\ \ \ \alpha_{0}R_{0}^{\text{MNL}}\left( \mathbf{x}_{0} \right)\ + \ \sum_{i \in M}^{}{\alpha_{i}R_{i}^{\text{IDM}}\left( \mathbf{x}_{i} \right)} \\ \text{s.t. }\mathbf{x}_{i}\ \in \ \left\{ 0,\ 1 \right\}^{n}\text{ for }i\ \in \ M^{+},\ \ \ \mathbf{x}_{0}\ \geq \ \mathbf{x}_{i}\text{ for }i\ \in \ M,\ \ \ x_{0j}\ \geq \ x_{0k}\text{ for }(j,\ k)\ \in \ E. \end{array}\text{ (QAP-IDM)}

若所有商品在所有渠道的单位收益均非负(rij≥0r_{ij}\ \geq \ 0),则利用(UNDER)不等式构建的如下线性规划模型(QAP-IDM-LP)与原离散问题(QAP-IDM)完全等价,且可在多项式时间内求解:

maxα0∑j∈Nr0jujyj+∑i∈Mαi(∑j∈Nrijθijxj)s.t. u0y0+∑j∈Nujyj=1,0≤yj≤y0 for j∈N,yj≥yk for (j,k)∈E, (xj,y0,𝐲) satisfies (UNDER) for j∈N and S⊆N∖{j}. (QAP-IDM-LP)\begin{array}{r} max\ \ \ \alpha_{0}\sum_{j \in N}^{}{r_{0j}u_{j}y_{j}}\ + \ \sum_{i \in M}^{}{\alpha_{i}\left( \sum_{j \in N}^{}{r_{ij}\theta_{ij}x_{j}} \right)} \\ \text{s.t. }u_{0}y_{0}\ + \ \sum_{j \in N}^{}{u_{j}y_{j}}\ = \ 1,\ \ \ 0\ \leq \ y_{j}\ \leq \ y_{0}\text{ for }j\ \in \ N,\ \ \ y_{j}\ \geq \ y_{k}\text{ for }(j,\ k)\ \in \ E, \\ \text{ }\left( x_{j},\ y_{0},\ \mathbf{y} \right)\text{ satisfies (UNDER) for }j\ \in \ N\text{ and }S\ \subseteq \ N\ \backslash\ \left\{ j \right\}. \end{array}\text{ (QAP-IDM-LP)}

【推论 4(Corollary 4)原文核心表述】 作为定理 6 的直接推论,Cao et al. (2023) 研究的单渠道混合 MNL 与独立需求模型(MIXTURE),在带有有向图先行约束 G=(N,E)G\ = \ (N,\ E) 且商品收益非负时,可通过(UNDER)不等式转化为多项式时间可解的线性规划(LP)。

【定理 6 与推论 4 直观数值算例:先行约束、随机舍入与负毛利反例】

1. 商业场景与算例设定:假设某超市与品牌商签订供货协议,存在先行约束(Precedence constraint):若想在门店上架高毛利的“网红限定口味酸奶(商品 2,r2=12r_{2}\ = \ 12 元)”,必须先上架基础款“经典原味酸奶(商品 1,r1=6r_{1}\ = \ 6 元)”,即约束为 x01≥x02x_{01}\ \geq \ x_{02}}(对应有向边 (1,2)∈E(1,\ 2)\ \in \ E)。线下顾客按 MNL 模型在 {1,2\{ 1,\ 2} 中替代选择;而线上顾客在 App 搜索购买时互不替代(服从独立需求 IDM,购买概率分别为 θ1=0.3,θ2=0.4\theta_{1}\ = \ 0.3,\ \theta_{2}\ = \ 0.4)。

2. 为什么当 rij≥0r_{ij}\ \geq \ 0 时(QAP-IDM-LP)能给出精确解?因为所有线上商品收益 rij≥0r_{ij}\ \geq \ 0,一旦线下门店备货了商品 jj(x0j=1x_{0j}\ = \ 1),线上为了最大化 ∑rijθijxij\sum\ r_{ij}\ \theta_{ij}\ x_{ij}},一定会把该商品推荐给所有线上客群(即最优线上决策必然满足 xij=x0j=xjx_{ij}\ = \ x_{0j}\ = \ x_{j})!同时,在目标函数中 xjx_{j} 的系数 ∑αirijθij≥0\sum\ \alpha_{i}\ r_{ij}\ \theta_{ij}\ \geq \ 0 是非负的,最大化目标函数会推动 xjx_{j} 尽可能往大取,因此只需用(UNDER)不等式从上方约束住 xjx_{j},就能限制住 xjx_{j} 的上界!若 LP 解出分数解,按 yjy_{j} 的大小顺序构造嵌套集合族(Nested family)进行随机舍入,由于 y1≥y2y_{1}\ \geq \ y_{2} 保证了嵌套集合天然满足先行约束 x1≥x2x_{1}\ \geq \ x_{2},因此必存在一个 0-1 整数品类达到 LP 最优值!

3. 负收益失效的重要警示(原文 Section 7.2 批注):如果基础款商品 1 是亏本销售的引流品(即 r1<0r_{1}\ < \ 0,负毛利),零售商只是为了拿到畅销品 2 的销售权才被迫考虑上架商品 1。此时目标函数中 x1x_{1} 的系数为负,优化器会试图把 x1x_{1} 往小压(压向 0),而仅靠限制 xjx_{j} 上界的(UNDER)或单商品(OVER)不等式无法阻止 x1x_{1} 在享受到 x2=1x_{2}\ = \ 1 的好处时自身取过小的分数值,导致 LP 松弛出现间隙。这体现了定理 6 中条件 rij≥0r_{ij}\ \geq \ 0 的严密性。

五、 全文结论的经济与管理启示总结

本文不仅在运筹学整数规划与凸化理论上取得了突破,其模型结论、理论性质(如 Proposition 2、Theorem 1–6)与拓展实验(Section 6 & Section 7)更为即时零售平台、全渠道商超(如盒马鲜生、全食超市)以及前置仓生鲜电商(如叮咚买菜)提供了深刻且可落地的经济学与运营管理启示:

5.1 打破“先线下、后线上”的部门墙:全渠道联合品类规划实现“企业收益与消费者福利”双赢

在传统全渠道零售企业中,线下门店采购部门与线上电商运营部门往往各自为政:门店店长通常仅根据线下到店客流的销售数据(遵循传统的收益排序法则 2-STEP-RO)决定门店备货,而线上团队只能在门店现有库存中被动挑选商品做推荐。本文通过 Example 1 与 Proposition 2 深刻揭示了这种“顺序割裂决策”的巨大弊端:

  • 克服高价品偏向与线上客群流失:线下单一客群的收益排序往往倾向于只保留高毛利、高单价的精品,而剔除中低价位的长尾或高性价比商品。然而,线上渠道覆盖周边 3 公里内高度异质化的多元客群,对价格敏感或有特定偏好的线上细分客群一旦在 App 上看不到心仪的高性价比商品,就会直接放弃购买(流向外部选项 ui0u_{i0})。

  • 联合优化创造帕累托改进(Proposition 2 的经济学含义):当企业转向全渠道联合优化(QAP)时,线下门店会有意识地扩充备货品类(𝐱RO≤𝐱QAP\mathbf{x}^{\text{RO}}\ \leq \ \mathbf{x}^{\text{QAP}}),纳入能够强烈吸引线上特定细分客群的商品。尽管这在线下门店可能产生微小的替代分流(在 Example 1 中线下收益仅微降 0.2%),但却能换取线上渠道收益的大幅跃升(总收益提升近 15%)。更重要的是,更丰富的品类意味着无论是线下到店顾客还是线上各细分客群,其面临的备选商品集合都得到了扩展,所有消费者群体的总效用(消费者满意度)与企业总利润实现了同步增长。

5.2 充分发挥线上数据赋能:利用个性化推荐与两阶段偏序筛选精准隔离“蚕食效应”

在传统线下商超中,一旦在货架上摆出低价引流品,所有进店顾客(包括原本愿意买高价品的顾客)都会看到该低价品,从而引发严重的内部蚕食效应(Cannibalization)。本文的模型机制揭示了即时零售相比传统零售的核心数字红利:

  • “物理共享库存 + 线上千人千面隔离”的协同机制:在即时零售中,虽然低价引流品必须物理存放在线下门店(𝐱0\mathbf{x}_{0} 分量为 1),但线上平台拥有个性化展示决策权 𝐱i\mathbf{x}_{i}。企业可以利用线上算法,将该低价商品精准定向展示给价格敏感型线上客群以促成转化,同时对高支付意愿的 VIP 线上客群隐藏该低价品(令其 xij=0x_{ij}\ = \ 0),从而在不牺牲高价值客群毛利率的前提下捕获长尾需求。

  • 洞察“零概率支配行为”以优化曝光效率(2SLM 模型的启示):借助线上丰富的点击流与购买历史数据,企业能够识别消费者在同一品类内部的严格支配偏好(Two-Stage Luce Model, 2SLM)。既然消费者在第一阶段会自动无视被支配的劣势商品,平台在个性化推荐时就应当利用链多面体约束(CH-Chain)直接过滤掉同一支配链上的冗余商品,将宝贵的屏幕曝光位置留给真正具有竞争力的非支配商品。

5.3 灵活适配多元即时零售仓配业态:实体店拣货、纯前置仓与“前店后仓”模式

文章第 7.3 节证明了本文开发的 QAP 整数规划框架并非局限于单一业态,而是可以通过调整参数无缝指导当前即时零售行业的三大主流仓配网络构型:

即时零售商业构型 典型代表企业 QAP 模型参数配置方式 核心运营管理逻辑与优势
1. 店仓一体模式(Store-Picking) 全食超市(Whole Foods)、传统商超接入 DoorDash 标准 QAP:α0>0\alpha_{0}\ > \ 0,𝐱0≥𝐱i\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i}(∀i∈M\forall i\ \in \ M) 线上线下完全共享门店卖场库存;店员在卖场拣货,提升门店坪效,但需平衡卖场顾客的蚕食效应。
2. 纯城市前置仓模式(Front Warehouse) 叮咚买菜(Dingdong)、每日优鲜等 令 α0=0\alpha_{0}\ = \ 0,ℱ0={x0|∑x0j≤k\mathcal{F}_{0}\ = \ \{ x_{0}\ |\ \sum\ x_{0j}\ \leq \ k},𝐱0≥𝐱i\mathbf{x}_{0}\ \geq \ \mathbf{x}_{i} 前置仓不接待线下顾客(α0=0\alpha_{0}\ = \ 0),在城市高租金区域受限于库容上限 kk,纯粹为周边 mm 个线上客群精选总仓备货与个性化推荐。
3. 前店后仓专供模式(Back-Room Space) 盒马鲜生(Hema Fresh)等新零售大店 设虚拟总仓类型 0(α0=0\alpha_{0}\ = \ 0,集合 AA),线下顾客设为类型 m+1m + 1(集合 B⊆AB\ \subseteq \ A) 门店总库存 AA 包含前场卖场 BB 与后仓专属区 A∩B¯A\ \cap \ \overline{B}。既能把易蚕食高毛利品的线上专供品藏在后仓(不对线下顾客开放),又能服务全渠道需求。

5.4 打通“品类规划—供应链约束—日度库存补货”的运营落地闭环

许多学术模型停留在静态流体近似(Fluid approximation)的品类选择层面,难以在复杂的零售现场落地。本文第 7.1、7.2 和 7.4 节为管理实践打通了最后一公里:

  • 兼容复杂的供应商协议与陈列规则:无论企业面临与供应商签订的品类覆盖保底协议(Covering constraints,要求每个分类至少上架 lkl_{k} 种商品),还是品牌商要求的捆绑先行约束(Precedence constraints,上架畅销品必须先上架基础品),本文的凸包重构与(UNDER/OVER)不等式都能在不牺牲求解速度的前提下将其内嵌至优化模型中。

  • 从最优选择概率到抗缺货整数库存目标(Section 7.4):品类规划选出上架商品后,如果门店备货数量不足引发缺货(Stockouts),消费者的动态替代或流失会直接侵蚀理论收益。本文展示了一套实用的库存转化规程:先由 QAP 最优解算出各商品在各客群下的匹配购买概率并乘以客流总数 TT 得到期望小数需求;随后在总库存整数约束下,按照跨客群期望收益贡献的加权价格指标(Weighted price metric)对商品优先级排序,优先向上取整高价值商品的库存量。仿真实验表明,该规程在存在随机动态替代的真实库存环境中依然能够稳定兑现 QAP 的绝大部分理论利润。

  • 算法工程化的降本增效(Algorithm 1 & 2):本文提出的双轮改进选择概率排序割平面算法(CH-2 / CH-Chain-2)无需依赖昂贵的定制化分支定界回调(Callback),仅用标准商业求解器即可在数分钟内求解数百种商品、上百个细分客群的全局最优解,使零售商能够以极低的算力成本进行高频(如每日或每周)的全渠道品类动态调优。

六、 参考文献(References)

以下完整列出本文原文信息及文中所引用的全部 46 篇学术参考文献(严格保持原文作者英文名与国际期刊标准格式):

[0] Chen Y, He T, Rong Y, Wang Y (2026) An Integer Programming Approach for Quick-Commerce Assortment Planning. Management Science 72(10):8789–8809. https://doi.org/10.1287/mnsc.2023.02996.

[1] Avadhanula V, Bhandari J, Goyal V, Zeevi A (2016) On the tightness of an LP relaxation for rational optimization and its applications. Oper. Res. Lett. 44(5):612–617.

[2] Balas E (1998) Disjunctive programming: Properties of the convex hull of feasible points. Discrete Appl. Math. 89(1–3):3–44.

[3] Berge C (1972) Balanced matrices. Math. Programming 2:19–31.

[4] Bertsimas D, Mišić VV (2019) Exact first-choice product line optimization. Oper. Res. 67(3):651–670.

[5] Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, Athena Scientific Series in Optimization and Neural Computation, vol. 6 (Athena Scientific, Belmont, MA).

[6] Bertsimas D, Weismantel R (2005) Optimization over Integers (Dynamic Ideas, Belmont, MA).

[7] Blanchet J, Gallego G, Goyal V (2016) A Markov chain approximation to choice modeling. Oper. Res. 64(4):886–905.

[8] Bront JJM, Méndez-Díaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769–784.

[9] Cao Y, Rusmevichientong P, Topaloglu H (2023) Revenue management under a mixture of independent demand and multinomial logit models. Oper. Res. 71(2):603–625.

[10] Charnes A, Cooper WW (1962) Programming with linear fractional functionals. Naval Res. Logist. Quart. 9(3–4):181–186.

[11] Chen YC, Mišić VV (2021) Assortment optimization under the decision forest model. Preprint, submitted March 25, https://arxiv.org/abs/2103.14067.

[12] Chen R, Jiang B, Ryan CT, Zhang N (2025) Assortment optimization with α-similar substitutes: Insights from customer browsing patterns. Management Sci., ePub ahead of print November 24, https://doi.org/10.1287/mnsc.2023.00786.

[13] Chen J, Liang Y, Shen H, Shen ZJM, Xue M (2022) Offline-channel planning in smart omnichannel retailing. Manufacturing Service Oper. Management 24(5):2444–2462.

[14] Conforti M, Cornuéjols G, Rao MR (1999) Decomposition of balanced matrices. J. Combin. Theory Ser. B. 77(2):292–406.

[15] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming, Graduate Texts in Mathematics, vol. 271 (Springer, Cham, Switzerland).

[16] Davis JM, Gallego G, Topaloglu H (2014) Assortment optimization under variants of the nested logit model. Oper. Res. 62(2):250–273.

[17] Désir A, Goyal V, Zhang J (2022) Capacitated assortment optimization: Hardness and approximation. Oper. Res. 70(2):893–904.

[18] Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.

[19] Dzyabura D, Jagabathula S (2018) Offline assortment optimization in the presence of an online channel. Management Sci. 64(6):2767–2786.

[20] Echenique F, Saito K (2019) General Luce model. Econom. Theory 68(4):811–826.

[21] Echenique F, Saito K, Tserenjigmid G (2018) The perception-adjusted Luce model. Math. Soc. Sci. 93:67–76.

[22] El Housni O, Topaloglu H (2023) Joint assortment optimization and customization under a mixture of multinomial logit models: On the value of personalized assortments. Oper. Res. 71(4):1197–1215.

[23] Elmachtoub AN, Gupta V, Hamilton ML (2021) The value of personalized pricing. Management Sci. 67(10):6055–6070.

[24] Fampa M, Lee J (2021) Convexification of bilinear forms through non-symmetric lifting. J. Global Optim. 80:287–305.

[25] Fawzi H, Gouveia J, Parrilo PA, Saunderson J, Thomas RR (2022) Lifting for simplicity: Concise descriptions of convex sets. SIAM Rev. 64(4):866–918.

[26] Flores A, Berbeglia G, Van Hentenryck P (2017) Assortment and price optimization under the two-stage Luce model. Preprint, submitted June 26, https://arxiv.org/abs/1706.08599.

[27] Gallego G, Li A (2024) A random consideration set model for demand estimation, assortment optimization, and pricing. Oper. Res. 72(6):2358–2374.

[28] Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics, International Series in Operations Research & Management Science, vol. 279 (Springer, New York).

[29] Gallego G, Iyengar G, Phillips R, Dubey A (2004) Managing flexible products on a network. Technical report, Department of Industrial Engineering and Operations Research, Columbia University, New York.

[30] Ghuge R, Kwon J, Nagarajan V, Sharma A (2022) Constrained assortment optimization under the paired combinatorial logit model. Oper. Res. 70(2):786–804.

[31] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1:169–197.

[32] Gupte A, Ahmed S, Cheon MS, Dey S (2013) Solving mixed integer bilinear problems using MILP formulations. SIAM J. Optim. 23(2):721–744.

[33] Gupte A, Kalinowski T, Rigterink F, Waterer H (2020) Extended formulations for convex hulls of some bilinear functions. Discrete Optim. 36:100569.

[34] Gurobi Optimization, LLC (2025) Gurobi Optimizer reference manual. https://www.gurobi.com.

[35] He T, Tawarmalani M (2026) Discreteness to convexity: Promotion planning via simplotope triangulation. Preprint, submitted January 27, https://arxiv.org/abs/2408.04562.

[36] Housni OE, Feng Q, Topaloglu H (2024) Assortment optimization under the multinomial logit model with covering constraints. Preprint, submitted November 15, https://arxiv.org/abs/2411.10310.

[37] Kelley JE Jr (1960) The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8(4):703–712.

[38] Kovach M, Tserenjigmid G (2022) The focal Luce model. Amer. Econom. J.: Microeconomics 14(3):378–413.

[39] Lin H, Li X, Wu L (2026) Intra-category multi-choice preferences learning and assortment recommendation in e-commerce. Production Oper. Management 35(1):304–330.

[40] Lo V, Topaloglu H (2022) Omnichannel assortment optimization under the multinomial logit model with a features tree. Manufacturing Service Oper. Management 24(2):1220–1240.

[41] Luce RD (1959) Individual Choice Behavior: A Theoretical Analysis (Courier Corporation, Lowell, MA).

[42] McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147–175.

[43] McFadden D (1978) Modelling the choice of residential location. Snikers F, Karlquist A, Lundquist L, Weibull J, eds. Spatial Interaction Theory and Planning Models (North–Holland, Amsterdam), 75–96.

[44] Megiddo N (1979) Combinatorial optimization with rational objective functions. Math. Oper. Res. 4(4):414–424.

[45] Rusmevichientong P, Shmoys D, Tong C, Topaloglu H (2014) Assortment optimization under the multinomial logit model with random choice parameters. Production Oper. Management 23(11):2023–2039.

[46] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24 (Springer, Berlin).

[47] Sen A, Atamtürk A, Kaminsky P (2018) A conic integer optimization approach to the constrained assortment problem under the mixed multinomial logit model. Oper. Res. 66(4):994–1003.

[48] Stanley RP (1986) Two poset polytopes. Discrete Comput. Geometry 1(1):9–23.

[49] Statista (2024) Quick Commerce—Worldwide. https://www.statista.com/outlook/emo/online-food-delivery/grocery-delivery/quick-commerce/worldwide.

[50] Sumida M, Gallego G, Rusmevichientong P, Topaloglu H, Davis J (2021) Revenue-utility tradeoff in assortment optimization under the multinomial logit model with totally unimodular constraints. Management Sci. 67(5):2845–2869.

[51] Talluri K, Van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15–33.

[52] Tawarmalani M (2024) New finite relaxation hierarchies for concavo-convex, disjoint bilinear programs, and facial disjunctions. Preprint, submitted May 17, https://arxiv.org/abs/2405.11068.

[53] Tawarmalani M, Richard JPP, Chung K (2010) Strong valid inequalities for orthogonal disjunctions and bilinear covering sets. Math. Programming 124(1–2):481–512.

[54] Tawarmalani M, Richard JPP, Xiong C (2013) Explicit convex and concave envelopes through polyhedral subdivisions. Math. Programming 138(1–2):531–577.

[55] Teo CP, Sethuraman J (1998) The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4):874–891.

[56] Tserenjigmid G (2021) The order-dependent Luce model. Management Sci. 67(11):6915–6933.

[57] Udwani R (2023) Submodular order functions and assortment optimization. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 202 (JMLR.org), 34584–34614.

[58] van Ryzin GJ (2005) Future of revenue management: Models of demand. J. Revenue Pricing Management 4(2):204–210.

[59] Vielma JP (2015) Mixed integer linear programming formulation techniques. SIAM Rev. 57(1):3–57.

[60] Zhang J, Ma W, Topaloglu H (2025) Leveraging the degree of dynamic substitution in assortment and inventory planning. Oper. Res. 73(3):1248–1259.