Ask Your Question
0

Linear programming with a strange result

asked 2021-01-23 12:21:18 +0100

Cyrille gravatar image

updated 2023-05-19 22:07:11 +0100

FrédéricC gravatar image

I have encoutered a strange behavior in solving a linear program.

def sol_zero_sum_game(M=matrix([[1,-1], [-1,1]]),code=1) :
    dim = M.nrows()
    U=ones_matrix(dim,dim)
    zsg=MixedIntegerLinearProgram(maximization=False, solver="GLPK")
    x=zsg.new_variable(real=True,nonnegative=True, indices=[0..dim-1])
    minM=min(min(M))
    Id= identity_matrix(dim)
    M1=(abs(minM)+1)*U+M
    Bzsgl=M1*x
    zsg.set_objective(sum(x[i] for i in range(dim)))
    zsg.solve()
    xx=zsg.get_values(x)
    #show(xx)
    for i in range(0,dim) :
           zsg.add_constraint(Bzsgl[i]>=1)
    if code==1 :
        return zsg.show()
    if code==2 :
        return xx

The above code can display the program for the following G matrix :

G=matrix([[1,-1], [-1,1]])
sol_zero_sum_game(G,1)

The solution is given by :

G=matrix([[1,-1], [-1,1]])
sol_zero_sum_game(G,2)

which gives {0: 0.0, 1: 0.0} as a solution. But this is obviously false since after substitution of $(0,0)$ in the constrains it doesn't work. As this is the formalisation of a game I know that the solution is $(0.25, 0.25)$ as confirmed by an other software LIPS (see the screen capture below).

image description

I have certainly made a mistake but I can't see where. Thanks for help.

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2021-01-23 15:30:28 +0100

Cyrille gravatar image

updated 2021-01-24 10:37:41 +0100

After a long time looking at my code I have found that the constraints were defined after calling solve

def sol_zero_sum_game(M=matrix([[1,-1], [-1,1]]),code=1) :
    dim = M.nrows()
    U=ones_matrix(dim,dim)
    zsg=MixedIntegerLinearProgram(maximization=False, solver="GLPK")
    x=zsg.new_variable(real=True,nonnegative=True, indices=[0..dim-1])
    minM=min(min(M))
    Id= identity_matrix(dim)
    M1=(abs(minM)+1)*U+M
    Bzsgl=M1*x
    zsg.set_objective(sum(x[i] for i in range(dim)))
    #show(xx)
    for i in range(0,dim) :
           zsg.add_constraint(Bzsgl[i]>=1)
    zsg.solve()
    xx=zsg.get_values(x)
    if code==1 :
        return zsg.show()
    if code==2 :
        return xx
edit flag offensive delete link more

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: 2021-01-23 12:21:18 +0100

Seen: 197 times

Last updated: Jan 24 '21