Ask Your Question

Solve very simple linear program

asked 2011-04-27 10:12:51 -0500

kcrisman gravatar image

I have tried to figure out the docs at the optimization docs 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.

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.

edit retag flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted

answered 2011-04-27 16:05:56 -0500

chaesloc gravatar image

updated 2011-04-27 16:10:01 -0500

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).

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.

edit flag offensive delete link more


Thanks 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 :)

kcrisman gravatar imagekcrisman ( 2011-04-27 17:40:12 -0500 )edit

answered 2011-04-28 07:00:44 -0500

Nathann gravatar image

You may find the use of the MixedIntegerLinearProgram class easier :


edit flag offensive delete link more


Well, 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!

kcrisman gravatar imagekcrisman ( 2011-04-28 10:03:06 -0500 )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


Asked: 2011-04-27 10:12:51 -0500

Seen: 582 times

Last updated: Apr 28 '11