How to use linear algebra inside of MixedIntegerLinearPrograms?
I have a largish matrix M that defines a polytope P, via a bunch of constraints of the form u.v > b. Here u is the vector of variables and v ranges over the columns of the matrix M. I want to optimize a simple linear functional over P. I can use a MixedIntegerLinearProgram to solve this problem. But I have to roll my own dot_prod function, because sage will not let me treat u as a vector. Is there something I've missed?
Here is the code -
def dot_prod(u, v): dim = len(v) return sum(u[i]*v[i] for i in range(dim)) def farkas(M): '''Look for edge vector u so that all entries of u*M are positive. If one exists, return True.''' N = Matrix(M) q = MixedIntegerLinearProgram( maximization=False, solver='GLPK' ) u = q.new_variable( real=True, nonnegative=False ) for v in N.columns(): q.add_constraint( dot_prod(u, v), min = 1 ) # unpleasant q.set_objective( sum( dot_prod(u, v) for v in N.columns() ) ) # likewise try: q.solve() return True except MIPSolverException: return False