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}

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Do we know $A$ is symmetric? Are its diagonal entries all 1's? $\endgroup$
    – hardmath ♦
    Apr 23, 2014 at 13:04
  • 1
    $\begingroup$ @hardmath Yes, it is symmetric, and all diagonal entries are 1's. $\endgroup$
    – Evgenii Nikitin
    Apr 23, 2014 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, 2014 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, 2014 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, 2014 at 18:06

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 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.

Improve this answer
$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2014 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, 2015 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, 2015 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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