ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 08 Sep 2015 20:26:07 -0500How to use linear algebra inside of MixedIntegerLinearPrograms?http://ask.sagemath.org/question/29413/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 FalseSun, 06 Sep 2015 21:41:48 -0500http://ask.sagemath.org/question/29413/how-to-use-linear-algebra-inside-of-mixedintegerlinearprograms/Answer by calc314 for <p>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? </p>
<p>Here is the code - </p>
<pre><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
</code></pre>
http://ask.sagemath.org/question/29413/how-to-use-linear-algebra-inside-of-mixedintegerlinearprograms/?answer=29416#post-id-29416 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_program` as found at http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/optimize.html
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$.Mon, 07 Sep 2015 15:58:58 -0500http://ask.sagemath.org/question/29413/how-to-use-linear-algebra-inside-of-mixedintegerlinearprograms/?answer=29416#post-id-29416Comment by Saul Schleimer for <p>I have a partial answer for you. I can get the matrix constraints to work as in the following example:</p>
<pre><code>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()
</code></pre>
<p>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.</p>
<p>Another option is to work with <code>linear_program</code>as found at <a href="http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/optimize.html">http://doc.sagemath.org/html/en/refer...</a></p>
<p>I think <a href="/users/30/nathann/">@Nathann</a> is one of the experts on the linear programming in Sage. He definitely would know more.</p>
<p>For the <code>linear_program</code> command, here is some sample code:</p>
<pre><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']
</code></pre>
<p>This minimizes the objective function $u^t x$ with constraint $M x \ge v$.</p>
http://ask.sagemath.org/question/29413/how-to-use-linear-algebra-inside-of-mixedintegerlinearprograms/?comment=29420#post-id-29420Thanks for finding a partial solution, and for the reference to linear_program. I'll take a look.Tue, 08 Sep 2015 20:26:07 -0500http://ask.sagemath.org/question/29413/how-to-use-linear-algebra-inside-of-mixedintegerlinearprograms/?comment=29420#post-id-29420Comment by Nathann for <p>I have a partial answer for you. I can get the matrix constraints to work as in the following example:</p>
<pre><code>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()
</code></pre>
<p>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.</p>
<p>Another option is to work with <code>linear_program</code>as found at <a href="http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/optimize.html">http://doc.sagemath.org/html/en/refer...</a></p>
<p>I think <a href="/users/30/nathann/">@Nathann</a> is one of the experts on the linear programming in Sage. He definitely would know more.</p>
<p>For the <code>linear_program</code> command, here is some sample code:</p>
<pre><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']
</code></pre>
<p>This minimizes the objective function $u^t x$ with constraint $M x \ge v$.</p>
http://ask.sagemath.org/question/29413/how-to-use-linear-algebra-inside-of-mixedintegerlinearprograms/?comment=29418#post-id-29418It 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.Tue, 08 Sep 2015 05:28:30 -0500http://ask.sagemath.org/question/29413/how-to-use-linear-algebra-inside-of-mixedintegerlinearprograms/?comment=29418#post-id-29418