Back to SYMPHONY Home Page
The majority of the computational effort of branch and cut is spent solving LPs and hence a major emphasis in the development was to make this process as efficient as possible. Besides using a good LP engine, the primary way in which this is done is by controlling the size of each relaxation, both in terms of number of active variables and number of active constraints. The standard column-ordered format is used for storage of the matrix since this is the format used by most LP engines. With sparse matrices, this format provides the most efficient storage of the matrix.
The number of constraints is controlled through use of a local cut pool and through purging of ineffective constraints. When a cut is generated by the cut generator, it is first sent to the local cut pool. In each iteration, up to a specified number of the strongest cuts (measured by degree of violation) from the local pool are added to the problem. Cuts that are not strong enough to be added to the relaxation are eventually purged from the list. In addition, cuts are purged from the LP itself when they have been deemed ineffective for more than a specified number of iterations, where ineffective is defined as either (1) the corresponding slack variable is positive, (2) the corresponding slack variable is basic, or (3) the dual value corresponding to the row is zero. Cuts that have remained effective in the LP for a specified number of iterations are sent to the global pool where they can be used in later search nodes. Cuts that have been purged from the LP can be made made active again if they later become violated.
The number of variables (columns) in the relaxation is controlled through reduced cost fixing and dynamic column generation. Periodically, each active variable is priced to see if it can be fixed by reduced cost. If the matrix is full at the time of the fixing, meaning that all unfixed variables are active, then the fixing is permanent for that subtree. Otherwise, it is temporary and only remains in force until the next time that columns are dynamically generated.
Dynamic column generation is costly and hence takes place only either
(1) before branching (optional), or (2) when a node is about to be
pruned (depending on the phase--see the description of the two-phase
algorithm in Section 5.3.2). To use dynamic column
generation, the user must supply a subroutine which generates the
column corresponding to a particular user index, given the list of
active constraints in the current relaxation. When column generation
occurs, each column not currently active that has not been previously
priced out is either priced out immediately, or becomes active in the
current relaxation. Only 
columns may enter the problem at a
time, so when that limit is reached, column generation ceases. Further
discussion of column generation will take place in Section 5.3.2,
where the two-phase algorithm is described.
Since the matrix is stored in compressed form, it can be expensive to add and remove rows and columns. Hence, rows and columns are only physically removed from the problem when there are enough of them to make it ``worthwhile.'' Otherwise, deleted rows and columns remain in the matrix but are simply ignored by the computation. This is a convenient way to handle row deletion since rows are expensive to delete from a column-ordered matrix and they tend to move in and out more frequently.