matlab - 0-1 绝对值优化（等价，有两个不等式）

Question

优化工具箱中的bintprog命令解决了具有不等式约束和可选等式约束的 0-1 编程问题：Ax <= b 其中 A 是矩阵和 ba 列向量。

我有一个 |Ax| 形式的问题 <= b，或等效地，-b <= Ax <= b。有没有办法用Matlab解决这类问题？

Answer 1

使用 size(A) = [n,m]，您的约束的形式为

for each {i in 1..m}
  -b <= sum {j in 1..n} a_{ij} * x_{ij} <= b

这与两组约束相同

for each {i in 1..m}
  sum {j in 1..n} a_{ij} * x_{ij} <= b
  sum {j in 1..n} a_{ij} * x_{ij} >= -b

由于您必须以 Ax <= b 的形式编写它，它看起来像

for each {i in 1..m}
  sum {j in 1..n} a_{ij} * x_{ij} <= b
  sum {j in 1..n} -a_{ij} * x_{ij} <= b

在 MATLAB 中，给定您原来的 A 和 b，您可以使用

A = [A; -A];
b = [b; b];

并用这些新的 (A,b) 求解你的整数程序。

Answer 2

这很容易：

你有|Ax| <= b. 这相当于（正如您自己指出的） to -b <= Ax <= b。
所以，你有额外的不等式约束：Ax <= b 和 -Ax <= b.
因此，您拥有AA = [ A ; -A ]并bb = [b;b]定义了您的绝对值约束：

x = bintprog( f, AA, bb );