ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 28 Apr 2011 17:03:06 +0200Solve very simple linear programhttps://ask.sagemath.org/question/8093/solve-very-simple-linear-program/I have tried to figure out the docs at [the optimization docs](http://www.sagemath.org/doc/reference/sage/numerical/optimize.html) and cannot for the life of me figure out how to program this very simple LP. The problem is that everything has to be written as a minimization, and figuring out what should be minus is a real headache - especially when it doesn't work as expected!
This is in an interact.
@interact
def _(M = matrix(RR,[[1,-1],[-1,1]]),auto_update=False):
f1(p) = (M[1,0] - M[0,0])*p+M[0,0]
f2(p) = (M[1,1] - M[0,1])*p+M[0,1]
# sol1 = find_maximum_on_interval(lambda y: min_symbolic(f1(y),f2(y)),0,1)[0]
sol1 = linear_program(vector([0,1]),matrix([[-1,0],[1,0],[M[1,0] - M[0,0],-1],[M[1,1] - M[0,1],-1]]),vector([0,1,-M[0,0],-M[0,1]]))['x'][0]
print sol1
E.g., `M=[[1,2],[0,-1]]` is just trying to maximize $y$ for below the lines $1-p$ and $2-3p$. (This is a basic zero-sum game I'm trying to demonstrate the solution of, for context.)
For the matrix [[1,2],[0,-1]], it should give p=0, but instead gives the minimum of the opposite.
It would be nice to not have to do quite as much work. Also, the `find_maximum_on_interval` function doesn't seem to give what I want here either.Wed, 27 Apr 2011 17:12:51 +0200https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/Answer by Nathann for <p>I have tried to figure out the docs at <a href="http://www.sagemath.org/doc/reference/sage/numerical/optimize.html">the optimization docs</a> and cannot for the life of me figure out how to program this very simple LP. The problem is that everything has to be written as a minimization, and figuring out what should be minus is a real headache - especially when it doesn't work as expected!</p>
<p>This is in an interact.</p>
<pre><code>@interact
def _(M = matrix(RR,[[1,-1],[-1,1]]),auto_update=False):
f1(p) = (M[1,0] - M[0,0])*p+M[0,0]
f2(p) = (M[1,1] - M[0,1])*p+M[0,1]
# sol1 = find_maximum_on_interval(lambda y: min_symbolic(f1(y),f2(y)),0,1)[0]
sol1 = linear_program(vector([0,1]),matrix([[-1,0],[1,0],[M[1,0] - M[0,0],-1],[M[1,1] - M[0,1],-1]]),vector([0,1,-M[0,0],-M[0,1]]))['x'][0]
print sol1
</code></pre>
<p>E.g., <code>M=[[1,2],[0,-1]]</code> is just trying to maximize $y$ for below the lines $1-p$ and $2-3p$. (This is a basic zero-sum game I'm trying to demonstrate the solution of, for context.)</p>
<p>For the matrix [[1,2],[0,-1]], it should give p=0, but instead gives the minimum of the opposite.</p>
<p>It would be nice to not have to do quite as much work. Also, the <code>find_maximum_on_interval</code> function doesn't seem to give what I want here either.</p>
https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/?answer=12323#post-id-12323You may find the use of the MixedIntegerLinearProgram class easier :
http://www.sagemath.org/doc/reference/sage/numerical/mip.html
NathannThu, 28 Apr 2011 14:00:44 +0200https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/?answer=12323#post-id-12323Comment by kcrisman for <p>You may find the use of the MixedIntegerLinearProgram class easier :</p>
<p><a href="http://www.sagemath.org/doc/reference/sage/numerical/mip.html">http://www.sagemath.org/doc/reference...</a></p>
<p>Nathann</p>
https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/?comment=21777#post-id-21777Well, but I wasn't looking for integer answers! Looks like that (floating-point) is supported as well, but it's sometimes hard to tell from this doc which is which in solving. Thanks!Thu, 28 Apr 2011 17:03:06 +0200https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/?comment=21777#post-id-21777Answer by chaesloc for <p>I have tried to figure out the docs at <a href="http://www.sagemath.org/doc/reference/sage/numerical/optimize.html">the optimization docs</a> and cannot for the life of me figure out how to program this very simple LP. The problem is that everything has to be written as a minimization, and figuring out what should be minus is a real headache - especially when it doesn't work as expected!</p>
<p>This is in an interact.</p>
<pre><code>@interact
def _(M = matrix(RR,[[1,-1],[-1,1]]),auto_update=False):
f1(p) = (M[1,0] - M[0,0])*p+M[0,0]
f2(p) = (M[1,1] - M[0,1])*p+M[0,1]
# sol1 = find_maximum_on_interval(lambda y: min_symbolic(f1(y),f2(y)),0,1)[0]
sol1 = linear_program(vector([0,1]),matrix([[-1,0],[1,0],[M[1,0] - M[0,0],-1],[M[1,1] - M[0,1],-1]]),vector([0,1,-M[0,0],-M[0,1]]))['x'][0]
print sol1
</code></pre>
<p>E.g., <code>M=[[1,2],[0,-1]]</code> is just trying to maximize $y$ for below the lines $1-p$ and $2-3p$. (This is a basic zero-sum game I'm trying to demonstrate the solution of, for context.)</p>
<p>For the matrix [[1,2],[0,-1]], it should give p=0, but instead gives the minimum of the opposite.</p>
<p>It would be nice to not have to do quite as much work. Also, the <code>find_maximum_on_interval</code> function doesn't seem to give what I want here either.</p>
https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/?answer=12322#post-id-12322You program is minimizing y above those lines. The problem is not unbounded only because of the additional constraints 0 < p < 1 given by the top 2 rows of G (=see below).
Using the notation in the article you linked, linear_program(c,G,h) *minimizes* c * x given G * x < h. You have c=[0,1] and x=[p,y], so you are *minimizing* y. You want c=[0,-1].
You have G * x = [-p,p,-p-y,-3p-y] < h, which gives y>-h[2]-p, y>-h[3]-3p. You want G*x=[-p,p,p+y,3p+y] and h=[0,1,1,2].
So you want c=[0,-1]; G=[[-1,0],[1,0],[1,1],[3,1]]; h=[0,1,1,2]. As for M, I have no clue what it is.
linear_program(vector([0,-1]),matrix([[-1,0],[1,0],[1,1],[3,1]]),vector([0,1,1,2]))['x'][0]
-7.08356432755e-09Wed, 27 Apr 2011 23:05:56 +0200https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/?answer=12322#post-id-12322Comment by kcrisman for <p>You program is minimizing y above those lines. The problem is not unbounded only because of the additional constraints 0 < p < 1 given by the top 2 rows of G (=see below).</p>
<p>Using the notation in the article you linked, linear_program(c,G,h) <em>minimizes</em> c * x given G * x < h. You have c=[0,1] and x=[p,y], so you are <em>minimizing</em> y. You want c=[0,-1].</p>
<p>You have G * x = [-p,p,-p-y,-3p-y] < h, which gives y>-h[2]-p, y>-h[3]-3p. You want G*x=[-p,p,p+y,3p+y] and h=[0,1,1,2].</p>
<p>So you want c=[0,-1]; G=[[-1,0],[1,0],[1,1],[3,1]]; h=[0,1,1,2]. As for M, I have no clue what it is.</p>
<pre><code>linear_program(vector([0,-1]),matrix([[-1,0],[1,0],[1,1],[3,1]]),vector([0,1,1,2]))['x'][0]
-7.08356432755e-09
</code></pre>
https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/?comment=21779#post-id-21779Thanks much; I had already realized I needed to switch c, but for some reason had my inequalities goofed and was not switching the [1,1],[3,1] from my original [-1,-1],[-3,-1]. Don't worry about M - I know what it is :)Thu, 28 Apr 2011 00:40:12 +0200https://ask.sagemath.org/question/8093/solve-very-simple-linear-program/?comment=21779#post-id-21779