具有二元变量的完全单模矩阵

问题描述

请您帮我解决这个问题

我有完全单模矩阵A乘以二元变量X集.

I have totally uni-modular matrix A multiplied by set of Binary variables X.

这意味着A * X

it means that A*X<=B

如何在多项式时间内解决此问题..我只想找到一个可行的解决方案.

how to solve this problem in polynomial time .. I am interested in finding just one feasible solution.

例如我有:

A= [ 1  1  1  0  0  0  0  0 ;
     0  0  1  1  1  1  0  0 ;
     0  0  0  0  1  1  1  1 ;
     1  1  1  1  1  0  0  0 ;
     0  0  0  0  0  1  1  1 ;
    -1 -1 -1 -1  0  0  0  0 ;
     0 -1 -1 -1 -1  0  0  0 ;
     0  0  0 -1 -1 -1 -1  0 ;
     0  0  0  0  0 -1 -1 -1 ];

B= [ 2 ; 2; 2; 3; 2;-3;-3;-2;-2];

推荐答案

使用 bintprog (二进制整数编程)，来自优化工具箱:

This easily solved with bintprog (binary integer programming) from the Optimization toolbox:

x = bintprog(ones(size(A,2),1),A,b)

返回

x =

      0
      1
      1
      1
      0
      0
      1
      1

您可以轻松确认A*x产生b.当然，不能保证这是唯一的解决方案.有关bintprog算法和调整选项的更多信息，请参见本文.根据此Wikipedia页面，bintprog所在的分支定界方法可以具有多项式时间复杂度.

You can easily confirm that A*x yields b. Of course it's not guaranteed that this is the only solution. For more on the bintprog algorithm and options for tuning, see this article. According to this Wikipedia page, the branch-and-bound method on which bintprog is based can have polynomial time complexity.

此外，正如@thewaywewalk指出的那样， lsqlin 可以也可以利用:

Additionally, as @thewaywewalk points out, lsqlin can also be leveraged:

x = lsqlin(A,b,A,b,[],[],zeros(size(A,2),1),ones(size(A,2),1))

这篇关于具有二元变量的完全单模矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！