# Modeling damaged edges on a network flow

I am working on a fake-ish research proposal for an undergraduate "writing for engineers" course. I am currently exploring the idea of a graph theory problem which models damage to a network flow. The main idea being that nodes on the graph have some amount of demand for resources, but edge capacities have been restricted/damaged. An edge $e$ in this model has:

• some capacity $c_e$ - amount of supply that can traverse the edge
• some weight $w_e$ - time to traverse the edge
• some repair cost $r_e$ - amount of man hours to increase capacity 1 unit
• some max capacity $m_e$ - when capacity reaches this point, no further repairs are possible.

A vertex $v$ in this model has:

• some amount of demand for resource $d_v$ - negative demand implies a source/supply.

The model works by simulation over discrete time intervals, say "hours". Each hour labor can be sent on a path towards a new edge, capacities are updated to reflect repairs,and unmet demand is recorded as $u_i$ for the $i^{th}$ hour.The problem is to minimize the $\sum_{i} u_i$ over the time it takes to restore all edges to maximum capacity.

My question is, does this sound remotely useful? Can anyone with experience in computer science / graph theory research point me in the direction of something that sounds remotely similar to this? Ultimately I am trying to construct an application of graph theory optimize aspects of recovering from a natural disaster.

• You are actually seeking for some Stochastic Processes course final project. – Brethlosze Nov 24 '17 at 5:17
• In my problem formulation I am presuming a lot of information is provided, while I see who most of the qualities of this graph should be supplied by a stochastic process, my focus is not in constructing the graph, but rather solving the optimization problem more or less how I stated it. – hulud Nov 24 '17 at 5:51
• Well, if simulation is not the focus, but optimization, i see the problem is really direct to solve after formulating it. You should write both the constraints and the objective function in the standard way, and thus the solution will arise straightforwardly. This is very similar to a Markov Chain model. But clarify yourself in what is the focus... – Brethlosze Nov 24 '17 at 6:00
• Such a solution would be completely intractable though no? The underlying problem is derivation of the facilities location problem which is known to be NP-hard. I suppose this question is too open ended for this setting, I am not really looking for a mathematical solution, but rather similar problems with a body of research around them into how the algorithmic complexity was managed, whether by heuristics / approximation or some other method. – hulud Nov 24 '17 at 15:29
• Well i insist on the stochastic process systemic approach. Things as queues, waiting times, event times, event rates, are standard, no need to innovate in there. Some solvers for simulate systems are available too. IF you dont intend to do anything else, and do not have experience, that is your best choice. By the way saying that the problem is NPh dont add anything new.... most if not all models with discrete variables are. – Brethlosze Nov 24 '17 at 19:00