After you have chosen the right optimizer and, if appropriate, you have started from an advanced basis, you may want to experiment with different parameter settings to improve performance. This section describes parameters that are most likely to affect performance of the simplex linear optimizers. (The barrier optimizer is different enough from the simplex optimizers that it is discussed elsewhere in this chapter, in Solving LP Problems with the Barrier Optimizer). The simplex tuning suggestions are arranged according to the following groupings:
The parameters in Table 5.3 determine the pricing algorithms that ILOG CPLEX uses. Consequently, these are the algorithmic parameters most likely to affect simplex linear programming performance. The default setting of these gradient parameters choose the pricing algorithms that are best for most problems. When you are selecting alternate pricing algorithms, look at these values as guides:
ILOG CPLEX records those values in the log file as it works. (By default, ILOG CPLEX creates the log file in the directory where it is executing, and it names the log file cplex.log. Managing Log Files: the Log File Parameter tells you how to rename and relocate this log file.)
If the number of iterations required to solve your problem is approximately the same as the number of rows, then you are doing well. If the number of iterations is three times greater than the number of rows (or more), then it may very well be possible to improve performance by changing the parameter that determines the pricing algorithm, DPriInd for the dual simplex optimizer or PPriInd for the primal simplex optimizer.
The symbolic names for the acceptable values for these parameters are given in Table 5.3 and Table 5.4 below. The default value in both cases is 0.
For the dual simplex pricing parameter, the default value selects steepest-edge pricing. That is, the default (0 or CPX_DPRIIND_AUTO) automatically selects 2 or CPX_DPRIIND_STEEP.
For the primal simplex pricing parameter, reduced-cost pricing (-1) is less computationally expensive, so you may prefer it for small or relatively easy problems. Try reduced-cost pricing, and watch for faster solution times. Also if your problem is dense (say, 20-30 nonzeros per column), reduced-cost pricing may be advantageous.
In contrast, if you have a more difficult problem taking many iterations to complete Phase I and arrive at an initial solution, then you should consider devex pricing (1). Devex pricing benefits more from ILOG CPLEX linear algebra enhancements than does partial pricing, so it may be an attractive alternative to partial pricing in some problems. Do not use devex pricing, however, if your problem has many columns and relatively few rows. In such a case, the number of calculations required per iteration will usually be disadvantageous.
If you observe that devex pricing helps, then you might also consider steepest-edge pricing (2). Steepest-edge pricing is computationally more expensive than reduced-cost pricing, but it may produce the best results on difficult problems. One way of reducing the computational intensity of steepest-edge pricing is to choose steepest-edge pricing with initial slack norms (3).
Poorly conditioned problems (that is, problems in which even minor changes in data result in major changes in solutions) may benefit from an alternative scaling method. Scaling attempts to rectify poorly conditioned problems by multiplying rows or columns by constants without changing the fundamental sense of the problem. If you observe that your problem has difficulty staying feasible during its solution, then you should consider an alternative scaling method.
Scaling is determined by the parameter ScaInd, and may be set to any of the following values:
ILOG CPLEX dynamically determines the frequency at which the basis of a problem is refactorized in order to maximize iteration speed. On very large problems, ILOG CPLEX refactorizes the basis matrix infrequently. Very rarely should you consider increasing the number of iterations between refactorizing. The refactorization interval is controlled by the ReInv parameter. The default value of 0 means ILOG CPLEX will decide dynamically; any positive integer specifies the user's chosen factorization frequency.
It is possible to control the way ILOG CPLEX builds an initial (crash) basis through the CraInd parameter.
In the dual simplex optimizer, the CraInd setting determines whether ILOG CPLEX aggressively uses primal variables instead of slack variables while it still tries to preserve as much dual feasibility as possible. If its value is 1 (one), it indicates the default starting basis; if its value is 0 (zero) or -1, it indicates an aggressive starting basis. These values are summarized in Table 5.6.
In the primal simplex optimizer, the CraInd setting determines how ILOG CPLEX uses the coefficients of the objective function to select the starting basis. If its value is 1 (one), ILOG CPLEX uses the coefficients to guide its selection; if its value is 0 (zero), ILOG CPLEX ignores the coefficients; if its value is -1, ILOG CPLEX does the opposite of what the coefficients normally suggest. These values are summarized in Table 5.7.
ILOG CPLEX automatically handles memory allocations to accommodate the changing size of a problem object as you modify it. And it manages (using a cache) most changes to prevent inefficiency when the changes will require memory re-allocations. If an application builds a large problem in small increments, you may be able to improve performance by increasing the growth parameters, RowGrowth, ColGrowth, and NzGrowth. In particular, if you know reasonably accurate upper bounds on the number of rows, columns, and nonzeros, and you are building a large problem in very small pieces with many calls to the problem modification routines, then setting the growth parameters to the known upper bounds will make ILOG CPLEX perform the fewest allocations and may thus improve performance of the problem modification routines. However, overly generous upper bounds may result in excessive memory use.
