# Geometric Presolver example

### From Wikimization

Current revision (16:51, 5 May 2016) (edit) (undo) |
|||

Line 1: | Line 1: | ||

Assume that the following optimization problem is massive: | Assume that the following optimization problem is massive: | ||

<center> | <center> | ||

- | <math>\begin{array}{rl}\mbox{find}&x\in\mathbb{R}^n\\ | + | <math>\begin{array}{rl}\mbox{ find}&x\in\mathbb{R}^n\\ |

\mbox{subject to}&E\,x=t\\ | \mbox{subject to}&E\,x=t\\ | ||

&x\succeq_{}\mathbf{0}\end{array}</math> | &x\succeq_{}\mathbf{0}\end{array}</math> |

## Current revision

Assume that the following optimization problem is massive:

The problem is presumed solvable but not computable by any contemporary means.

The most logical strategy is to somehow make the problem smaller.

Finding a smaller but equivalent problem is called *presolving.*

This Matlab workspace file contains a real matrix having dimension and compatible vector. There exists a cardinality solution . Before attempting to find it, we presume to have no choice but to reduce dimension of the matrix prior to computing a solution.

A lower bound on number of rows of retained is .

A lower bound on number of columns retained is .

An eliminated column means it is evident that the corresponding entry in solution must be .

The present exercise is to determine whether any contemporary presolver can meet this lower bound.