How do CPLEX's different linear programming algorithms make use of advanced start information after a problem modification?
Optimization practitioners sometimes wish to use the solution or basis from a previously solved linear program (LP) as an advanced start for a related model obtained by modifying the previous LP. The nature of the modification determines whether LP remains primal or dual feasible. This in turn influences the most suitable choice of algorithm for the optimization.
As of this writing, the barrier method used by commercial optimizers lacks any restart capability after a problem modification. The barrier method always starts the optimization from scratch after a problem modification, regardless of the nature of the change. Therefore, one usually will use the primal or dual simplex method when solving a modified problem. However, the barrier method may still offer superior performance if either the problem modifications compromise both primal and dual feasibility, or the barrier method solves the LPs in question much faster than either simplex method.
In contrast to the barrier and other interior point methods, the basis with which the simplex algorithm operates is well suited for advanced starts. Such advance starts are frequently used when solving related subproblems in an iterative technique in which new variables and/or constraints have been inserted. For the case in which the practitioner is interested in multiple, similar solves, the choice of the primal or the dual simplex method is influenced by how the modifications that generate the sequence of instances preserve primal or dual feasibility. For example, adding columns to a primal feasible solution of a LP maintains primal feasibility, but typically compromises dual feasibility. One can set the variables associated with the newly added columns to zero (except for the relatively uncommon case where the added columns have positive lower bounds or negative upper bounds) and append those values to those of the existing primal feasible solution. Therefore, after adding columns, the primal simplex method has an advantage over the dual simplex method because the optimal basis from the previous LP remains primal feasible, but not typically dual feasible. If the added column to the primal appears as a redundant constraint in the dual, then dual feasibility is preserved as well. But, such redundant constraints are uncommon in most practical uses of adding columns (e.g. column generation). Similarly, adding rows to an LP with a dual feasible solution (which is equivalent to adding columns to the dual LP) preserves dual feasibility but typically compromises primal feasibility, so the dual simplex method has an advantage over the primal simplex method. Analogous to adding columns, primal feasibility is preserved as well if the additional row is redundant relative to the primal constraints. Similarly, one can examine all the different types of problem modifications to an LP and determine whether the modification preserves primal or dual feasibility. The table below summarizes the different types of modifications to the primal LP, and whether they ensure preservation of primal or dual feasibility. Note that the preservation of primal feasibility for a row of the table does not imply the absence of dual feasibility for the given problem modification (or vice versa). For example, relaxing a variable bound ensures that primal feasibility is preserved, but it does not guarantee that dual feasibility is compromised. Specifically, if the associated variable is basic, or nonbasic with a reduced cost of 0, dual feasibility will be preserved as well.
|Problem modification||Primal or dual feasibility preserved?|
|Add columns||Primal feasibility|
|Add rows||Dual feasibility|
|Tighten variable bounds||Dual feasibility|
|Relax variable bounds||Primal feasibility|
|Change objective function coefficients; tighter dual||Primal feasibility|
|Change objective function coefficients; relaxed dual||Primal and dual feasibility|
|Change right-hand-side coefficients; tighter primal||Dual feasibility|
|Change right-hand-side coefficients; relaxed primal||Primal and dual feasibility|
|Change matrix coefficients of basic variables||Neither|
|Change matrix coefficients of nonbasic variables at value 0||Primal feasibility|