0

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.'"

Ilia Karmanov
  • 215
  • 5
  • 13
  • linprog: `Minimize a linear objective function subject to linear equality and inequality constraints.` - Does that help? – cel Oct 13 '15 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 Oct 13 '15 at 14:37

1 Answers1

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))
Mathiou
  • 399
  • 2
  • 12
  • Thank you very much! You cured my long hour of stupidity – Ilia Karmanov Oct 13 '15 at 14:52
  • 1
    Nothing to do with stupidity, you just needed a small refreshment in linear programming :) – Mathiou Oct 13 '15 at 14:54
  • 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 `ILP`problems. Have a look at this if you want to know more on where to look : http://stackoverflow.com/questions/26305704/python-mixed-integer-linear-programming – Mathiou Oct 13 '15 at 15:12
  • 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! – Ilia Karmanov Oct 13 '15 at 15:14
  • 1
    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 !). – Mathiou Oct 13 '15 at 15:19