A small library of functions with few dependencies to run k rounds of Sherali-Adams relaxation on a system of the form Ax <= b represented by raw numpy matrix A and array b.
The constraints 0 <= y <= 1 will be added for all variables in the system returned. Send me a note if you'd like for this to be optional.
For a small instances (~7 variables) I recommend the default mode, for larger use memoized = True (it will be faster but use more memory).
pip install sherali_adams
> nosetests
Ran 5 tests in 0.423s
OK
- Run 1 round of SA on a system with 2 variables.
A = np.array([1,1],[1,1])b = np.array([1,1])(AA,bb) = run_SA(1,2,A,b) - Find the original monomial corresponding to new variables. Here we find it for y_3 in the result above after 1 round of SA on a system with 2 variables.(0 based indexing)
monomial = invert(2,2,1)monomial == [0,1]Thus y_3 = y_{0,1} which delinearizes to x_0x_1 - Supports dynamic programming/memoized mode and brute force. To use memoized:
run_SA(k = 2,n = 5,A = A,b = b,memoize = True)