I have a fairly large network with eleven commodities and arc capacities that are commodity-dependent (i.e. an arc may have a higher capacity for one commodity than another). I'm solving a protection-interdiction-restoration problem using Benders' decomposition, and running into some initial error because (I believe) the network is unbalanced so there is unmet demand to start. What would be a potential way to check how the network is unbalanced? The supply and demand for each commodity are equal across the entire network, but there may be some issue with arc capacity or general connectivity.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
From your question I gather that your problem instance is infeasible because your network capacities are not high enough. One easy trick is to include artificial arcs that directly connect a supply and a demand node. These artificial arcs have unlimited capacity (or capacity equal to the demand). Give these arcs a high cost (larger than the most expensive path that connects the supply and demand node pair in the original graph). That way, if the original network does not have enough capacity, some volume will be routed through the expensive artificial arcs and your solution is guaranteed to be feasible.
$\begingroup$
$\endgroup$
In addition to Joris's answer, another thing you might want to try is to solve a min cost flow problem on the network, without any interdiction threat and (importantly) without using Benders decomposition. If capacity is a bottleneck, this will identify it. If the min cost flow problem is feasible, then it may be that your Benders cuts are rendering the problem infeasible, in which case you might want to check that they are implemented correctly.
