Simplex Parameters

> Continuous Optimization > Solving LPs: Simplex Optimizers > Tuning LP Performance > Simplex Parameters

Simplex Parameters

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 Chapter 9, Solving LPs: Barrier Optimizer). The simplex tuning suggestions appear in the following topics:

Pricing Algorithm and Gradient Parameters

The parameters in Table 8.4 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 chooses the pricing algorithms that are best for most problems. When you are selecting alternate pricing algorithms, look at these values as guides:

overall solution time;
number of Phase I iterations (that is, iterations before ILOG CPLEX arrives at an initial feasible solution);
total number of iterations.

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 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 appear in Table 8.4 and Table 8.5. The default value in both cases is 0 (zero).

Table 8.4 DPriInd Parameter Settings for Dual Simplex Pricing Algorithm
	Description	Concert	Callable Library
`0`	determined automatically	`DPriIndAuto`	`CPX_DPRIIND_AUTO`
`1`	standard dual pricing	`DPriIndFull`	`CPX_DPRIIND_FULL`
`2`	steepest-edge pricing	`DPriIndSteep`	`CPX_DPRIIND_STEEP`
`3`	steepest-edge in slack space	`DPriIndFullSteep`	`CPX_DPRIIND_FULLSTEEP`
`4`	steepest-edge, unit initial norms	`DPriIndSteepQStart`	`CPX_DPRIIND_STEEPQSTART`
`5`	devex pricing	`DPriIndDevex`	`CPX_DPRIIND_DEVEX`

Table 8.5 PPriInd Parameter Settings for Primal Simplex Pricing Algorithm
	Description	Concert	Callable Library
-1	reduced-cost pricing	`PPriIndPartial`	`CPX_PPRIIND_PARTIAL`
0	hybrid reduced-cost and devex	`PPriIndAuto`	`CPX_PPRIIND_AUTO`
1	devex pricing	`PPriIndDevex`	`CPX_PPRIIND_DEVEX`
2	steepest-edge pricing	`PPriIndSteep`	`CPX_PPRIIND_STEEP`
3	steepest-edge, slack initial norms	`PPriIndSteepQStart`	`CPX_PPRIIND_STEEPQSTART`
4	full pricing	`PriIndFull`	`CPX_PPRIIND_FULL`

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

Scaling

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 as in Table 8.6.

Table 8.6 ScaIndParameter Settings for Scaling Methods
ScaInd Value	Meaning
`-1`	no scaling
`0`	equilibration scaling (default)
`1`	aggressive scaling

Refactoring Frequency

ILOG CPLEX dynamically determines 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.

Crash

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 settings are summarized in Table 8.7.

Table 8.7 CraInd Parameter Settings for the Dual Simplex Optimizer
CraInd Setting	Meaning for Dual Simplex Optimizer
`1`	Use default starting basis
`0`	Use an aggressive starting basis
`-1`	Use an aggressive starting basis

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 settings are summarized in Table 8.8.

Table 8.8 CraInd Parameter Settings for the Primal Simplex Optimizer
CraInd Setting	Meaning for Primal Simplex Optimizer
`1`	Use coefficients of objective function to select basis
`0`	Ignore coefficients of objective function
`-1`	Select basis contrary to one indicated by coefficients of objective function

Memory Management and Problem Growth

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.

PREVIOUS NEXT