python - Scipy: Linear programming with sparse matrices -

i want solve linear program in python. number of variables (i call n on) large (~50000) , in order formulate problem in way scipy.optimize.linprog requires it, have construct 2 n x n matrices (a , b below). lp can written as

minimize: c.x subject to:     a.x <=     b.x  = b     x_i >= 0 in {0, ..., n} 

whereby . denotes dot product , a, b, , c vectors length n.

my experience constructing such large matrices (a , b have both approx. 50000x50000 = 25*10^8 entries) comes issues: if hardware not strong, numpy may refuse construct such big matrices @ (see example very large matrices using python , numpy) , if numpy creates matrix without problems, there huge performance issue. natural regarding huge amount of data numpy has deal with.

however, though linear program comes n variables, matrices work sparse. 1 of them has entries in first row, other 1 in first m rows, m < n/2. of course exploit fact.

as far have read (e.g. trying solve scipy optimization problem using sparse matrices , failing), scipy.optimize.linprog not work sparse matrices. therefore, have following questions:

• is true scipy not offer possibility solve linear program sparse matrices? (if not, how can it?)
• do know alternative library solve problem more effectively scipy non-sparse matrices? (the library suggested in thread above seems not flexible enough purposes - far understand documentation)
• can expected new implementation of simplex algorithm (using plain python, no c) exploits sparsity of matrices more efficient scipy non-sparse matrices?

i forming dense matrix (or two) solve large sparse lp not right thing do. when solving large sparse lp important use solver has facilities handle such problems , generate model in way not create explicitly of these 0 elements.

writing stable, fast, sparse simplex lp solver in python replacement scipy dense solver not trivial exercise. solver written in pure python may not perform well.

for size indicate, although not very, large (may large medium sized model classification) may want consider commercial solver cplex, gurobi or mosek. these solvers fast , reliable (they solve lp problem throw @ them). have python apis. solvers free or cheap academics.

if want use open source solver, may want @ coin clp solver. has python interface.

if model more complex may want consider use python modeling tool such pulp or pyomo (gurobi has modeling support in python).