search

bqth29 / simulated-bifurcation-algorithm

Python CPU/GPU implementation of the Simulated Bifurcation (SB) algorithm to solve quadratic optimization problems (QUBO, Ising, TSP, optimal asset allocations for a portfolio, etc.).
MIT License
103 stars 25 forks source link

[BUG] MemoryError when creating an instance of IntegerPolynomial for integers with a large number of bits #13

Closed BusyBeaver-42 closed 8 months ago

BusyBeaver-42 commented 1 year ago

Description

Creating an instance of IntegerPolynomial over integers with a large number of bits raises a MemoryError.

The IntegerPolynomial.__init__ creates a list of all accepted values which has size 2**number_of_bits.

Code example

import torch
import simulated_bifurcation as sb

sb.build_model(matrix, input_type="int42")

Traceback

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Users\agero\PycharmProjects\simulated-bifurcation-algorithm\.test_env\.pypi_env_no_gpu\lib\site-packages\simulated_bifurcation\simulated_bifurcation.py", line 823, in build_model
    return IntegerPolynomial(
  File "C:\Users\agero\PycharmProjects\simulated-bifurcation-algorithm\.test_env\.pypi_env_no_gpu\lib\site-packages\simulated_bifurcation\polynomial\integer_polynomial.py", line 60, in __init__
    matrix, vector, constant, [*range(2**number_of_bits)], dtype, device
MemoryError
bqth29 commented 9 months ago

This problem stems from the fact that the list of possible values has to be generated before the polynomial is evaluated, to ensure that the input values actually belong to the polynomial's definition domain.

From version 1.3.0 onwards (the first PR of which is #37), polynomials will no longer have a default definition domain (the domain will only need to be specified when casting the polynomial in an Ising model or when converting SB-optimized spins back to the origin domain). As a result, there will be no need to check the values when evaluating the polynomial, which solves this problem.