Application of DC Analyzer to Combinatorial Optimization Problems

Solution of many combinatorial optimization problems can be found by analyzing appropriate electrical networks made up of positive resistors, voltage sources, current sources and ideal diodes. This method is an alternative approach for the approximate solution of such problems. Two graph method based fast simulator is a more suitable option for this purpose than modified nodal analysis based conventional simulators. Using this approach the authors have made an attempt to solve min cost flow and single source shortest path problems. A planar min cost flow problem of size 200,000 nodes and 600,000 edges is solved by our simulator approximately within 0.1% of the optimum solution in about 11 mins. The authors have exactly solved a planar single source shortest path problem (having negative edge weights also) of size 100, 000 nodes and 600, 000 edges in about 2 mins. The authors have performed our experiments on a PIV processor having 1 GB RAM