Network Extraction

ILOG CPLEX 11.0 User's Manual > Continuous Optimization > Solving Network-Flow Problems > Solving Problems with the Network Optimizer > Network Extraction

Network Extraction

INDEX

PREVIOUS NEXT

The ILOG CPLEX network extractor searches an LP constraint matrix for a submatrix with the following characteristics:

the coefficients of the submatrix are all 0 (zero), 1 (one), or -1 (minus one);
each variable appears in at most two rows with at most one coefficient of +1 and at most one coefficient of -1.

ILOG CPLEX can perform different levels of extraction. The level it performs depends on the NetFind parameter.

When the NetFind parameter is set to 1 (one), ILOG CPLEX extracts only the obvious network; it uses no scaling; it scans rows in their natural order; it stops extraction as soon as no more rows can be added to the network found so far.
When the NetFind parameter is set to 2, the default setting, ILOG CPLEX also uses reflection scaling (that is, it multiplies rows by -1) in an attempt to extract a larger network.
When the NetFind parameter is set to 3, ILOG CPLEX uses general scaling, rescaling both rows and columns, in an attempt to extract a larger network.

In terms of total solution time expended, it may or may not be advantageous to extract the largest possible network. Characteristics of your problem will qualify the tradeoff between network size and the number of simplex iterations required to finish solving the model after solving the embedded network.

Even if your problem does not conform precisely to network conventions, the network optimizer may still be advantageous to use. When it is possible to transform the original statement of a linear program into network conventions by these algebraic operations:

changing the signs of coefficients,
multiplying constraints by constants,
rescaling columns,
adding or eliminating redundant relations,

then ILOG CPLEX will carry out such transformations automatically if you set the NetFind parameter appropriately.

PREVIOUS NEXT