BoundedOptimization

作者：叶昊星 陈俊锟

关键词

子集枚举，带限制的不等式

题目大意

定义项为两个不同变量相乘。求一个由多个不同项相加，含有$n$个不同变量的式子的最大值。另外限制了每一个变量的最大最小值$Upperbound_{i}$和$Lowerbound_{i}$和所有变量之和的最大值$Max$。

数据范围

$n\leq 13, 0\leq Lowerbound_{i}\leq Upperbound_{i}\leq 100,Max\leq 1300, 2s$。

解法1

注意到如果$Max\geq \sum Upperbound_{i}$那么直接将每个变量赋为$Upperbound_{i}$即可。

否则设变量为$x_{i}$，我们可以得到$\sum x_{i}=Max$。

设原式为$max\{\sum a_{i,j}x_{i}x_{j}\}$，在这道题中$a_{i,j}$是由给定式子决定的01变量。

假设我们已经知道了如何求出没有上下界限制的该方程。（具体做法在后面）

考虑上下界限制。

我们将每个变量按照是否在边界上分为三种情况：最大值，最小值，其他值。

这个可以通过子集枚举得到所有情况，最终的答案显然会属于子集枚举时出现的一种情况。

此时上述方程会有些变量变为固定值（即最大值或最小值），我们对固定一些值的方程进行求解。

如果此时方程的解满足限制，那么该解可能是全局最优解。如果不满足限制，根据调整法易得最优解一定有在边界上的变量。这与其他值变量的定义相矛盾。所以不需要考虑。

然后我们要求的就是在这种条件下f的最值以及此时其他值变量的取值。

显然如果一种情况下求出来的变量不满足要求，那么根据前面的证明，不需要考虑这种情况。

剩下的就是如何求式子$max\{\sum a_{i,j}x_{i}x_{j}\}$在固定一些值后的最值。

我们注意到$a_{x,y}\in \{0,1\}$。

对于两个其他值变量（假设是$x_{1}$和$x_{2}$），如果$a_{1,2}$为$0$且$x_{1}+x_{2}$为定值，那么当其他变量任意取值时，原式可表示为$b_{1}x_{1}+b_{2}x_{2}+c$，此时必然能将某个变量调整至边界使f值不变小，根据上面的论述可知不需要考虑。

所以我们只需要考虑对于所有均属于其他值变量的xi及xj，aij均为1的情况。

对于两个其他值变量（假设是$x_{1}$和$x_{2}$），根据上述可知$a_{1,2}=1$。

于是原式可表示成$x_{1}x_{2}+b_{1}x_{1}+b_{2}x_{2}+c=(x_{1}+b_{2})*(x_{2}+b_{1})-(b_{1}*b_{2}-c)$。

显然当$x_{1}+x_{2}$为定值的条件下，$x_{1}-x_{2}=b_{1}-b_{2}$时f取到最值。

于是可以定义每个变量与$x_{1}$的差值，此时我们幸运地找到了一组$f$取到最大值时变量的值。

至于$b_{x}-b_{y}$，因为对于所有均属于其他值变量的xi及xj，aij均为1，所以其他值变量对$b_{x}$与$b_{y}$的贡献相同，所以差值完全由最大值或最小值变量提供，这个只要在枚举的时候计算即可。

现在我们知道了其他值变量的总和和每个函数与$x_{1}$的差值，于是我们可以$O(n)$将每个变量的值计算出来并判断是否合法。

将所有求出来的f值取max，这样就做完了题目。

时空复杂度

$O(3^n*n^2)-O(n^2)$（参考程序做法）或$O(3^n)-O(n^2)$

解法2

这题并不是线性规划，看起来不好做。

然而数据范围比较小（只有 $n=13$），因此如果在思考不出正解的时候，可以考虑乱搞（雾）。

一种经典的乱搞方式是这样的：首先随机一个解，迭代执行以下操作多次：

1. 随机选择两个不同的变量 $x_p,x_q$

2. 控制在两个变量合法并且 $x_p+x_q$ 不变的情况下，最大化目标函数

在这题中，确定了其它变量和这两个变量的和之后，目标函数和 $x_p$ 的关系是一个不超过二次的函数，使得目标函数最大化的 $x_p$ 的值可以直接求出。我们要做的，就是在每次迭代的时候 $O(n)$ 扫描其它的点，求出系数，然后直接将两个变量改成能使得目标函数最大化的值。

上述做法会 FST，因为容易陷入局部最优解。可以每迭代若干次之后将两个变量直接随机调整，这样就能通过全部 TC 数据了……（为了保证精度迭代 $5\times 10^6$ 次，每隔 $10^5$ 次随机调整变量）

不是很会证明这个解法的正确性……但感觉比模拟退火稍微靠谱一些，因为模拟退火调整的太厉害，函数不是很连续……

设迭代次数为 $T$，时间复杂度 $O(T n)$，空间复杂度 $O(n^2)$。