Originally posted by: UserCplex

Hello:

The following is from the CPLEX manual

Quote 1:

setting RootAlg to Network in Concert Technology

When you do so, CPLEX performs a sequence of steps. It first searches for a part of the LP that conforms to network structure. Such a part is known as an embedded network. It then uses the network optimizer to solve that embedded network. Next, it uses the resulting basis to construct a starting basis for the full LP problem. Finally,it solves the LP problem with a simplex optimizer.

I am trying to contrast this with the following quote also from the manual.

Quote 2:

If your entire problem consists of a network flow, you should consider creating a network object instead of an LP object. Then populate it, and solve it with the network optimizer. This alternative generally yields the best performance because it does not incur the overhead of LP data structures. This option is available only for the Callable library.

I code in Concert C++. I have a pure network flow problem - i.e. - I populate IloRangeArray constraint object such that it contains atmost one +1 and one -1 entry in each column. I set the RootAlg of the IloCplex instance to IloCplex::Network.

Now, Quote 1 would indicate that given the above, CPLEX will solve the LP using Network Simplex. Is this right? But, what does this mean? Does this mean that CPLEX will internally create the network object (as indicated in Quote 2) and solve this object using network simplex?

To really exploit the network simplex algorithm, should I only code using the C Callable Library and not Concert?

Thanks.

Originally posted by: RWunderling

The network optimizer is only directly available through the C API via the functions starting with CPXNET...().  It allows you to build a network problem directly in terms of arcs and nodes in the data structures used by the network optimizer.  If you want to use this, you have to use the C API (which you can easily do from C++).

For other APIs, you can only use the network optimizer indirectly: You create an LP representation of the network problem and select the hybrid network optimizer to solve it. CPLEX will then cary out the follwoing steps:

1. extract a (sub-)network from the LP to the network optimizer.  If your problem is indeed the natural LP representation of a pure network problem, it will extract the full network; otherwise some constraints will not be extracted

2. Solve the resulting network problem

3. install the optimal basis from the network solver in the original LP problem (potentially extending it with basic statuses for the constraints that could not have been extracted in step 1)

4. Solve the LP from this advanced basis.

Roland

Originally posted by: UserCplex

Hi Roland,

Thanks.

Just a clarification. When you say:

2. Solve the resulting network problem

what you really mean is that CPLEX solves the embedded network problem using primal network simplex, right? OK. That is what I guessed.

The larger problem I am seeing in my application is that Primal Network Simplex is simply not that competitive (atleast not to the extent of 10 to 100 times as compared to primal simplex) as quoted in the CPLEX manual and as widely reported in OR literature.

I have a problem

[LP]

min cx

Ax = b

x >= 0

where A can be transformed into a network matrix N via non-trivial matrix operations.

The equivalent network problem [NP]  is

min cx

Nx = d

x>=0

I am seeing that using Concert, solving [LP] directly using primal simplex is as competitive as solving [NP] using primal network simplex. I am wondering how much of this lack of competitiveness is due to my coding in Concert C++. Perhaps the overload involved in extracting the network and creating an internal network object followed by reconverting the basis to the LP basis is too time consuming.

Originally posted by: RWunderling

Yes, the CPLEX network optimizer implenets the primal Network Simplex algorithm.

In general with LP or MIP there is no way of apriori predicing performance of one algorithm over another.  If you use Concert for building both LP as well as NP, the performance difference should not be due to Concert.  However, you may get some more insight from looking at the CPLEX log of both runs.  For NP it will display the network extraction time and the time to solve the network problem separately.

Roland