Network Design Optimod

[stevedwards]

Why this Mod?

I have heard Network Design problems being discussed with a few users now so they seem to be receiving a bit of attention. Essentially you have nodes and possible arcs between the nodes as well as commodities that must flow from one specific node to another in certain quantities. There are costs to build the arcs as well as costs for commodities to flow along them. The task is to design the network to minimize the cost such that all the commodities can get where they need to be in the required quantities. This feels like a nice optimod as it can be expressed and visualised with graphs. Alternatively, it could naturally be described in terms of supply chains.

Does it fall under an existing category?

• Graphs

What will the API be?

The data that needs to be conveyed is:

• Network $(N,A)$ of nodes & potential arcs, which can be either directed or undirected.
• Arcs are labelled with a flow cost $c{ij}$, fixed cost $f{ij}$ for building the arc, and capacity $C_{ij}$
• Commodities $k\in K$ with origin/destination $(o_k,d_k)$ and flow demand $W_k$

The API could look something like

network, cost = gurobi_optimods.network_design(arc_labeled_network, commodities)

Where:

• The arc_labeled_network is a scipy object representing the network with all possible arcs, and each arc would be labeled with the flow cost, fixed cost, and capacity.
• commodities is just a list of tuples containing origin, destination, and flow demand.
• network is just another scipy object representing an unlabelled network of nodes and arcs, and the cost is just a float representing the cost to build the network.
• The method might need an optional argument that specifies if the network is directed or not.

Additional context

Started looking into Network Design problems as supposedly they lend themselves well to Benders Decomposition but have found that the default Gurobi behavior is very strong so think a basic MIP model will suffice for this.

[simonbowly]

Sounds great @stevedwards !

Just one thought, I know I suggested scipy.sparse as a way to capture the graph, but I did not think about the multiple labels part. networkx might be more suited to that, or a pandas dataframe with a multi-index like this: https://github.com/Gurobi/gurobipy-pandas/blob/netflow/docs/source/examples/networkflow.ipynb

[stevedwards]

I don't have permissions to assign myself to this mod btw. I've already failed step 1 of contributing haha.