Research Notes

最近在写一个新的工作，回顾了一下Integer L-shaped method。之前的认知里对Benders Decomposition和L-shaped Method之间的区别并不是特别清晰，通过这次回顾，有了一些新的认知，故将其写成这篇notes。 1 Two Stage Stochastic Programming Benders Decomposition是经典的用于求解MILP问题的算法，他利用可分解结构，将复杂决策变量留在master problem中，将简单决策变量留在sub problem中。与Benders Decomposition的思想一致，L-shaped用于求解两阶段随机规划模型（通过采样平均近似后的模型） $$ \begin{equation*} (\text{TSSP}) \ \min_{\pmb{x} \in \mathcal{X}} \quad \pmb{c}^\top \pmb{x} + \mathbb{E}_{\tilde{\pmb{\xi}} \sim \mathbb{P}} \left[Q(\pmb{x}, \tilde{\pmb{\xi}})\right] \end{equation*} $$ 基于$N$组scenario，TSSP被近似为 $$ \begin{equation*} (\text{TSSP-SAA}) \ \min_{\pmb{x} \in \mathcal{X}} \quad \pmb{c}^\top \pmb{x} + \sum_{n=1}^{N} w_n Q(\pmb{x}, \hat{\pmb{\xi}}_n) \end{equation*} $$ 注意到，其具备一阶段问题和$N$个scenario下的recourse问题，天然有可分解结构。 2 L-shaped Method 考虑如下问题， $$ \begin{equation*} \begin{aligned} \min_{\pmb{x}, \pmb{y}_n} \quad & \pmb{c}^\top \pmb{x} + \sum_{n=1}^{N} w_n \pmb{q}^\top \pmb{y}_n \\ s....

1 Exponential Cone Programming 对于约束， \[ \left\lbrace \begin{aligned} & x \in \mathbb{R}, z \geq y e^{x / y}, && y > 0 \\ & x \leq 0, z \geq 0, && y = 0 \end{aligned} \right. \] 将该曲面上方部分所形成的空间，定义为指数锥（Exponential Cone） \[ \mathcal{K}_{exp} := \left\lbrace (x, y, z) \mid y > 0, z \geq y \exp\left(\frac{x}{y}\right) \right\rbrace \cup \left\lbrace (x, 0, z) \mid x \leq 0, z \geq 0 \right\rbrace \] 这是一个凸的可行域，底层一般采用内点法求解EP。对于我们做上层应用，可以调用Mosek或COPT来求解。...

本周写一篇科研笔记，阐述滴滴派单算法背后的核心思想，展示一种以运筹优化（Operations Research & Mathematical Programming）为核心的 AI 视角，从而拓宽对AI的理解，避免局限在传统Machine Learning/Deep Learning的“桎梏”中。 (a) 网约车扎堆 (b) 打车困难 ​ 网约车平台的核心问题之一是，如何把订单分配给合适的司机？这一过程被称为Order Dispatching（派单）。派单效果会直接影响用户等待时间，司机收入，平台成交率，用户体验等。 ​ 解决派单问题，一种非常直接的思路是：最近司机接最近订单。但这种贪心策略过于短视（myopic），有时会造成供给侧接不到单（如图a）或需求侧打不到车（如图b）。其本质原因在于，当前的决策会影响未来的供需结构。因此，在进行派单时，不仅要考虑当前收益，还需要考虑未来影响。 1 打车流程回顾 用户侧： 用户输入起点和终点 平台进行价格预估 用户提交订单 系统指派合适的司机 司机接驾 完成订单 平台侧： 为订单用户搜索附近可用司机 预测接驾时间 评估不同匹配方案 完成订单分配 ​ 现实中的派单并不是“订单一来立刻派单”，而通常采用Batch Dispatch（批量派单），即：每隔几秒钟收集一批订单和司机，统一进行优化匹配。 2 派单问题的数学模型 ​ 对于每一个batch，记用户数量为J，可用司机数量为I，派单问题可以用如下二部图（Bipartite graph）表示 其中，左侧节点是用户，右侧节点是司机，边表示对应派单决策。同时，每条边带有一个“价值”。 记$x_{i,j}=1$表示用户j指派给司机i。因此，为最大化总体收益，上述派单问题可以建模为 其中，约束（2）表示每位司机至多接一个用户。约束（3）表示每位用户至多被指派给一个司机。 Remark 1: 这个问题很有意思，表面上看其决策变量是binary的（离散），并不容易求解。而实际上，这个问题约束的系数矩阵具有全单模性（Total Unimodularity），直接求解其线性规划松弛就等价于求解原来的离散优化问题。 Remark 2: 在早期的系统中，$w_{i,j}=-\text{pickup distance}$，即基于最小化接送距离进行派单。后来慢慢加入了订单价格、等待时间，变成$w_{i,j}=\lambda_1 \cdot \text{fare} -\lambda_2 \cdot \text{pickup distance} - \lambda_3 \cdot \text{waiting time}$。但随着系统运行，越来越发现无论怎么调整这些系数，总是会出现某些区域订单很多而司机不足，或者某些区域订单很少而司机非常多。其本质原因在于模型过于短视，只考虑当前最优，而忽略了当前派单决策会直接影响未来的司机分布。 3 多智能体强化学习 Motivation：平台的目标是最大化长期收益。在实时运行中，由于当前派单决策会影响未来司机分布，如果能直接用一个模型来预测每条边对应的长期价值，那么似乎问题就解决了。 3.1 前处理 基于六边形网格，对城市空间位置进行离散化 将调度时间轴离散化...

近些年来，分布鲁棒优化（Distributionally Robust Optimization, DRO）与数据科学的结合发展迅速，尤其是在如何利用历史数据构建更具表达能力的不确定集这一问题上，出现了大量新思路。其中，一类非常重要的方法是基于上下文信息分布鲁棒优化（Contextual DRO, CDRO）。这类方法不再假设所有历史样本同分布，而是尝试根据当前环境（如天气、时间、区域等）筛选“更相关”的历史数据，从而构建更精细的分布刻画。 本周，我重点回顾了基于局部学习（local learning）的上下文鲁棒优化方法。其核心思想是：只利用“与当前情境相似”的历史样本来刻画不确定性，而不是对所有历史数据一视同仁。 1 局部学习 局部学习（Local Learning）是一类基于“相似性”的方法，其核心思想是： 在进行预测或估计时，优先利用与当前输入更接近的样本，而不是使用全部数据。 具体来说，给定一个输入 $x$，通过某种距离度量找到与其相似的历史样本，并基于这些“邻近数据”进行计算。根据使用方式的不同，局部学习通常分为两类： 硬选择：只选取最近的一部分样本（如kNN）； 软加权：对所有样本赋权，但距离越近权重越大（如KDE）。 1.1 K最近邻 K最近邻（k-Nearest Neighbors, kNN）是一种最直观的局部学习方法。 基本思想： 对于当前上下文 $x$，在历史数据集中找到与其“最相似”的 $k$ 个样本，仅使用这 $k$ 个样本来进行建模。 具体做法: 定义距离度量 对上下文特征空间定义一个距离函数，例如欧氏距离： $$ > d(x, x_i) = \lVert x - x_i\rVert_2 > $$ 选择邻居 在历史样本 $\lbrace x_i \rbrace_{i=1}^N$ 中，选取距离当前 $x$ 最近的 $k$ 个样本，记为集合 $\mathcal{N}_k(x)$。 构建经验分布 仅基于这 $k$ 个样本构建经验分布： $$ > \hat{\mathbb{P}}_k = \frac{1}{k} \sum\_{i \in \mathcal{N}\_k(x)} \delta\_{\xi_i} > $$ 特点与理解：...