Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: 0-1 integer programming
Replies: 0

 Miguel Angel Camara Posts: 1 Registered: 12/18/04
0-1 integer programming
Posted: Jun 15, 1996 11:58 AM

I'm interesting about solving this 0-1 integer programming
problem:

Min sum(Xj), j:=1,...,n
An X >= 1, where An is a matrix recursive like that:

- A1 = 1

- A(n-1 I(n-1)
An =
I(n-1) A(n-1)

where In is de identity matrix of order n.
- n= 2**k, where k:= 1, 2, 3, 4......
- Xj = (0,1).
- An(i,j) = (0,1)

Example: n=8=2**3

Min X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8

|1 1 1 0 1 0 0 0| X1 1
|1 1 0 1 0 1 0 0| X2 1
|1 0 1 1 0 0 1 0| X3 1
|0 1 1 1 0 0 0 1| X4 1
|1 0 0 0 1 1 1 0| X5 >= 1
|0 1 0 0 1 1 0 1| X6 1
|0 0 1 0 1 0 1 1| X7 1
|0 0 0 1 0 1 1 1| X8 1

That is:
X1 + X2 + X3 + X5 >= 1
X1 + X2 + X4 + X6 >= 1
X1 + X3 + X4 + X7 >= 1
+ X2 + X3 + X4 + X8 >= 1
X1 + X5 + X6 + X7 >= 1
+ X2 + X5 + X6 + X8 >= 1
+ X3 + X5 + X7 + X8 >= 1
+ X4 + X6 + X7 + X8 >= 1

The matrix An is symetric, and his determin sometimes is 0.

I'm practising and solving this problem with the aditiv
algorithm of Balas, and his results about the complexity of time don+t
satisfy me. This problem for n=32=2**5 was executed in 6 hours
aproximately in one Pentium 100 Mhz. I'm interesting to solve the

bibliography to see will be gratefully.

Regards. I hope your mail or news.

Miguel Angel Cbmara