Totally uni modular matrix with binary variable

Question

please can you help me in solving this problem

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

it means that A*X<=B

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

For example I have:

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];

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]; — user1514730
– user1514730, Commented Dec 7, 2013 at 16:19
you can edit your question, I did that for you. What do you mean whit polynomial time? What about A\B = X? — Robert Seifert
– Robert Seifert, Commented Dec 7, 2013 at 16:35
thank you for editing the question .. it is not possible to solve it in this way because inverse of A is undefined , the determination of A is zero — user1514730
– user1514730, Commented Dec 7, 2013 at 16:40
how it is feasible solution ? what is the values of X in this case — user1514730
– user1514730, Commented Dec 7, 2013 at 17:01

horchler · Accepted Answer · 2013-12-15 21:53:20Z

0

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

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

which returns

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.

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))

edited Dec 15, 2013 at 21:53

answered Dec 8, 2013 at 5:30

horchler

18.5k4 gold badges42 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Totally uni modular matrix with binary variable

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related