I proposed an algorithm for multicast in smart grid and I want to compare it with the optimal tree. I tried to to write a model by myself but I finally came up with shortest path tree instead of Steiner tree. Any suggestions will be appreciated .
thankyou kamran . you're right I couldn't find a good resource for that so I started to write a model by myself . I got help from Dr bakhshi and Although my model doesn't work for large networks on my regular linux system -due to it's large number of variables and constraints -but as this model was not an essential part of my thesis , this performance is acceptable . thanks for seeking anyway ...
Steiner tree problema is a particular case for the uncapacited fixed-charge network flow (Newhauser and Wolset, 1998).
http://books.google.com.br/books/about/Integer_and_Combinatorial_Optimization.html?id=84trQgAACAAJ&redir_esc=y
If fij=0, this model is a Steiner tree:
http://www.scielo.br/scielo.php?pid=S0101-74382001000200001&script=sci_arttext
Great problems are hard to solve.
Steiner problems are notoriously hard to solve. The most efficient (exact) algorithms
have been developed by the trio: Warme, Winter and Zachariasen.
after some searches I used the model issued in this presentation :
http://myweb.clemson.edu/~pbelott/bulk/teaching/lehigh/ie426-f09//lecture16.pdf
this model is for Minimum Spanning Tree and I changed it to use for steiner tree.
anyway thanks Dear Bruno, Thomas and Fritz.
You could try these papers:
http://onlinelibrary.wiley.com/doi/10.1002/net.3230230104/abstract
http://www.sciencedirect.com/science/article/pii/S0166218X00003188
Slightly delayed answer:
If you want to solve a geometric Steiner tree problem,
I would recommend GeoSteiner: http://geosteiner.com/
If you want to solve a Steiner tree problem in graphs,
I would recommend SCIP-Jack: http://scipjack.zib.de/
- Badges
- Science topic
- Similar topics
- Biological Science
- Bioecology
- Systems Ecology
- Landscape Ecology
- Connectivity