MCKP.pdf

7.8突然发现gurobi的许可证和硬件绑定甚至包括mac地址，wsl2每次重启都随机生成mac地址，这非常不妙，许可证直接失效了，
这里有在wsl2上激活的提示，固定mac地址再激活…

2. lyft optimization -> blog -> paper

https://eng.lyft.com/how-to-solve-a-linear-optimization-problem-on-incentive-allocation-5a8fb5d04db1

at most one variable with a fractional solution?

LP

分组01背包的线性松弛；一共 组物品，每组有 个物品，每个物品有价值 和费用 ，组内只能选择至多一个物品，并且选择的物品费用总和不能超过上限

可以发现线性松弛的最优解中至多只有一个 s.t. for some j 不为整数

假设最优解中某一组中有两个分数解，其中一个物品效率比另一个更高，降低效率低的物品对应的 提高效率高的物品对应的 ，总价值未必更高，可以轻易构造出一组中有两个分数解的反例（我开始时想要这样证明，但是并不行）

preprocessing

Coupons eliminated in the preprocessing step are dominated by at least one coupon in the feasible set. In other words, the cost, value and efficiency of feasible coupons for each given rider are in increasing order.

assumption

这两个问题（fractional solution 和 preprocessing）都在this文章中解决了，第二个问题对应文章中的proposition 2，同时也说明了预处理就是求同组物品在 平面上的下凸包上的物品。注意到proposition 2 的条件如果再加上每组总有一个 的物品（对应着不选择任何物品），就相当于上面图片中的assumption

第一个问题对应文章的Properties of an Optimal Solution 部分，文章证明了线性规划所有基本解都只有最多两个

每组中一定有一个 在基本解中，而我们可以给每组都增加一个 的物品，可以把约束写成 ，线性规划一共有 个约束，基本可行解一共就有 个变量，那么一定有且仅有一组中两个变量都在基本解中，对于其他组，组内一定只有整数解（为了满足 ）,最多只有两个分数解

the algorithm

简单总结一下lyft解决这个lp的方法和复杂度。 Dual

首先把对偶问题目标函数看成 的函数，根据第一个约束 , 得到目标函数中的

然后发现每一个 的最大值只和 还有第 组的coupons有关，可以求出在给定 的情况下 的最优解然后对于 个 求解，这是lyft的大概思路

  1. 可以求出在给定 的情况下 的最优解，也就是说对于所有i，算出 最优解关于 的函数，根据之前的preprocessing这是一个直线构成的分段函数，并且是下凸的。（实际上对于每一个物品都有 这样的直线，而我们要找的函数显然就是这些直线最上面的边缘线up envelope）而且可以知道如果把物品按照cost大小排序，只有相邻的物品对应的直线交点位于up envelope上(此处出现了错误，未必是相邻物品对应的直线交点才在up envelope上，相邻物品对应的交点也可能不在上面。 见graph from lyft blog)，我们只需要维护这些breakpoints，每个passenger有k个coupon，time complexity .找到这k条直线的up envelope 可以使用这本书 中duality一章17.1.1.2 Convex hull and upper/lower envelopes 介绍的内容，因此k条直线需要 … 然而计算一下得知直线为 对偶的点为 ，要求 构成的up envelope 就相当于求 这些点的凸包的下半部分。 可以看到在预处理的时候（文章）我们采用的方法是求 的“右下方”凸包（这个预处理比lyft blog也就是上文的图片中讲的更强），很容易发现这个部分一定是 的下凸包的一部分。于是发现做过预处理之后这里不需要再做了，剩下的所有物品对应的直线都会出现在up envelope 上，需要 的时间找到所有 breakpoints
  2. LP Dual 的最优解，对于每个i，1中的 函数都是凸函数，他们的和也是，我们需要找到 这个函数的最小值点.

For each rider we keep a pointer to the largest element in the sorted list of breakpoints that has yet to be processed. We start with an active set of breakpoints, one for each passenger i = 1, . . . , m, initially equal to vᵢ₁/cᵢ₁(which is that passenger’s greatest bang/buck value). We initialize the current slope, which is for λ greater than all breakpoints, equal to C, and introduce the notation that cᵢ₀ = 0, i = 1, . . . , m, for a latter use (though this doesn’t correspond to any coupon option).We keep the currently active breakpoints in a priority queue, and in each iteration, extract the maximum remaining one. Suppose that the current breakpoint extracted corresponds to coupon j* for rider i. We know the slope of the dual objective function greater than this breakpoint, and want to compute the slope just less than it. To do so, we need to reflect the change from the old contribution to the slope for i to its new one: the new one is option j, and the old one is option j − 1. If we let let OLD denote the cost of coupon j* − 1 for rider i* and let NEW denote the cost of coupon j* for rider i, then the change of cost is OLD-NEW. To replace the breakpoint extracted for i, we insert the next breakpoint of i* into the priority queue (if there is one available), and the algorithm continues to the next iteration. We continue to iterate until we have decreased the slope from C to below zero.

from lyft blog

LP(one person can be assigned coupons)

Dual

For one passenger

Dual

LP 最优解中: 至多存在一个i 满足 存在非整数解

p=1 时的证明方法大概不行了.

对于 每行至少有一个x不为0， 但是基本解应该有 个元素.

对于每组物品，新的线性规划变量 表示是否取 组物品的某一个组合( )

这样一来就变成了p=1的情况. (coauthor中许超老师的方法) ### p=1 时的预处理

这个显然不满足了，这就导致在计算breakpoint的时候不能拿相邻物品对应的直线直接求，也不能确定哪些直线在 up envelope 上。

凸包？

每组有n个物品，在其中取p个物品 ==> 二维平面有n个点，找其中任意p个点的和（两维坐标分别相加）形成的 个点 形成的凸包

https://arxiv.org/pdf/1111.5340.pdf有关于均匀分布的点凸包上点的数量的研究

n个点在二维平面上均匀分布，凸包上的点只有 个