3
$\begingroup$

I have 10000 variables (each of them is binary), vector of positive coefficients and a matrix $A$ ($10000\times10000$), if $A_{ij}=1$, then $i$th and $j$th variables can take 1 simultaneously, if it is 0, then it is not possible. The goal is to maximize their weighted sum. What algorithms and software could I use to solve this problem?

\begin{array}{l} \max F\left( x_{1}..x_{m} \right)=\sum\limits_{i=1}^m {b_{i}x_{i}} \end{array}

\begin{array}{l} x_{i}\in \left\{ 0,1 \right\},\, \, i=1..m \\ x_{i}x_{j}\le A_{ij}\,, i,j=1..m \\ A_{ij}\in \left\{ 0,1 \right\},\, \, i,j=1..m \\ \end{array}

$\endgroup$
  • 1
    $\begingroup$ Do we know $A$ is symmetric? Are its diagonal entries all 1's? $\endgroup$ – hardmath Apr 23 '14 at 13:04
  • 1
    $\begingroup$ @hardmath Yes, it is symmetric, and all diagonal entries are 1's. $\endgroup$ – Evgenii Nikitin Apr 23 '14 at 16:18
  • 1
    $\begingroup$ Known in the literature as maximum weight clique problems, these are NP-hard as a general class. Your problem size seems daunting if an exact solution is needed, but studies have proceeded along lines of faster exact solutions of smaller problems and better approximate solutions with larger problems. $\endgroup$ – hardmath Apr 23 '14 at 16:48
  • 1
    $\begingroup$ @hardmath Thanks for the reference, I briefly read about max weight clique problem formulation, but I'm not sure that it's my case. I guess, I have, well, weighted nodes, not edges. I formulated my problem above. $\endgroup$ – Evgenii Nikitin Apr 23 '14 at 17:18
  • 1
    $\begingroup$ Look for papers by Patrick Ostergard, from 2000-2002. He considers problems with positive integer weights on the vertices (nodes). $\endgroup$ – hardmath Apr 23 '14 at 18:06
1
$\begingroup$

The following answer from before the edit interpreted the words "not possible" as "not possible to take 1". If we read it as "not possible to both take 1", then this answer does not apply.

If I'm reading the question correctly, it seems to me this problem is far easier than maximum weight clique problems. It appears to be $O(m^2)$. The given coefficients $b_i$ are all positive, so it is apparent that the maximum weighted sum for a given set of coefficients would be where $x_i$ were all 1. So we want them to be 1 unless they cannot be. Therefore, initialize all $x_i$ to 1, iterate over all $m^2$ elements of $A_{ij}$, and if those matrix elements are 0, set the corresponding $x_i$ and $x_j$ to 0. Then we have all the 1's in the vector $x$ that we are allowed to have by the matrix, and the weighted sum is maximized.

$\endgroup$
  • $\begingroup$ That sounds too simplistic. What if the first node in the graph, $x_1$, disallows all other nodes? Then by this simple greedy algorithm, we'd keep only $x_1$ on, while instead having $\{x_2, \ldots, x_m\}$ on might be much better. $\endgroup$ – cfh Mar 24 '15 at 11:51
  • $\begingroup$ Your comment doesn't quite match my answer, but upon rereading I see why you have concluded this while I did not. I edited my answer with a restriction on how I interpreted the question. $\endgroup$ – Ryan Colyer Mar 26 '15 at 20:42
0
$\begingroup$

The best idea is to use an algorithm tailored to your particular optimization problem structure.

Without using any specialized algorithms tailored to this problem, you have an MINLP, and there's no really good way of solving general large MINLPs; "large" at the time of this writing is probably somewhere in the hundreds or thousands.

There is some work by Glover on reformulating these problems to MILPs; the basic idea is to note that for $x_{i}, x_{j} \in \{0, 1\}$, some valid inequalities hold, like

\begin{align} x_{i}x_{j} &\geq x_{i} + x_{j} - 1 \\ x_{i} &\geq x_{i}x_{j} \\ x_{j} &\geq x_{i}x_{j} \end{align}

You add those inequalities and replace $x_{i}x_{j}$ with the variable $z_{ij} \in \{0, 1\}$. However, such a reformulation greatly increases the number of binary variables in your problem, so I doubt it's a viable option. Other versions of this idea vary in the size of the reformulation, but the order of magnitude of the sizes of each reformulation is more or less the same.

$\endgroup$
  • $\begingroup$ Sorry for the stupid question, but why is this problem nonlinear? I can reformulate constraints like xi+xj<=Aij because Aij can be either 0 or 1. And about the problem - if it's any good, it's a sceduling problem, I have 17 time slots, each of them can be filled by different numbers of alternatives. Each variable represents one alternative for one slot. So, all alternatives for one slot are mutually exclusive and some alternatives for different slots are incompatible. And their "compatibility" is modelled by these Aij parameters $\endgroup$ – Evgenii Nikitin Apr 24 '14 at 20:46
  • $\begingroup$ The $x_{i}x_{j}$ terms are nonlinear. If you can reformulate the problem to be linear without using the techniques from Glover, great. $x_{i}x_{j} \neq x_{i} + x_{j}$ for binary variables, in case that matters. $\endgroup$ – Geoff Oxberry Apr 24 '14 at 20:55
  • $\begingroup$ Well, for me it doesn't. I am interested only if they are both 1s. I tried to implement maximum weight clique algorithms as discussed above, but they work too slow for my problem. $\endgroup$ – Evgenii Nikitin Apr 25 '14 at 6:28
  • 1
    $\begingroup$ xi + xj <= Aij + 1 is equivalent to xi.xj <= Aij for binary x and A right? $\endgroup$ – jf328 Jan 20 '15 at 9:30
  • $\begingroup$ @jf328: Yes, those two inequalities are equivalent for all 8 cases of binary $x_{i}, x_{j}, A_{ij}$. $\endgroup$ – Geoff Oxberry Jan 20 '15 at 23:15

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.