PreSolve
Purpose
Simplify the structure of the constraints and the variable bounds in a linear constrained program.
Calling Syntax
Prob = preSolve(Prob)
Inputs
Input | Description | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Prob | Problem description structure. The following fields are used:
|
Outputs
Output | Description | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Prob | Problem description structure. The following fields are changed:
|
Description
The routine preSolve is an implementation of those presolve analysis techniques described by Gondzio, which is applicable to general linear constrained problems.
preSolve consists of the two routines clean and mksp. They are called in the sequence clean, mksp, clean. The second call to clean is skipped if the mksp routine could not remove a single nonzero entry from A.
clean consists of two routines, r_rw_sng that removes singleton rows and el_cnsts that improves variable bounds and uses them to eliminate redundant and forcing constraints. Both r_rw_sng and el_cnsts check if empty rows appear and eliminate them if so. That is handled by the routine emptyrow. In clean the calls to r_rw_sng and el_cnsts are repeated (in given order) until no further reduction is obtained.
Note that rows are actually not deleted or removed, instead preSolve indicates that constraint i is redundant by setting b_L(i) = b_U(i) = NaN and leaves to the calling routine to decide what to do with those constraints.