# Geometric Presolver example

(Difference between revisions)
 Revision as of 16:54, 11 April 2013 (edit)← Previous diff Revision as of 17:15, 11 April 2013 (edit) (undo)Next diff → Line 1: Line 1: - Assume that the following problem is massive: + Assume that the following optimization problem is massive:
- $\begin{array}{rl}\mbox{find}&x\\ + [itex]\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}$ &x\succeq_{}\mathbf{0}\end{array}[/itex]
- The problem is presumed solvable but not computable by any contemporary means. + The problem is presumed solvable but not computable by any contemporary means.
- The most logical strategy is to make the problem smaller. + The most logical strategy is to somehow make the problem smaller.
+ Finding a smaller but equivalent problem is called ''presolving.'' [http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file] [http://www.convexoptimization.com/TOOLS/EAndy.mat This Matlab workspace file] contains a real $E$ matrix having dimension $533\times 2704$ and compatible $t$ vector. There exists a cardinality $36$ binary solution $x$. Before attempting to find it, we presume to have no choice but to reduce dimension of the $E$ matrix prior to computing a solution. contains a real $E$ matrix having dimension $533\times 2704$ and compatible $t$ vector. There exists a cardinality $36$ binary solution $x$. Before attempting to find it, we presume to have no choice but to reduce dimension of the $E$ matrix prior to computing a solution. - A lower bound on the number of rows of $\,E\in\mathbb{R}^{533\times 2704}\,$ retained is $217$.
+ A lower bound on number of rows of $\,E\in\mathbb{R}^{533\times 2704}\,$ retained is $217$.
- A lower bound on the number of columns retained is $1104$. + A lower bound on number of columns retained is $1104$. - The present exercise is to determine those rows and columns using any contemporary presolver. + The present exercise is to determine whether any contemporary presolver can meet this lower bound.

## Revision as of 17:15, 11 April 2013

Assume that the following optimization problem is massive:

$LaTeX: \begin{array}{rl}\mbox{find}&x\in\mathbb{R}^n\\ \mbox{subject to}&E\,x=t\\ &x\succeq_{}\mathbf{0}\end{array}$

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 $LaTeX: E$ matrix having dimension $LaTeX: 533\times 2704$ and compatible $LaTeX: t$ vector. There exists a cardinality $LaTeX: 36$ binary solution $LaTeX: x$. Before attempting to find it, we presume to have no choice but to reduce dimension of the $LaTeX: E$ matrix prior to computing a solution.

A lower bound on number of rows of $LaTeX: \,E\in\mathbb{R}^{533\times 2704}\,$ retained is $LaTeX: 217$.
A lower bound on number of columns retained is $LaTeX: 1104$.

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