Python linprog to maximise objective function

Question

It has been a while since I have done this so I am a bit rusty, but equation is:

max t(C)*x
s.t. Ax <=b

And I have my A matrix of constraints which is (1448x1359) :

[[ 1.  1.  0. ...,  0.  0.  0.]

 ..., 


 [ 0.  0.  0. ...,  1.  1.  1.]]

Then I have my binding b (1448x1):

[ 1.  1.  7. ...,  2.  1.  2.]

And my objective function to be maximised which is a vector of ones (1359,1).

Now in other packages my maximised objective function is 841, however using linprog:

res = linprog(c=OBJ_N, A_ub=A, b_ub=b, options={"disp": True})

It optimised successfully to -0.0 so I wonder if I'm using the right command in python and have my constraints the right way around?

Edit: Ok that makes sense, it was trying to minimise. I have rewritten now (swapped c and b and transposed A to minimise).

# (max t(C)*x s.t. Ax <=b) = min t(b)*x s.t. ATy = c, y ≥ 0
# (i): minimise number of shops no bounds
ID = np.ones(len(w[0]))
print(ID)
print(ID.shape)  #1359

At = A.transpose()

need_divest = (A.dot(ID)) - 1
print(need_divest)
print(need_divest.shape)  #1448

res = linprog(c=need_divest, A_eq=At, b_eq=ID, options={"disp": True})
print(res)

However, I get "message: 'Optimzation failed. Unable to find a feasible starting point.'"

linprog: Minimize a linear objective function subject to linear equality and inequality constraints. - Does that help? — cel
– cel, Commented Oct 13, 2015 at 13:49
You are going the wrong way... Here you are trying to solve the dual problem of your original minimization problem. You can consider the answer below to state correctly your original problem. — Mathiou
– Mathiou, Commented Oct 13, 2015 at 14:37

Mathiou · Accepted Answer · 2015-10-13 14:37:30Z

2

I guess you are probably minimizing instead of maximizing your objective function. Try with this (inserting a - in front of your objective function coefficients) :

res = linprog(c=-OBJ_N, A_ub=A, b_ub=b, options={"disp": True})

Your result should then be -841.

This works simply because :

min(f(x))=-max(-f(x))

edited Oct 13, 2015 at 14:37

answered Oct 13, 2015 at 14:25

Mathiou

4173 silver badges12 bronze badges

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

5 Comments

Ilia Karmanov Over a year ago

Thank you very much! You cured my long hour of stupidity

Mathiou Over a year ago

Nothing to do with stupidity, you just needed a small refreshment in linear programming :)

Mathiou Over a year ago

I don't think you can do that using linprog. Problem is much more difficult when you need integral variables so there are different resolution algorithms for those ILPproblems. Have a look at this if you want to know more on where to look : stackoverflow.com/questions/26305704/…

Ilia Karmanov Over a year ago

Interestingly when I imposed the constraint that x is between 0 and 1 (res = linprog(c=-ID, A_ub=A, b_ub=need_sell, bounds=(0,1), options={"disp": True})) I was able to match my answer using the R package. So I wonder if it's the case it forces an integer? However, I guess it could be a coincidence. Thank you for the link!

Mathiou Over a year ago

No, just a coïncidence (lucky you !) I guess. It may happen depending of the structure of your problem. But they say in the documentation that only the simplex algorithm is implemented yet, and it cannot solve ILP (else we'll be rich because we would have proven a famous mathematical conjecture that is P=NP !).

Collectives™ on Stack Overflow

Python linprog to maximise objective function

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related