Network Interdiction algorithms

[Azzaare]

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
• For Network Interdiction and Adaptive Flow (arc version)
• 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
• 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]

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]

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]

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

[Azzaare]

@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]

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