from mip import Model, BINARY, xsum, OptimizationStatus #  CONTINUOUS, INTEGER
import numpy as np
from itertools import permutations

A = np.array([[1,1,1,1,1],
              [2,2,2,2,2],
              [0,1,2,3,4],
              [2,1,4,1,0],
              [0,1,0,1,0]])
var_type = BINARY
max_gap = 0.05
max_seconds=10

def createModelAndCheck(A, b, var_type, max_gap, max_seconds):
    n,m = A.shape
    model = Model()
    x = [model.add_var(var_type=var_type) for i in range(n)]
    
    for i in range(m):
        A_i = A[i]
        b_i = b[i]
        model += xsum(A_i[j]*x[j] for j in range(n)) == b_i
    
    model.max_gap = max_gap
    status = model.optimize(max_seconds=max_seconds)
    if status != OptimizationStatus.INFEASIBLE:
        print("Found b: ", b)
    if status == OptimizationStatus.OPTIMAL:
        print('optimal solution cost {} found'.format(model.objective_value))
    elif status == OptimizationStatus.FEASIBLE:
        print('sol.cost {} found, best possible: {}'.format(model.objective_value, model.objective_bound))
    elif status == OptimizationStatus.NO_SOLUTION_FOUND:
        print('no feasible solution found, lower bound is: {}'.format(model.objective_bound))
    if status == OptimizationStatus.OPTIMAL or status == OptimizationStatus.FEASIBLE:
        print('solution:')
        for v in model.vars:
            if abs(v.x) > 1e-6: # only printing non-zeros
                print('{} : {}'.format(v.name, v.x))

brute_force_b = list(permutations([0,1,2,3,4,5,6,7,8],5))
for b in brute_force_b:
    createModelAndCheck(A, np.array(b), var_type, max_gap, max_seconds)


A.dot(np.array([0,1,1,0,0]))

