Search All of the Math Forum:

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

Topic: 0-1 integer programming
Replies: 0

 Miguel Angel Camara Posts: 4 Registered: 12/6/04
0-1 integer programming
Posted: Jun 16, 1996 7:28 AM

[In the question below, the poster would like to know the thinnest
covering of the finite set {0,1}^k by Hamming balls of radius 1. In
particular, he would like a practical algorithm to find such a covering
for k <= 16. - Greg]

I'm interesting to solve this 0-1 integer programming
problem, that is a minimal covering set 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 implemented by me in Turbo Pascal lenguage, and his
results about the complexity of time dont satisfy me. This problem for
n=32=2**5 was executed in 6 hours aproximately in one Pentium 100 Mhz. I'm
(from n=64 to 16384).

bibliography to see will be gratefully.

Excuse me for my poor English.

Regards. I hope your mail or news.

Miguel Angel Camara