Maximizing the number of nonnegative coordinates of $Wx$

Question

I want to find good incumbent solutions to the following problem: $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\norm}[1]{\left\Vert#1\right\Vert}$

Given a matrix $W \in \RR^{m \times n}$, find the maximum number of nonnegative coordinates of $Wx$, over $x \in \RR^n \backslash \{0\}$.

The following linear formulation solves it, however it's not efficient:

\begin{align} \max_{x \in \RR^n, a \in \RR^m} \quad & \sum_{i=1}^m a_i \\ \text{subject to} \quad & \norm{x}_1 = n \\ & -U(1 - a_i) \le w_i^T x \le Ua_i ~\text{for } 1 \le i \le m \\ & a_i \in \{0, 1\} \end{align}

Here $U$ is a large enough scalar, say $U = n\norm{W}_1$.

I would like to run it on matrices with $m = 700$ and $n = 100$.

Answer 1

First, a comment on the MIP model. I assume that the constraint $\|x\|_1 = n$ is intended to eliminate $x=0$ as a solution. An alternative that works with probability 1 is to generate a random vector $r\in \mathbb{R}^n$ from a continuous distribution, say uniform over $[-1,1]^n$, normalize it so that $\|r\|_2=1$, and use the normalization constraint $r^\prime x = 1$. This works unless the optimal $x$ is orthogonal to $r$, which has probability 0 of occurring given that the distribution of $r$ is uniform over a region with positive volume. The reason I suggest this is that eliminates any binary variables added (either by you or the solver) to deal with absolute values.

As far as generating a "good" incumbent, you can apply a number of different metaheuristics. I tried a genetic algorithm (coded in R) on a randomly generated matrix $W$. The GA converges in under a minute on my PC using your dimensions (700 x 100), but to compare it to the optimal solution (computed using CPLEX) I scaled the matrix down to 70 x 10. (I tried 700 x 100, but CPLEX did not look as if it was going to terminate in what was an acceptable time for me.) My first trial at 70 x 10 produced an optimal solution with 54 nonzeros versus a GA solution with 51. A retry with a different random number seed yielded an optimum of 59 nonzeros and a GA solution with 57.