3
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ You can omit the $\le U a_i$. $\endgroup$
    – RobPratt
    Dec 9, 2021 at 4:44

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Your first paragraph is really helpful, the absolute values seem bad for optimization. Just that reformulation of the $x \neq 0$ constraint improves performance by at least an order of magnitude. Could you elaborate on the genetic algorithm? $\endgroup$ Dec 9, 2021 at 14:11
  • $\begingroup$ Assuming you have at least some idea of how GAs work, there's not much to say. The "chromosome" is simply $x$, a vector double-precision values with somewhat arbitrary lower and upper bounds. I generated the $W$ matrix with values in $[-10, 10]$, and I restricted values of $x$ to the same interval, but that was just guesswork. The GA starts with a random population of several hundred $x$ values, using the number of nonnegative components of $Wx$ as the fitness value, and mates and mutates them until a generation limit is hit. $\endgroup$
    – prubin
    Dec 9, 2021 at 16:52
  • $\begingroup$ There is a nice GA library for R, which is what I used, with mostly default parameter settings. If you know R, I'm happy to share the R notebook. $\endgroup$
    – prubin
    Dec 9, 2021 at 16:53
  • $\begingroup$ I adjusted my answer above slightly. First, there was a typo in the domain of $r$. It should be uniform over $[-1,1]$, not $[0,1]$. Second, it's probably good practice in general to normalize $r$. I don't think it's really necessary when the domain is $[-1, 1]$, but in general you want to avoid very large (small) norms for $r$ since they will possibly force $x$ to scale in a way that could conflict with the "big M" (or, here, $U$) constraints. $\endgroup$
    – prubin
    Dec 9, 2021 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.