Simplex Parameters
PREVIOUS
NEXT
| ILOG CPLEX 11.0 User's Manual > Continuous Optimization > Solving LPs: Simplex Optimizers > Tuning LP Performance > Simplex Parameters |
Simplex Parameters |
INDEX
PREVIOUS
NEXT
|
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 documents 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 Solving LPs: Barrier Optimizer). The simplex tuning suggestions appear in the following topics:
The parameters in Table 9.4 set 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 chooses 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 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 sets 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 appear in Table 9.4 and Table 9.5. The default value in both cases is 0 (zero).
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. However, if your problem has many columns and relatively few rows, devex pricing is not likely to help much. 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.
Use the scaling parameter (ScaInd, CPX_PARAM_SCAIND) to set scaling appropriate for your model. Table 9.6 summarizes available values for this parameter.
ScaInd Value |
Meaning |
|---|---|
-1 |
no scaling |
0 |
equilibration scaling (default) |
1 |
aggressive scaling |
ILOG CPLEX dynamically decides the frequency at which the basis of a problem is refactored in order to maximize the speed of iterations. On very large problems, ILOG CPLEX refactors the basis matrix infrequently. Very rarely should you consider increasing the number of iterations between refactoring. The refactoring interval is controlled by the ReInv parameter. The default value of 0 (zero) means ILOG CPLEX will decide dynamically; any positive integer specifies the user's chosen factoring 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 parameter sets 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 settings are summarized in Table 9.7.
In the primal simplex optimizer, the CraInd setting sets 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 settings are summarized in Table 9.8.
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.
| Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |