[SciPy-Dev] Proposed enhancement: pure Python implementation of LP simplex method (two-phase)

Bruce Southey bsouthey@gmail....
Fri Jul 30 08:49:31 CDT 2010

  On 07/30/2010 03:49 AM, Pauli Virtanen wrote:
> Fri, 30 Jul 2010 09:48:49 +0800, Enzo Michelangeli wrote:
> [clip]
>>>> http://projects.scipy.org/scipy/ticket/1252
>>> I think your "test case" could easily be turned into a unit test, which
>>> would make the submission more complete.
>> Done.
> Seems to work.
> Some API nitpicks,
> 1)
> Return a solution object rather than a tuple:
> class NamedTuple(tuple):
>      def __new__(cls, values, names):
>          self = tuple.__new__(cls, values)
>          for value, name in zip(values, names):
>              setattr(self, name, value)
>          return self
> class Solution(NamedTuple):
>      _fields = []
>      def __new__(cls, *a, **kw):
>          values = list(a)
>          for name in cls._fields[len(values):]:
>              values.append(kw.pop(name))
>          if len(values) != len(cls._fields) or kw:
>              raise ValueError("Invalid arguments")
>          return NamedTuple.__new__(cls, values, cls._fields)
>      def __repr__(self):
>          return "%s%s" % (self.__class__.__name__,
>                           NamedTuple.__repr__(self))
> class LPSolution(Solution):
>      """
>      Solution to a linear programming problem
>      Attributes
>      ----------
>      x
>          The optimal solution
>      min
>          The optimal value
>      is_bounded
>          True if the solution is bounded; False if unbounded
>      solvable
>          True if the problem is solvable; False if unsolvable
>      basis
>          Indices of the basis of the solution.
>      """
>      _fields = ['x', 'min', 'is_bounded', 'solvable', 'basis']
> def lp(...):
>      ...
>      return LPSolution(optx, zmin, is_bounded, sol, basis)
> We could (and probably should) replace *all* cases in Scipy where a tuple
> is currently returned by this sort of pattern. It's backwards compatible,
> since the returned object is still some sort of a tuple.
> 2)
> Don't print to stdout.
> Use warnings.warn if you need to warn about something.
> 3)
> Call
> 	c = np.asarray(c)
> 	A = np.asarray(A)
> 	b = np.asarray(b)
> in the beginning -- good for convenience.
Really this is lacking major documentation that needs to be addressed as 
much as possible. It would be really really nice if there was 
documentation as per the Scipy doc marathon. In particular there is no 
description of 'A', 'b' and 'c' as these could be any type of 'numpy 
array' and of different shapes.

Just a couple of other suggestions as I have only glanced at the code.
This is necessary to check the input shapes because it is not very 
obvious what the shapes are without reading the code. For example 'A' 
must be a 2-d array and apparently 'b' and 'c' must be 1d arrays. So I 
do think that you need to provide some checks that 'A', 'b' and 'c' are 
of the correct shape - at least to inform the user what is expected when 
an error arises. This also related to documentation.

Also np.asarray does not respect other ndarray subclasses so you 
probably want to test and reject things like masked arrays and Matrix 
inputs but allow other array-like inputs. (It is my little hope that 
numpy/scipy functions become aware of the different arrays and at least 
warn the user when an array is not what is expected.)


More information about the SciPy-Dev mailing list