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

edit retag close merge delete

Sort by ยป oldest newest most voted

I have a partial answer for you. I can get the matrix constraints to work as in the following example:

p = MixedIntegerLinearProgram(maximization = True, solver='GLPK')
x = p.new_variable(real=True,nonnegative=True)
M=Matrix([[1,0.2],[1.5,3]])
v = vector([4,4])
u = vector([1,5])
p.show()


Unfortunately, I cannot get the objective function to work so nicely with vectors. I cannot seem to get set_objective to let me do a vector calculation inside the command.

Another option is to work with linear_programas found at http://doc.sagemath.org/html/en/refer...

I think @Nathann is one of the experts on the linear programming in Sage. He definitely would know more.

For the linear_program command, here is some sample code:

M=Matrix(RDF,[[-1,0],[0,-1],[-1,-1] ])
v = vector(RDF,[-5.5,-3.5,-7.5])
u = vector(RDF,[3,4])
sol=linear_program(u,M,v)
sol['x']


This minimizes the objective function $u^t x$ with constraint $M x \ge v$.

more

It is true that the "matrix shortcut" that is used in the add_constraint method is not available in set_objective. That should be rather straightforward to implement, though. If any of you feels like contributing to Sage, that is a good occasion.

( 2015-09-08 12:28:30 +0200 )edit

Thanks for finding a partial solution, and for the reference to linear_program. I'll take a look.

( 2015-09-09 03:26:07 +0200 )edit