Presolver

(Difference between revisions)
 Revision as of 01:30, 10 August 2011 (edit) (→Geometry of Constraints)← Previous diff Revision as of 19:26, 10 August 2011 (edit) (undo)m (→Geometry of Constraints)Next diff → Line 31: Line 31: ==Geometry of Constraints== ==Geometry of Constraints== [[Image:pyramid.jpg|thumb|right|234px|Euclidean pyramid]] [[Image:pyramid.jpg|thumb|right|234px|Euclidean pyramid]] - The idea, central to our method for presolving, is more easily understood geometrically. + The central idea in our presolving method is best understood geometrically. Constraints Constraints
$[itex] Line 42: Line 42: Geometers in ''convex analysis'' regard cones as convex Euclidean bodies semi-infinite in extent. 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. 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. + Each of the great Pyramids of Egypt is a finite polyhedral cone. - The geometer defines a polyhedral (semi-infinite) cone [itex]\,\mathcal{K}$ in $\,\reals^m$ as the set: + The geometer defines a polyhedral (semi-infinite) cone $\,\mathcal{K}$ in $\,\reals^m$ as a set
$\mathcal{K}\triangleq\{A_{}x~|~x\succeq0\}$
$\mathcal{K}\triangleq\{A_{}x~|~x\succeq0\}$
- which is closed and convex but not necessarily pointed (does not necessarily have a vertex). + that is closed and convex but not necessarily pointed (may not have a vertex). [[Image:Polycone2.jpg|thumb|right|200px|A pointed polyhedral cone (truncated)]] [[Image:Polycone2.jpg|thumb|right|200px|A pointed polyhedral cone (truncated)]] Line 51: Line 51: and then indefinitely out into space from the opposite side of Earth. and then indefinitely out into space from the opposite side of Earth. Its four edges correspond to four columns from matrix $A\,$. Its four edges correspond to four columns from matrix $A\,$. - In fact, those four columns completely describe this semi-infinite Pyramid per definition of $\mathcal{K}\,$. + Those four columns completely describe the semi-infinite Pyramid per definition of $\mathcal{K}\,$. - But $A\,$ can have more than four columns and still describe that same Pyramid. + But $A\,$ can have more than four columns and still describe the same Pyramid. - For such a fat $A\,$, each remaining column resides anywhere in $\mathcal{K}\,$: + For such a fat $A\,$, each additional column resides anywhere in $\mathcal{K}\,$: - interior to the cone $(\{A_{}x~|~x\succ0\})$ or on one of its ''faces'' (the vertex, an edge, or facet). + either interior to the cone $(\{A_{}x~|~x\succ0\})$ or on one of its ''faces'' (the vertex, an edge, or facet). - There is infinite variety of polyhedral cones; most are not so regularly shaped as a Pyramid. + Polyhedral cones have infinite variety. Most are not so regularly shaped as a Pyramid, - In fact, a polyhedral cone can have any number of edges and facets. + and they can have any number of edges and facets. We assume a pointed polyhedral cone throughout, so there can be only one vertex We assume a pointed polyhedral cone throughout, so there can be only one vertex - which resides at the origin in Euclidean space by definition. + (which resides at the origin in Euclidean space by definition).

Introduction

Presolving conventionally means quick elimination of some variables and constraints prior to numerical solution of an optimization problem. Presented with constraints $LaTeX: a^{\rm T}x=0\,,~x\succeq0$ for example, a presolver is likely to check whether constant vector $LaTeX: a\,$ is positive; for if so, variable $LaTeX: \,x$ 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: $LaTeX:
\begin{array}{rl} \mbox{minimize}_{x\in_{}\mathbb{R}^{^n}} & f(x) \\ \mbox{subject to} & A_{}x=b \\ & x\succeq0 \\ & x_{j\!}\in\mathbb{Z}~,\qquad j\in\mathcal{J} \end{array}
$

where $LaTeX: A\,$ is a matrix of predetermined dimension, $LaTeX: \mathbb{Z}$ represents the integers, $LaTeX: \reals$ the real numbers, and $LaTeX: \mathcal{J}$ 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 central idea in our presolving method is best understood geometrically. Constraints $LaTeX:
\begin{array}{l} \\ A_{}x=b \\ x\succeq0 \end{array}
$

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. Each of the great Pyramids of Egypt is a finite polyhedral cone. The geometer defines a polyhedral (semi-infinite) cone $LaTeX: \,\mathcal{K}$ in $LaTeX: \,\reals^m$ as a set $LaTeX: \mathcal{K}\triangleq\{A_{}x~|~x\succeq0\}$

that is closed and convex but not necessarily pointed (may not have a vertex).

To visualize a pointed polyhedral cone in three dimensions, think of one Egyptian Pyramid continuing into the ground and then indefinitely out into space from the opposite side of Earth. Its four edges correspond to four columns from matrix $LaTeX: A\,$. Those four columns completely describe the semi-infinite Pyramid per definition of $LaTeX: \mathcal{K}\,$. But $LaTeX: A\,$ can have more than four columns and still describe the same Pyramid. For such a fat $LaTeX: A\,$, each additional column resides anywhere in $LaTeX: \mathcal{K}\,$: either interior to the cone $LaTeX: (\{A_{}x~|~x\succ0\})$ or on one of its faces (the vertex, an edge, or facet).

Polyhedral cones have infinite variety. Most are not so regularly shaped as a Pyramid, and they can have any number of edges and facets. We assume a pointed polyhedral cone throughout, so there can be only one vertex (which resides at the origin in Euclidean space by definition).