PreSolve

From TomWiki
Revision as of 10:55, 22 July 2011 by Elias (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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:
A Constraint matrix for linear constraints.
b_L Lower bounds on the linear constraints.
b_U Upper bounds on the linear constraints.
x_L Lower bounds on the variables.
x_U Upper bounds on the variables.

Outputs

Output Description
Prob Problem description structure. The following fields are changed:
A Constraint matrix for linear constraints.
b_L Lower bounds on the linear constraints, set to NaN for redundant constraints.
b_U Upper bounds on the linear constraints, set to NaN for redundant constraints.
x_L Lower bounds on the variables.
x_U Upper bounds on the variables.

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.