Simplex parameters

Documents parameters settings that may improve performance of LP optimizers.

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:

Pricing algorithm and gradient parameters

The parameters in Table 1 set the pricing algorithms that 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 CPLEX arrives at an initial feasible solution);
total number of iterations.

CPLEX records those values in the log file as it works. (By default, 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 1 and Table 2. The default value in both cases is 0 (zero).

Table 1. DPriInd parameter settings for dual simplex pricing algorithm
	Description	Concert	Callable Library
`0`	set 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 2. 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 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.

Use the scaling parameter (scale parameter: ScaInd, CPX_PARAM_SCAIND) to set scaling appropriate for your model. Table 3 summarizes available values for this parameter.

Table 3. ScaInd parameter settings for scaling methods
ScaInd Value	Meaning
`-1`	no scaling
`0`	equilibration scaling (default)
`1`	aggressive scaling

Refactoring frequency

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, 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 CPLEX will decide dynamically; any positive integer specifies the user's chosen factoring frequency.

Crash

It is possible to control the way CPLEX builds an initial (crash) basis through the CraInd parameter.

In the dual simplex optimizer, the CraInd parameter sets whether 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 specifies the default starting basis; if its value is 0 (zero) or -1, it specifies an aggressive starting basis. These settings are summarized in Table 4.

Table 4. CraInd parameter settings for the dual simplex optimizer
CraInd Setting	Meaning for Dual Simplex Optimizer
`1`	Use default starting basis guided by coefficients
`0`	Use an aggressive starting basis ignoring coefficients
`-1`	Use an aggressive starting basis contrary to coefficients

In the primal simplex optimizer, the CraInd setting sets how CPLEX uses the coefficients of the objective function to select the starting basis. If its value is 1 (one), CPLEX uses the coefficients to guide its selection; if its value is 0 (zero), CPLEX ignores the coefficients; if its value is -1, CPLEX does the opposite of what the coefficients normally suggest. These settings are summarized in Table 5.

Table 5. 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

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.