Network Interdiction algorithms

JuliaGraphs / LightGraphsExtras.jl

Additional functionality for LightGraphs.jl

Other

21 stars 13 forks source link

Network Interdiction algorithms #5

Open Azzaare opened 8 years ago

Azzaare commented 8 years ago

As mentioned in issue #400, LightGraphs.jl, I would like to add some algorithms to compute Network Interdiction flows.

As a mid-term objective it would be:

A polynomial algorithm (exact for a category of network, approximation otherwise) based on the Extended Multiroute Flow available (very soon) in LightGraphs.jl
- [x] For Network Interdiction and Adaptive Flow (arc version)
- [x] 2-approximation for Adaptive Flow (path version)
A Bilevel Mixed-Integer Linear Program (BMILP) using JuMP when the previous algorithm fails to give the exact value
- [x] For Adaptive Flow (arc version)
- [ ] For Adaptive Flow (path version)
- [ ] For Network Interdiction (available in the literature)

There are a couple of other algorithms available also in the academic literature, but I don't plan to add them before a while.

Azzaare commented 8 years ago

I implemented (including tests) some of the algorithms according to the previous post. For the moment I provided dummy functions for the empty boxes cases. I am still in the process of writing the related documentation.

Would it be OK to have a PR checked and eventually merged for the current work ? I will work the rest out during September, but I would like to share this my team for experimental results and also refer to LightGraphs/LightGraphsExtras for the implementation in an article.

sbromberger commented 8 years ago

Sure - I think this is appropriate. If you're using JuMP or any other non-core, non-leaf package, then LGExtras is the right place for this.

sbromberger commented 7 years ago

@Azzaare now that #6 is merged, should we close this issue, or is there other functionality you're planning on including?

Azzaare commented 7 years ago

@sbromberger sorry, I totally missed the notifications. I am currently waiting for a colleague to take care of the last two points of this issue, but he obviously isn't doing it.

I will take care of those eventually, but I guess it is fine to close the issue. We can reopen it if necessary at some point.

sbromberger commented 7 years ago

Let's keep it open - there's no problem with that. When you get to it, we can close.