[BUG] Algorithm performance dwindles when the number of agents increases

[bqth29]

Considering 6 binary variables $x_1$, $x_2$, $x_3$, $x_4$, $x_5$ and $x_6$, we seek to solve

$$\mbox{Maximize } 2x_1 + 2x_2 + 2x_3 + 2x_4 + 4.5x_5 + 3x_6$$

subjected to the following constraints:

• $x_1 + x_2 \leq 1$
• $x_1 + x_3 \leq 1$
• $x_2 + x_3 + x_4 \leq 1$
• $x_3 + x_4 \leq 1$
• $x_4 + x_5 \leq 1$
• $x_5 + x_6 \leq 1$

Introducing a penalty coefficient $P$, we can write this LP problem as a QUBO problem that we want to maximize:

$$ x_1 + x_2 + x_3 + x_4 - Px_1x_2 - Px_1x_3 - Px_2x_3 - Px_2x_4 - 2Px_3x_4 - Px_4x_5 - Px_5x_6$$

We can chose any value of $P$ as long as one violated constraint results in a negative objective function. Thus, we set $P = 2 + 2 + 2 + 2 + 4.5 + 3 = 15.5$

The optimal situation is met when only $x_1$, $x_4$ and $x_6$ are set to $1$ with an objective function of $7$.

This can be written in terms of PyTorch tensors:

import torch

P = 15.5
Q = torch.tensor(
    [
        [2, -P, -P, 0, 0, 0],
        [0, 2, -P, -P, 0, 0],
        [0, 0, 2, -2 * P, 0, 0],
        [0, 0, 0, 2, -P, 0],
        [0, 0, 0, 0, 4.5, -P],
        [0, 0, 0, 0, 0, 3],
    ]
)

I tried to use the SB algorithm to solve this problem but got an unexpected behavior. The code snippet below allows to reproduce it. In a few words, I used different numbers of agents with 100 runs of the SB algorithm each time and looked at the obtained objective values:

from collections import defaultdict
from simulated_bifurcation.models import QUBO

torch.manual_seed(42) #  Reproducibility
study = {}

for agents in [1, 2, 5, 20, 50, 100]:
    study[agents] = defaultdict(int)
    for _ in range(100):
        _, obj = QUBO(Q).maximize(agents=agents, verbose=False)
        study[agents][obj] += 1

Plotting the study's data as pie charts for a more understandable visualization, I got:

We can clearly see that the optimal value is getting more and more rare as the number of agents increases which is counter-intuitive since using more agents should result in an objective function at least as good as what we get with fewer agents. In the same time, as the number of agents increases, the bad values get more and more frequent.