Skip to content

A 6 x 6 linprog testcase: 3 methods x sparse / dense give different results #10288

@denis-bz

Description

@denis-bz

A 6 x 6 linprog testcase from glpk: 3 methods x sparse / dense give different results

transp-linprog.py below is a 6 x 6 testcase of scipy.optimize.linprog
from a GLPK example, transp. In outline:

for method in ["interior-point", "revised simplex", "simplex"]:
    for sparse in [True, False]
        try:
            linprog( ... )

The 6 combinations give rather different results. grep transp-linprog.log:

linprog  method: interior-point  sparse: True 
The algorithm terminated successfully and determined that the problem is infeasible.
final f: 0.649008  x: [0.711 0.57 0.515 0.707 0.557 0.549] 

linprog  method: interior-point  sparse: False 
The algorithm terminated successfully and determined that the problem is unbounded.
final f: 0.649472  x: [0.712 0.57 0.515 0.708 0.557 0.55] 

linprog  method: revised simplex  sparse: True 
ValueError: shapes (1,12) and (1,12) not aligned: 12 (dim 1) != 1 (dim 0)

linprog  method: revised simplex  sparse: False 
final f: 153.675  x: [50 300 0 275 0 275] 

linprog  method: simplex  sparse: True 
ValueError: all the input arrays must have same number of dimensions

linprog  method: simplex  sparse: False 
final f: 153.675  x: [0 300 0 325 0 275] 

The full logfile and transp.* glpk files are under https://gist.github.com/denis-bz transp-linprog .

Transp is the smallest of the GLPK examples/, here made into a standalone testcase.

Reproducing code example:

    #!/usr/bin/env python
    """ linprog testcase from transp.glp: all 3 methods, sparse / dense """

    from __future__ import division, print_function
    import sys
    import time
    import traceback  # cf. better-exceptions
    import numpy as np
    import scipy
    from scipy import sparse
    from scipy.optimize import linprog  # $scopt13/_linprog.py
        # https://docs.scipy.org/doc/scipy/reference/optimize.linprog-interior-point.html

    __version__ = "2019-06-10 june"
    __author_email__ = "denis-bz-py t-online.de"

    np.set_printoptions( threshold=10, edgeitems=5, linewidth=140,
            formatter = dict( float = lambda x: "%.3g" % x ))  # float arrays %.3g
    print( "\n" + 80 * "=" )
    print( "from", " ".join( sys.argv ), time.strftime( "%c" ))
    print( "versions: numpy %s  scipy %s   python %s " % (
            np.__version__, scipy.__version__ , sys.version.split()[0] ))

    #...............................................................................
    disp = True
    maxiter = 50
    tol = 1e-4  # default 1e-8

        # from glpk /examples/transp.glp glp_linprog --
    c = np.r_[ 0.225, 0.153, 0.162, 0.225, 0.162, 0.126 ]
    lb = np.r_[ 0, 0, 0, 0, 0, 0 ]
    ub = np.r_[ 1e10, 1e10, 1e10, 1e10, 1e10, 1e10 ]  # grr inf
    b = np.r_[ 1e10, 350, 600, -325, -300, -275 ]

    Adense = np.array(
        [[0.225, 0.153, 0.162, 0.225, 0.162, 0.126],
        [1, 1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1, 1],
        [-1, 0, 0, -1, 0, 0],
        [0, -1, 0, 0, -1, 0],
        [0, 0, -1, 0, 0, -1]]
        )

        # to change these params, run this.py  a=1  b=None  'c = expr' ...
        # in sh or ipython --
    for arg in sys.argv[1:]:
        exec( arg )


    A = [Adense, sparse.csr_matrix( Adense )]
    bounds = np.c_[ lb, ub ]
    print( "c A: \n%s \n%s \nb: %s " % (c, Adense, b) )
    print( "params: disp %s  tol %g " % (disp, tol) )

    #...............................................................................
    for method in ["interior-point", "revised simplex", "simplex"]:
      for sparse in [True, False]:
        print( "\n" +  80 * "-" )
        print( "linprog  method: %s  sparse: %s " % (method, sparse) )
        options = dict( disp=disp, maxiter=maxiter, tol=tol,
                    sparse = sparse )  # rs, simplex OptimizeWarning
        try:
            res = linprog( A_ub=A[sparse], b_ub=b, c=c, bounds=bounds,
                    method=method, options=options )
            if not disp:
                print( "linprog:", res.message )
            print( "final f: %g  x: %s " % (res.fun, res.x) )
                # glpk: 50 300 0 275 0 275
        except (IndexError, ValueError):
            traceback.print_exc()

Error messages:

above

Scipy/Numpy/Python version information:

versions: numpy 1.16.4 scipy 1.3.0 python 3.7.3

Metadata

Metadata

Assignees

No one assigned

    Labels

    good first issueGood topic for first contributor pull requests, with a relatively straightforward solutionscipy.optimize

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions