Originally posted by: revolt

Is it possible to access the network simplex iteration count?

The functions IloCplex.getNiterations64(); and CPXgetitcnt(...); always return zero if I use the network simplex for solving a min cost flow problem. However, if I use the command line tool, the log reveals that the number of network simplex iterations is non-zero: 10584. Is it possible to access this value using the C, C++ or Java-API?

Best regards,
Johannes

CPLEX> set lpmethod 3
New value for method for linear optimization: 3
CPLEX> o
Tried aggregator 1 time.
LP Presolve eliminated 0 rows and 2595 columns.
Reduced LP has 21 rows, 7406 columns, and 14812 nonzeros.
Presolve time = 0.03 sec. (5.71 ticks)
Extracted network with 21 nodes and 7406 arcs.
Extraction time = 0.00 sec. (0.43 ticks)
Iteration log . . .
Iteration:     0   Infeasibility     =         23424.000000 (5.89814e+08)
...
Iteration: 10000   Objective         =      11123103.000000

Network - Optimal:  Objective =    1.1135598000e+07
Network time = 0.01 sec. (2.11 ticks)  Iterations = 10584 (6071)

Dual simplex - Optimal:  Objective =  1.1135598000e+07
Solution time =    0.08 sec.  Iterations = 0 (0)
Deterministic time = 9.46 ticks  (116.12 ticks/sec)
 

The information is only available in the C API via CPXNETgetitcnt() (you may want to take a look at the list of network simplex specific function). Since the network API is not accessible from the Concert API the information is not available in C++ or Java.

Originally posted by: revolt

Ok, thanks. It worked. 

However, I had to switch from the C++ LP-API to the C Network-API. Interestingly switching the API caused a speedup by a factor of 2!

Just curious: is this speedup in the actual solution time or in the model build time?

Originally posted by: revolt

The speedup is basically due to the time for model creation and due to the final call to the dual simplex. Enclosed you find a figure which is based on 1000 random min cost flow instances. The marked area is the computing time that is needed for model creation.

One can see that the model creation in the Network API is costs nearly nothing, whereas it is quite expensive if one uses the LP API. If one deactivates the presolving also in the LP API one also gets a significant speedup.

PS: In all test instanstes the number of nodes amounts to 20, whereas the numer of ars ranges from 50 to 10,000, that is, there are a lot of parallel arcs.

Originally posted by: revolt

In the above example Cplex runs the dual simplex after running the Network Simplex. Whereas if I use the network API it only runs the Network Simplex without running the dual simplex. Is this due to the fact, that in the above exaple, CPLEX performs presolving and actually doesn't solve a pure network flow model?

CPLEX> r network.net
Problem 'netex1.net' read.
Read time = 0.04 sec. (0.10 ticks)
CPLEX> o
Iteration log . . .
Iteration:     0   Infeasibility     =         23172.000000 (5.89814e+08)
Iteration:  5000   Infeasibility     =          6726.000000 (-132584)
Iteration: 10000   Objective         =      10931728.000000

Network - Optimal:  Objective =  1.1135598000e+07
Solution time =    0.04 sec.  Iterations = 12627 (9307)

Deterministic time = 4.45 ticks  (122.69 ticks/sec)
 

Originally posted by: RWunderling

CPLEX supports a network problem type, but only via the C API and the interactive.  With all other APIs only the hybrid network optimizer is supported, i.e. the model is stored as an LP from which a network problem is extracted and solved; the resulting basis is installed in the LP as starting basis for the dual Simplex to solve to completion.

Using the network problem type (via that functions starting in CPXNET...() in the C API) you can directly build a network problem formulated as nodes and arcs and solve it with the network simplex algorithm.  Thus comparing to the hybrid network optimizer you don't need the extraction of the network from an LP and the final solve with the dual Simplex method which explains the difference in runtime.  Another difference is that no presolve is carried out on the network problem, whereas it when using the LP formulation.

Roland

Originally posted by: revolt

Thanks for the detailed answer!