Ask Your Question
0

How to use linear algebra inside of MixedIntegerLinearPrograms?

asked 2015-09-07 04:41:48 +0100

Saul Schleimer gravatar image

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2015-09-07 22:58:58 +0100

calc314 gravatar image

updated 2015-09-08 01:39:46 +0100

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.add_constraint(M*x <= v)
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$.

edit flag offensive delete link more

Comments

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.

Nathann gravatar imageNathann ( 2015-09-08 12:28:30 +0100 )edit

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

Saul Schleimer gravatar imageSaul Schleimer ( 2015-09-09 03:26:07 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-09-07 04:41:48 +0100

Seen: 402 times

Last updated: Sep 08 '15