Presolver
From Wikimization
(→Geometry of Constraints) |
(→Geometry of Constraints) |
||
Line 53: | Line 53: | ||
Those four columns completely describe the Pyramid by definition of <math>\mathcal{K}\,</math>. | Those four columns completely describe the Pyramid by definition of <math>\mathcal{K}\,</math>. | ||
But <math>\,A</math> can have more than four columns and still describe that same Pyramid. | But <math>\,A</math> can have more than four columns and still describe that same Pyramid. | ||
- | + | For such an <math>A\,</math>, each remaining column resides interior to the cone | |
or on one of its ''faces'' (the vertex, an edge, or facet). | or on one of its ''faces'' (the vertex, an edge, or facet). | ||
We give the name ''generators'' to any set of columns from <math>\,A</math> | We give the name ''generators'' to any set of columns from <math>\,A</math> | ||
that constructs <math>\mathcal{K}\,</math> per its definition. | that constructs <math>\mathcal{K}\,</math> per its definition. | ||
- | There is an infinite variety of polyhedral | + | There is an infinite variety of polyhedral cone that are not necessarily so regular as a Pyramid. |
A polyhedral cone can have any number of edges, facets, and higher-order faces. | A polyhedral cone can have any number of edges, facets, and higher-order faces. | ||
Throughout we assume a pointed polyhedral cone, so there can only be one vertex. | Throughout we assume a pointed polyhedral cone, so there can only be one vertex. | ||
By definition, that vertex resides at the origin in Euclidean space. | By definition, that vertex resides at the origin in Euclidean space. |
Revision as of 20:39, 9 August 2011
Introduction
Presolving conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem. Presented with constraints for example, a presolver is likely to check whether constant vector is positive; for if so, variable can have only the trivial solution. The effect of such tests is to reduce the problem dimensions.
Most commercial optimization problem solvers incorporate presolving. Particular reductions can be proprietary or invisible, while some control or selection may be given to a user. But all presolvers have the same motivation: to make an optimization problem smaller and (ideally) easier to solve. There is profit potential because a solver can then compete more effectively in the marketplace for large-scale problems.
We present a method for reducing variable dimension based upon geometry of constraints in the problem statement:
where is a matrix of predetermined dimension, represents the integers, the real numbers, and is some possibly empty index set.
The caveat to use of our proposed method for presolving is that it is not fast. One would incorporate this method only when a problem is too big to be solved; that is, when solver software chronically exits with error or hangs.
Geometry of Constraints
The idea, central to our method for presolving, is more easily understood geometrically. Constraints
suggest that a polyhedral cone comes into play. Geometers in convex analysis regard cones as convex Euclidean bodies semi-infinite in extent. Finite circular cones hold ice cream and block road traffic in daily life. The great Pyramids of Egypt are each an example of finite polyhedral cone. The geometer defines a polyhedral (semi-infinite) cone in as the set:
which is closed and convex but not necessarily pointed (does not necessarily have a vertex).
To visualize a pointed polyhedral cone in three dimensions, think of one Egyptian Pyramid continuing into the ground and then out into space from the opposite side of Earth. Its four edges correspond to four columns from matrix . Those four columns completely describe the Pyramid by definition of . But can have more than four columns and still describe that same Pyramid. For such an , each remaining column resides interior to the cone or on one of its faces (the vertex, an edge, or facet). We give the name generators to any set of columns from that constructs per its definition.
There is an infinite variety of polyhedral cone that are not necessarily so regular as a Pyramid. A polyhedral cone can have any number of edges, facets, and higher-order faces. Throughout we assume a pointed polyhedral cone, so there can only be one vertex. By definition, that vertex resides at the origin in Euclidean space.