Geometric Presolver example

From Wikimization

Revision as of 14:06, 12 April 2013 by Dattorro (Talk | contribs)
Jump to: navigation, search

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\\

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.
An eliminated column means it is evident that the corresponding entry in solution LaTeX: x must be LaTeX: 0.

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

Personal tools