Revision history [back]

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