Linear programming, unexpected solution with equality constraint

Question

I'm trying to figure out what is wrong with my implementation, I expect the result to be [5, 10], I don't understand how it gets [7.5, 7.5], x1 should be half of x2.

from scipy.optimize import linprog
import numpy as np

c = [-1, -1]

A_eq = np.array([
    [1, 0.5],
    [1, -0.5],
])

b_eq = [15, 0]

x0_bounds = (0, None)
x1_bounds = (0, None)

res = linprog(
    c,
    A_eq=A_eq.transpose(),
    b_eq=b_eq,
    bounds=(x0_bounds, x1_bounds),
    options={"disp": True})

print res.x
# =>                                                                                                                                                                                 
# Optimization terminated successfully.                                                                                                                                              
#          Current function value: -15.000000                                                                                                                                        
#          Iterations: 2                                                                                                                                                             
# [ 7.5  7.5]

Update from the author:

As it was said matrix transposition is not needed here. The problem was in the matrix itself, in order to get desired result, which is [5, 10], it has to be:

A_eq = np.array([
    [1, 1],
    [1, -0.5],
])

Community · Accepted Answer · 2020-06-20 09:12:55Z

2

Per the scipy linprog docs:

Minimize: c^T * x

Subject to:

A_ub * x <= b_ub

A_eq * x == b_eq

So, you are now solving the following equations:

Minimize -x1 -x2

Subject to,*

x1 + x2 = 15 (i)
0.5 * x1 - 0.5 * x2 = 0 (ii)

Now, (ii) implies x1 = x2 (so your desired solution is infeasable), and then (i) fixes x1 = x2 = 7.5. So, the solution returned by linprog() is indeed correct. Since you are expecting a different result, maybe you should look into the way you translated your problem into code, as I think that's where you will find both the issue and the solution.

*) Since you are taking the transpose.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Dec 21, 2015 at 17:19

Nelewout

6,6446 gold badges31 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rusty Robot Over a year ago

Thanks, original question was without matrix transposition, did it this way unconsciously probably due to a late evening, basically found out how to achieve desired result, the first row in the matrix has to be [1, 1], thanks once more.

Nelewout Over a year ago

@RustyRobot it is good to hear that you found out where the problem was. You are welcome! :)

Holt · Accepted Answer · 2015-12-21 17:20:09Z

2

Your problem is:

x1 + x2 == 15
0.5 * x1 - 0.5 * x2 == 0

minimize -x1 -x2

So obviously you have x1 == x2 (second constraint), and thus x1 = x2 = 7.5 (first constraint).

Looking at your question, you probably don't want to transpose A:

res = linprog(
    c,
    A_eq=A_eq,
    b_eq=b_eq,
    bounds=(x0_bounds, x1_bounds),
    options={"disp": True}
)

Why gives you the problem:

x1 + 0.5 * x2 == 15
x1 - 0.5 * x2 == 0

minimize -x1 -x2

And you get x1 = 7.5 and x2 = 15 (the only possible values).

answered Dec 21, 2015 at 17:20

Holt

38.1k7 gold badges100 silver badges147 bronze badges

Collectives™ on Stack Overflow

Linear programming, unexpected solution with equality constraint

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related