0.99 is equivalent to x = 0, if x is known to be a nonnegative integer variable.This chapter describes performance-tuning subroutines and general performance considerations. The sections of this chapter are:
For most problems, EKKCRSH will give a good starting basis; EKKPRSL will reduce the size of the matrix; EKKSCAL will reduce numerical instabilities; and EKKLPDC can find an advanced basis for problems with special structures. Each of these subroutines usually improves performance.
For most mathematical programming problems, you will have to solve the problem in a production mode. That is, you will be solving the same, or a very similar problem, over and over again. In this kind of situation you can experiment with the performance tuners. Try them for your application and choose the approach that gives the best performance.
|
Note: |
The performance tuners are not applicable for use with the network solver EKKNSLV. Also, some of the subroutines are not applicable to some of the other solvers. See the individual descriptions below for details. |
|
Note: |
EKKCRSH should not be used in conjunction with EKKBSLV or EKKQSLV. |
EKKCRSH starts from a basis of all logical variables. From that, it tries to create a good basis by inserting structural variables. To facilitate computation, the basis is kept triangular. This makes EKKCRSH very fast. It tends to insert column or row singletons first and then doubletons, and so on.
However, this may not be the best procedure because there are cases where EKKCRSH finds a feasible basis immediately, but creates an enormous objective function. In such cases, calling EKKSSLV with the init argument set to 1 or 2 might improve performance by an order of magnitude.
To avoid this, you can use the dual option of EKKCRSH. If pivots are made only for variables with zero costs and the problem is dual feasible, then it will remain dual feasible (starting from an all logical basis). This tends to put fewer structural variables in the basis, but has less potential for harm.
EKKPRSL can make a dramatic difference in performance. If the number of rows and columns is reduced by more than 5%, it is probably worth using.
There are various things that EKKPRSL can do to reduce the size of the problem based on the calling parameter, type.
EKKPRSL tries variables it can. This is only done, if there is a clear advantage, since primal degeneracy might be increased. For example, if all entries in a row are 1.0 (and all lower bounds are 0.0), then that row's smallest contribution is zero. Further, if the upper bound on the row activity is also zero, then all variables with entries in that row are fixed at zero. If just one variable in a row is not fixed, then EKKPRSL uses the row to impose an implicit upper or lower bound on the variable and then eliminates the row.
The type=1 and type=2 reductions have the greatest benefit on an IBM Vector Facility, where the increased density gives significant improvement with vectorization.
After solving the reduced problem, EKKPSSL recomputes all the values for variables that were removed and reconstructs a basis. After EKKPSSL, the values of the variables provide an optimal solution, but not a basic optimal solution. To get a basic optimal solution, call EKKSSLV with init set to 3.
CALL EKKSSLV(RTCOD,DSPACE,1,3)
EKKPSSL restores the original bounds, while EKKMSLV will return with bounds that give the optimal integer solution. To use EKKPSSL in conjunction with EKKMSLV, you should save the values of all integer variables and, after EKKPSSL but before EKKSSLV, set both the lower and upper bounds on integer variables to these values. Refer to "Sample FORTRAN Program EXMPRSL" for an example of how to do this.
Also note that not all variables are eligible for type 1 or 2 presolve when there are integer variables, since integer variables may not be eliminated by these tests. Also, it is possible for presolve to declare the problem infeasible when integer variables have been activated. For example, x 0.99 is equivalent to x = 0, if x is known to be a nonnegative integer variable.
|
Note: |
EKKSCAL should usually be used with the primal-dual barrier options of EKKBSLV. |
EKKSCAL can be used to scale the coefficients of the constraint matrix so as to reduce their numerical spread, in the hope of increasing the numerical stability of the computations to follow.
Scaling is very important, and can be very effective in improving numerical stability. You should realize, however, that you the user are probably in a better position to scale the problem than any computer algorithm. The way to do this is: first choose appropriately scaled units for the extensive variables of the problem, e.g., kilo-tons instead of pounds, tankcar loads instead of gallons, millions of dollars instead of pennies, or nanometers instead of feet, so that the numerical spread of the coefficients in each single constraint, and in the objective function, will be at most one or two orders of magnitude; and then second scale the constraints themselves, by multiplying each entire constraint relation by an appropriate positive constant, so that the numerical spread of the coefficients in the different constraints is at most another one or two orders of magnitude. The scaling algorithm implemented in EKKSCAL is intended to approximate this, in its attempt to minimize the numerical spread of the matrix coefficients, but of course, it knows nothing about choosing appropriate units for the extensive variables. EKKSCAL does the following:
|
Note: |
Free rows and fixed variables are ignored in these computations. |
Scaling helps on many problems. On some problems, however, it will not help. For example, if half the columns contain only a 1.0 on a row with a cost, then this relationship might be disturbed by scaling.
EKKSCAL computes scaling factors to be applied to the bounds and costs arrays internally and actually scales the matrix elements, creating a matrix stored by columns that replaces the existing one.
Scale factors are applied to each matrix element ai j as follows:
scaled ai j = (original ai j * rowscale i ) / colscale j
Upon entry to EKKSSLV, EKKBSLV, EKKQSLV, EKKQPAR, or EKKSPAR, the upper bounds, lower bounds, and solution arrays are multiplied by the scale factors. The costs and reduced costs are also divided by the scale factors. This process is reversed when exiting the solve routine.
EKKLPDC is a high-level crash procedure that takes advantage of the special structure of certain problems. It should be followed by EKKSSLV. Two common problem classes are addressed by EKKLPDC: Dantzig-Wolfe and staircase. You must decide which of these structures is best suited to your problem when using EKKLPDC.
Problems with a block diagonal structure and coupling rows (or side constraints) are referred to here as Dantzig-Wolfe problems. These problems have a structure similar to the one in the constraint system shown below, in which matrix blocks containing nonzeros are indicated by an "X." Typically, there is a set of disjoint blocks coupled together by a few coupling rows grouped together either at the top of the system or at the bottom.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX = X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX = X XXXXXXXX = X XXXXXXXX = X XXXXXXXXXXXXX = X XXXXXXXXXXXXX = X XXXXXXXXXXXXX = X XXXXXXXXXXXXXXX = X XXXXXXXXXXXXXXX = X
Staircase-structured problems have a structure similar to the one in the constraint system shown below. As before, matrix blocks containing nonzeros are indicated by an "X." Between each pair of adjacent blocks, there are typically a few coupling columns that belong to both blocks. These problems are often called multiperiod problems, because each major block corresponds to a time period such as a month or a year.
XXXXXXXX = X XXXXXXXX = X XXXXXXXX = X XXXXXXXXXX = X XXXXXXXXXX = X XXXXXXXXXX = X XXXXXXXXXXXXX = X XXXXXXXXXXXXX = X XXXXXXXXXXXXX = X
A problem with either Dantzig-Wolfe or staircase structure can be stored in dspace using either EKKLMDL or EKKMPS. After the problem date is in dspace, you can either specify the structure of your problem to EKKLPDC, or allow EKKLPDC to find the structure of your problem automatically. In other words, you need to do one of the following:
Note that it may be very time-consuming for EKKLPDC to identify the block structure. It is usually much more efficient to identify a block structure in the application program. Having EKKLPDC automatically identify blocks should only be done when the structure is unknown, and multiple variations of the problem will be run; the blocks that EKKLPDC finds on the first run can be identified specifically on subsequent runs.
The crash techniques in EKKLPDC solve a collection of sub-problems using the previously identified blocks as the constraint systems. Two of the crash techniques (types 1 and 2) involve just one pass through the blocks and can be used for Dantzig-Wolfe or staircase problems. Each block is used just once, and the solutions from the subproblems are combined to yield an advanced basis for EKKSSLV. The remaining technique (type 3) is used only for Dantzig-Wolfe problems. This technique performs the number of Dantzig-Wolfe decomposition iterations that you specify with the integer control variable Imajorits. See Chvatal and Dantzig for additional information. Specifically, the crash techniques in EKKLPDC are:
If strategy=0, the columns are marked to indicate their block on exit. No solving is done, if strategy=0.
If strategy=1, each subproblem is solved with the neighboring coupling columns free.
If strategy=2, each subproblem is solved with the columns coupling it to the previous subproblem free, and the columns coupling it to the next subproblem fixed at lower bound.
If strategy=3, the first subproblem consists of the first block. The constraint matrix for the kth subproblem consists of the first k blocks. The solution to the kth problem is used as an advanced start for the (k+1)th problem.
If strategy=0, EKKLPDC determines if the problem can be decomposed into a Dantzig-Wolfe structure. If it can be, the columns are marked to indicate their block on exit. No solving is done, if strategy=0.
If strategy=1, the subproblems are solved giving a dual feasible solution to the problem. After using EKKLPDC with this option, it is recommended that EKKSSLV be called with the dual algorithm option.
If strategy=2, the right-hand side for the coupling rows is partitioned, and blocks of the coupling constraints are added to the subproblems. This helps to find a feasible starting solution for EKKSSLV.
If strategy=3, an approach similar to when strategy=2 is taken, except that EKKLPDC puts every second block together until no blocks remain to be added to the problem.
If strategy=0, EKKLPDC determines if the problem can be decomposed into a Dantzig-Wolfe structure. If it can be, the rows and columns are marked to indicate their block on exit. No solving is done, if strategy=0.
If strategy=1, EKKLPDC performs the number of Dantzig-Wolfe decomposition passes specified by the integer control variable Imajorits. The master rows are ignored for the initial solution.
If strategy=2, EKKLPDC performs the number of Dantzig-Wolfe decomposition passes specified by the integer control variable Imajorits. The master rows are included for the initial solution. EKKLPDC partitions the RHS of the master problem and gives some portion of it to each subproblem.
If strategy=3, EKKLPDC performs the number of Dantzig-Wolfe decomposition passes specified by the integer control variable Imajorits. The current solution in dspace is used as the initial solution. This solution may have been created by EKKSSLV, EKKNSLV, or EKKBSLV. Notes:
When solving mathematical programming problems, in the absence of any specific instructions, the library modules are designed to do what is most likely to yield the best performance on a broad class of problems. You can alter the default strategies in many ways. At the highest level, you can select which subroutines to call, such as whether to use EKKSSLV or EKKBSLV or whether to call EKKCRSH. The next level of control is determining what parameters are passed to the subroutine, for example, whether EKKSSLV should use primal or dual or what level of work should be attempted by EKKPRSL. General information is given in the descriptions of the specific subroutines and in the following chapters:
Another level of control is exerted with the control variables. Again, the default values are designed to give good performance on a broad range of problems. Knowledge of the particular characteristics of your problem may allow you to adjust these control variables to improve performance on your problem. In "Strategies for Solving Mathematical Programming Problems", the description of each solver is followed by a list and description of the key control variables that affect it. By experimenting with these, you may find settings that reduce the time needed to solve your problem.
Lastly, the library solvers provide user exits-points where your program can take a variety of actions, particularly for mixed-integer problems. For example, the application program can change the choice of branching variable or means of evaluating a node. The mechanics of using these user exits are described in the individual user exit descriptions and in "Understanding Informational User Exit Subroutines" and "Understanding Mixed-Integer User Exit Subroutines".
Following are some tips that may be helpful when trying to get the best performance.
Remember that units 100-109 are not standard FORTRAN units, so you will not be able to open or close these units with FORTRAN statements or with EKKFOPN and EKKFCLS. If needed, you are responsible for closing these files after they have been read.
[ Top of Page | Previous Page | Next Page | Table of Contents ]