Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.stat.math.independent

Topic: 0-1 integer programming
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
Miguel Angel Camara

Posts: 4
Registered: 12/6/04
0-1 integer programming
Posted: Jun 15, 1996 11:58 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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
maximum number of variables about this problem.

All suggestions or recomendations about this problem, or
bibliography to see will be gratefully.

Regards. I hope your mail or news.

Miguel Angel Cámara
Facultad de Cc. Matemáticas
Universidad Complutense de Madrid
Spain

Mail: mcamaral@madrid.idec.es







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.