计算科学 - 捕获 MILP 中某些对象的顺序 - 吾爱随笔录

我有一个凸优化问题，它取决于一组的顺序 $N$ 对象。这意味着，对于每个可能的排序，我都会得到一个不同的凸优化问题。我的最终目标是在给定所有可能排序的情况下找到最佳解决方案。一种方法是解决所有问题 $n!$ 可能的问题。一个更好的方法（我认为）是将整个事情写成一个 MILP，让 MOSEK 来处理这些艰苦的工作。我这样做如下：我创建了 $N$ 每个对象的二进制变量总共 $N^2$ 二进制变量。说对象是 $F_1,\ldots,F_N$ 并且二进制变量是 $b_{kj}$ 在哪里 $k,j\in\{1,\ldots,N\}$ .

我让

b_{k j} = {\begin{cases} 1 & if object F_{k} goes into position j; \\ 0 & otherwise . \end{cases}

$b_{kj} = \left\{ \begin{array}{ll} 1 & \text{if object $F_k$ goes into position $j$;} \\ 0 & \text{otherwise}. \end{array} \right.$

为了保证每个对象都准确地进入一个位置，我对每个对象都强制执行以下约束 $k$ ：

\sum_{j = 1}^{N} b_{k j} = 1

$\sum_{j=1}^N b_{kj} = 1$ 此外，为了保证每个位置都接收到一个对象，我对每个位置强制执行以下约束

j

$j$ ：

\sum_{k = 1}^{N} b_{k j} = 1

$\sum_{k=1}^N b_{kj} = 1$

这对我有用，我能够使用 MOSEK 解决问题。

我的第一个问题是：有没有更好的方法来做到这一点？可能少于 $N^2$ 二进制变量？

我的第二个问题是：假设我想要对象 $p$ 出现在对象之前 $q$ . 我如何在约束中强制它？我能想出的唯一想法是以下。我们必须对每个 $k \in \{1,\ldots,N-1\}$ .

b_{p k} = 1 \Rightarrow b_{q k} = \dots = b_{q N} = 0

$b_{pk} = 1 \Rightarrow b_{qk} = \ldots = b_{qN} = 0$ 我们翻译成：

b_{p k} = 0 \lor b_{q k} = \dots = b_{q N} = 0

$b_{pk} = 0 \vee b_{qk} = \ldots = b_{qN} = 0$ 由于“或”，这将需要额外的二进制变量来处理。有更好的主意吗？

谢谢