1286764557

Source: mpsFileFor10000nodeNDP_Cullenbine.mps
File: upload/11.10.2010_1286764557_Chris_Cullenbine/mpsFileFor10000nodeNDP_Cullenbine.mps
Name: Chris_Cullenbine
Company: Colorado School of Mines
eMail: ccullenb@mymail.mines.edu
Street: 8392 Old Exchange Dr
City: Colorado Springs, CO
Country: UNITED STATES (US)
Message: The problem I chose to include is a large instance of the directed network diversion problem (DND). We want to find a minimum weight, minimal s-t cut that includes a specific edge, the diversion edge, and maintains a flow-preserving path through said edge. DND is provably NP-complete using a transformation from Vertex Cover. The instance I created a .mps file for has 10,002 nodes and 39,800 edges.  CPLEX 12.1 solves this instance in ~286 seconds with an optimal objective of 242.

delivered on: 11.10.2010
Fileupload successfully confirmed!