0

I am trying to solve a linear programming problem of the form

minimise cT.x
A.x = b
x >= 0

for a transportation problem.

However, using CVXOPT requires defining the variables G.x <= h for the lp(G,h,A,b) solver.

I have tried creating my A and b matrices, and for the G and h matrices i use a identity matrix for G (multiplied by -1) and a vector of zeros for h, so as to impose the x>=0 constraints.

However, when i run my code, it returns a "singular KKT matrix".

Could anyone help me with what is the problem, or how i can run the CVXOPT solver without a G and h variables.

mtigger
  • 2,397
  • 3
  • 15
  • 17
  • Why don't you use an LP (linear programming) solver? CVXOPT is for convex optimization which is far more difficult than LP. See [my earlier answer](http://stackoverflow.com/a/10705799/341970) here. – Ali Feb 22 '13 at 18:56
  • Yes, i am trying to use PuLP and Pyglpk now. thanks! @Ali – mtigger Feb 23 '13 at 18:17

2 Answers2

0

Optimal solution of the transportation problem is searched using Potential Method. To use Potential Method, you shall solve three lavel equation. Network problem such as transportation problem have to solve using dual problem, please.

GMHMH
  • 1
-1

Your solution (-G - identity matrix, h - zeros vector) should be work. You can post your data here.

For example:

from cvxopt import matrix, solvers
c = matrix([ 2.0, 1.0 ])
G = matrix(-np.eye(2))
h = matrix(np.zeros(2)) 
A = matrix(np.eye(2))
b = matrix([1., 2.])
sol = solvers.lp(c, G, h, A, b)
print(sol['x'])

Optimal solution found.
[ 1.00e+00]
[ 2.00e+00]
nampi
  • 9
  • 4