matlab - 絶対値による 0-1 最適化 (等価、2 つの不等式)

Question

Optimization Toolboxの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

これは、2 組の制約と同じです。

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 を指定すると、これらの "2 倍の" 制約行列を次のように作成できます。

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

これらの新しい (A,b) を使用して整数計画法を解きます。

Answer 2

これはとても簡単です:

あなたが持ってい|Ax| <= bます。これは (ご自身で指摘されているように) と同等です-b <= Ax <= b。
したがって、追加の不等式制約があります:Ax <= b および -Ax <= b. したがって、abs-value 制約を
すべて定義します。AA = [ A ; -A ]bb = [b;b]

x = bintprog( f, AA, bb );