Network extraction

Documents how the network optimizer extracts a problem.

The 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.

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), 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, 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, 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 CPLEX will carry out such transformations automatically if you set the NetFind parameter appropriately.