Skip to content

MatrixVariable.sum is slower than quicksum #1070

Closed

Description

@Zeroto521

Is your feature request related to a problem? Please describe.

Weirdly, Matrix is slower than list or dict.
The time costing: list/dict < numpy.ndarray < MatrixVariable.

In [2]: import numpy as np
   ...:
   ...: from pyscipopt import Model, quicksum

In [3]: def test_pyscipopt(n):
   ...:     model = Model()
   ...:
   ...:     model.addMatrixVar((n, n), vtype="I").sum()
   ...:

In [4]: def test_numpy(n):
   ...:     model = Model()
   ...:     matrix = np.empty((n, n), dtype=object)
   ...:     for idx in np.ndindex(matrix.shape):
   ...:         matrix[idx] = model.addVar(vtype="I")
   ...:
   ...:     matrix.sum()
   ...:

In [5]: def test_dict(n):
   ...:     model = Model()
   ...:
   ...:     x = {}
   ...:     for i in range(n):
   ...:         for j in range(n):
   ...:             x[i, j] = model.addVar(vtype="I")
   ...:
   ...:     quicksum(x[i, j] for i in range(i) for j in range(n))
   ...:

In [6]: timeit test_pyscipopt(180)
14 s ± 4.61 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [7]: timeit test_numpy(180)
10.6 s ± 305 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [8]: timeit test_dict(180)
265 ms ± 56.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Image

Describe the solution you'd like
A clear and concise description of what you want to happen.

Speed up MatrixVariable.

Additional context
Add any other context or screenshots about the feature request here.

Numpy could handle numeric and static data types.
But it is hard to handle non-numeric and dynamic data types.

The profiler information
In [9]: prun test_pyscipopt(180)
         65009 function calls (65008 primitive calls) in 9.413 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    9.151    9.151    9.151    9.151 {method 'reduce' of 'numpy.ufunc' objects}
        1    0.134    0.134    9.375    9.375 <ipython-input-3-00105e30a609>:1(test_pyscipopt)
    32401    0.087    0.000    0.094    0.000 _index_tricks_impl.py:715(__next__)
        1    0.018    0.018    0.022    0.022 history.py:833(_writeout_input_cache)
        1    0.013    0.013    9.387    9.387 <string>:1(<module>)
    32407    0.007    0.000    0.007    0.000 {built-in method builtins.next}
        1    0.003    0.003    0.025    0.025 decorator.py:232(fun)
        7    0.000    0.000    0.001    0.000 numeric.py:324(full)
        7    0.000    0.000    0.000    0.000 {built-in method numpy.empty}
      2/1    0.000    0.000    9.413    9.413 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 _stride_tricks_impl.py:37(as_strided)
        1    0.000    0.000    0.000    0.000 _index_tricks_impl.py:688(__init__)
        2    0.000    0.000    0.000    0.000 traitlets.py:3631(set)
        2    0.000    0.000    0.000    0.000 {method '__exit__' of 'sqlite3.Connection' objects}
        1    0.000    0.000    0.000    0.000 {method 'execute' of 'sqlite3.Connection' objects}
        1    0.000    0.000    0.022    0.022 history.py:845(writeout_cache)
        1    0.000    0.000    0.000    0.000 inspect.py:3133(_bind)
        2    0.000    0.000    0.000    0.000 traitlets.py:718(_validate)
        1    0.000    0.000    0.000    0.000 traitlets.py:1527(_notify_observers)
        2    0.000    0.000    0.000    0.000 traitlets.py:3474(validate)
        1    0.000    0.000    0.000    0.000 numeric.py:98(zeros_like)
        7    0.000    0.000    0.000    0.000 _weakrefset.py:39(_remove)
        2    0.000    0.000    0.000    0.000 traitlets.py:689(set)
        1    0.000    0.000    0.022    0.022 history.py:55(only_when_enabled)
        5    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
        6    0.000    0.000    0.000    0.000 traitlets.py:676(__get__)
        1    0.000    0.000    9.151    9.151 _methods.py:49(_sum)
        1    0.000    0.000    0.000    0.000 {built-in method numpy.asarray}
        2    0.000    0.000    0.000    0.000 traitlets.py:727(_cross_validate)
        6    0.000    0.000    0.000    0.000 traitlets.py:629(get)
        1    0.000    0.000    0.000    0.000 traitlets.py:1512(_notify_trait)
        1    0.000    0.000    0.000    0.000 decorator.py:200(fix)
        1    0.000    0.000    0.000    0.000 {built-in method _thread.allocate_lock}
        1    0.000    0.000    0.000    0.000 threading.py:311(_acquire_restore)
        2    0.000    0.000    0.000    0.000 traitlets.py:3624(validate_elements)
        1    0.000    0.000    0.000    0.000 inspect.py:2949(apply_defaults)
        2    0.000    0.000    0.000    0.000 traitlets.py:708(__set__)
        1    0.000    0.000    0.000    0.000 inspect.py:3275(bind)
        8    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        1    0.000    0.000    0.000    0.000 traitlets.py:1523(notify_change)
        2    0.000    0.000    0.000    0.000 traitlets.py:2304(validate)
        1    0.000    0.000    0.000    0.000 history.py:839(_writeout_output_cache)
        1    0.000    0.000    0.000    0.000 inspect.py:2896(args)
        2    0.000    0.000    0.000    0.000 threading.py:302(__exit__)
        2    0.000    0.000    0.000    0.000 threading.py:299(__enter__)
        1    0.000    0.000    0.000    0.000 threading.py:308(_release_save)
        3    0.000    0.000    0.000    0.000 {method 'acquire' of '_thread.lock' objects}
       22    0.000    0.000    0.000    0.000 typing.py:2187(cast)
        7    0.000    0.000    0.000    0.000 {method 'discard' of 'set' objects}
        2    0.000    0.000    0.000    0.000 {built-in method numpy.zeros}
        4    0.000    0.000    0.000    0.000 {method '__exit__' of '_thread.lock' objects}
        1    0.000    0.000    0.000    0.000 threading.py:627(clear)
        1    0.000    0.000    0.000    0.000 {built-in method numpy.array}
        2    0.000    0.000    0.000    0.000 traitlets.py:3486(validate_elements)
        4    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 inspect.py:2919(kwargs)
        8    0.000    0.000    0.000    0.000 multiarray.py:1106(copyto)
        3    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        3    0.000    0.000    0.000    0.000 base_events.py:728(__del__)
        2    0.000    0.000    0.000    0.000 {method '__enter__' of '_thread.lock' objects}
        1    0.000    0.000    0.000    0.000 {method 'values' of 'mappingproxy' objects}
        4    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        2    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.iter}
        1    0.000    0.000    0.000    0.000 _stride_tricks_impl.py:24(_maybe_view_as_subclass)
       10    0.000    0.000    0.000    0.000 inspect.py:2808(kind)
        3    0.000    0.000    0.000    0.000 {method 'items' of 'mappingproxy' objects}
        1    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}
        1    0.000    0.000    0.000    0.000 threading.py:314(_is_owned)
        3    0.000    0.000    0.000    0.000 base_events.py:724(is_closed)
        4    0.000    0.000    0.000    0.000 inspect.py:3089(parameters)
        1    0.000    0.000    0.000    0.000 _stride_tricks_impl.py:19(__init__)
        1    0.000    0.000    0.000    0.000 {method 'release' of '_thread.lock' objects}
        4    0.000    0.000    0.000    0.000 inspect.py:2796(name)
        1    0.000    0.000    0.000    0.000 inspect.py:2888(__init__)
        1    0.000    0.000    0.000    0.000 multiarray.py:115(empty_like)
        1    0.000    0.000    0.000    0.000 numeric.py:92(_zeros_like_dispatcher)
        1    0.000    0.000    0.000    0.000 _index_tricks_impl.py:696(__iter__)

In [10]: prun test_numpy(180)
         64971 function calls in 9.433 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    9.187    9.187    9.187    9.187 {method 'reduce' of 'numpy.ufunc' objects}
        1    0.194    0.194    9.392    9.392 <ipython-input-4-d9bf266ea23e>:1(test_numpy)
        2    0.014    0.007    0.016    0.008 {method '__exit__' of 'sqlite3.Connection' objects}
        1    0.012    0.012    0.014    0.014 {method 'execute' of 'sqlite3.Connection' objects}
        1    0.011    0.011    9.403    9.403 <string>:1(<module>)
    32401    0.008    0.000    0.014    0.000 _index_tricks_impl.py:715(__next__)
    32407    0.006    0.000    0.006    0.000 {built-in method builtins.next}
        1    0.000    0.000    0.000    0.000 {built-in method numpy.empty}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    9.403    9.403 {built-in method builtins.exec}
        2    0.000    0.000    0.000    0.000 traitlets.py:718(_validate)
        5    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
        1    0.000    0.000    0.030    0.030 history.py:845(writeout_cache)
        1    0.000    0.000    0.000    0.000 traitlets.py:1527(_notify_observers)
        1    0.000    0.000    0.030    0.030 history.py:833(_writeout_input_cache)
        2    0.000    0.000    0.000    0.000 traitlets.py:3631(set)
        1    0.000    0.000    0.000    0.000 _stride_tricks_impl.py:37(as_strided)
        1    0.000    0.000    0.000    0.000 _index_tricks_impl.py:688(__init__)
        2    0.000    0.000    0.000    0.000 traitlets.py:689(set)
        2    0.000    0.000    0.000    0.000 traitlets.py:727(_cross_validate)
        2    0.000    0.000    0.000    0.000 traitlets.py:3474(validate)
        1    0.000    0.000    0.000    0.000 inspect.py:3133(_bind)
        2    0.000    0.000    0.000    0.000 traitlets.py:3624(validate_elements)
        1    0.000    0.000    0.000    0.000 numeric.py:98(zeros_like)
        1    0.000    0.000    0.000    0.000 traitlets.py:1512(_notify_trait)
        6    0.000    0.000    0.000    0.000 traitlets.py:676(__get__)
        1    0.000    0.000    9.187    9.187 {method 'sum' of 'numpy.ndarray' objects}
        2    0.000    0.000    0.000    0.000 traitlets.py:708(__set__)
        2    0.000    0.000    0.000    0.000 traitlets.py:2304(validate)
        1    0.000    0.000    0.000    0.000 traitlets.py:1523(notify_change)
        8    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        6    0.000    0.000    0.000    0.000 traitlets.py:629(get)
        1    0.000    0.000    0.000    0.000 {built-in method _thread.allocate_lock}
        1    0.000    0.000    0.000    0.000 decorator.py:200(fix)
        1    0.000    0.000    0.030    0.030 decorator.py:232(fun)
        1    0.000    0.000    0.000    0.000 _weakrefset.py:39(_remove)
        1    0.000    0.000    0.000    0.000 history.py:839(_writeout_output_cache)
        1    0.000    0.000    9.187    9.187 _methods.py:49(_sum)
        1    0.000    0.000    0.030    0.030 history.py:55(only_when_enabled)
        1    0.000    0.000    0.000    0.000 inspect.py:2949(apply_defaults)
        1    0.000    0.000    0.000    0.000 inspect.py:3275(bind)
        4    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
       22    0.000    0.000    0.000    0.000 typing.py:2187(cast)
        2    0.000    0.000    0.000    0.000 threading.py:299(__enter__)
        1    0.000    0.000    0.000    0.000 {built-in method numpy.asarray}
        2    0.000    0.000    0.000    0.000 traitlets.py:3486(validate_elements)
        1    0.000    0.000    0.000    0.000 threading.py:311(_acquire_restore)
        4    0.000    0.000    0.000    0.000 {method '__exit__' of '_thread.lock' objects}
        1    0.000    0.000    0.000    0.000 threading.py:308(_release_save)
        2    0.000    0.000    0.000    0.000 {built-in method numpy.zeros}
        3    0.000    0.000    0.000    0.000 {method 'acquire' of '_thread.lock' objects}
        2    0.000    0.000    0.000    0.000 {method '__enter__' of '_thread.lock' objects}
        1    0.000    0.000    0.000    0.000 inspect.py:2896(args)
        2    0.000    0.000    0.000    0.000 threading.py:302(__exit__)
        3    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        2    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
        1    0.000    0.000    0.000    0.000 threading.py:627(clear)
        1    0.000    0.000    0.000    0.000 inspect.py:2919(kwargs)
        1    0.000    0.000    0.000    0.000 {method 'values' of 'mappingproxy' objects}
        1    0.000    0.000    0.000    0.000 {method 'discard' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {built-in method numpy.array}
       10    0.000    0.000    0.000    0.000 inspect.py:2808(kind)
        1    0.000    0.000    0.000    0.000 threading.py:314(_is_owned)
        3    0.000    0.000    0.000    0.000 {method 'items' of 'mappingproxy' objects}
        4    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.iter}
        1    0.000    0.000    0.000    0.000 {method 'release' of '_thread.lock' objects}
        1    0.000    0.000    0.000    0.000 _stride_tricks_impl.py:24(_maybe_view_as_subclass)
        4    0.000    0.000    0.000    0.000 inspect.py:3089(parameters)
        4    0.000    0.000    0.000    0.000 inspect.py:2796(name)
        1    0.000    0.000    0.000    0.000 inspect.py:2888(__init__)
        1    0.000    0.000    0.000    0.000 multiarray.py:1106(copyto)
        1    0.000    0.000    0.000    0.000 _stride_tricks_impl.py:19(__init__)
        1    0.000    0.000    0.000    0.000 numeric.py:92(_zeros_like_dispatcher)
        1    0.000    0.000    0.000    0.000 multiarray.py:115(empty_like)
        1    0.000    0.000    0.000    0.000 _index_tricks_impl.py:696(__iter__)

In [11]: prun test_dict(180)
         32371 function calls in 0.252 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.140    0.140    0.145    0.145 <ipython-input-5-60ba8a587fa8>:1(test_dict)
        1    0.049    0.049    0.049    0.049 history.py:833(_writeout_input_cache)
        1    0.047    0.047    0.047    0.047 {method 'execute' of 'sqlite3.Connection' objects}
        1    0.011    0.011    0.156    0.156 <string>:1(<module>)
    32221    0.005    0.000    0.005    0.000 <ipython-input-5-60ba8a587fa8>:9(<genexpr>)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.096    0.096 history.py:845(writeout_cache)
        1    0.000    0.000    0.000    0.000 inspect.py:3133(_bind)
        2    0.000    0.000    0.000    0.000 {method '__exit__' of 'sqlite3.Connection' objects}
        1    0.000    0.000    0.000    0.000 decorator.py:200(fix)
        1    0.000    0.000    0.252    0.252 {built-in method builtins.exec}
        2    0.000    0.000    0.000    0.000 traitlets.py:3631(set)
        1    0.000    0.000    0.000    0.000 inspect.py:2919(kwargs)
        1    0.000    0.000    0.000    0.000 _weakrefset.py:39(_remove)
        1    0.000    0.000    0.096    0.096 history.py:55(only_when_enabled)
        6    0.000    0.000    0.000    0.000 traitlets.py:676(__get__)
        1    0.000    0.000    0.000    0.000 traitlets.py:1527(_notify_observers)
        1    0.000    0.000    0.000    0.000 inspect.py:2949(apply_defaults)
        6    0.000    0.000    0.000    0.000 traitlets.py:629(get)
        2    0.000    0.000    0.000    0.000 traitlets.py:3624(validate_elements)
        2    0.000    0.000    0.000    0.000 traitlets.py:718(_validate)
        2    0.000    0.000    0.000    0.000 traitlets.py:689(set)
        1    0.000    0.000    0.000    0.000 threading.py:311(_acquire_restore)
        1    0.000    0.000    0.000    0.000 inspect.py:3275(bind)
        1    0.000    0.000    0.096    0.096 decorator.py:232(fun)
        1    0.000    0.000    0.000    0.000 {built-in method _thread.allocate_lock}
        2    0.000    0.000    0.000    0.000 traitlets.py:3474(validate)
        5    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
        2    0.000    0.000    0.000    0.000 traitlets.py:727(_cross_validate)
        1    0.000    0.000    0.000    0.000 inspect.py:2896(args)
        1    0.000    0.000    0.000    0.000 traitlets.py:1512(_notify_trait)
        2    0.000    0.000    0.000    0.000 threading.py:299(__enter__)
        6    0.000    0.000    0.000    0.000 {built-in method builtins.next}
        2    0.000    0.000    0.000    0.000 traitlets.py:708(__set__)
        3    0.000    0.000    0.000    0.000 {method 'acquire' of '_thread.lock' objects}
        2    0.000    0.000    0.000    0.000 threading.py:302(__exit__)
        1    0.000    0.000    0.000    0.000 traitlets.py:1523(notify_change)
        7    0.000    0.000    0.000    0.000 {built-in method builtins.isinstance}
        2    0.000    0.000    0.000    0.000 traitlets.py:2304(validate)
        1    0.000    0.000    0.000    0.000 threading.py:627(clear)
       22    0.000    0.000    0.000    0.000 typing.py:2187(cast)
        1    0.000    0.000    0.000    0.000 history.py:839(_writeout_output_cache)
        1    0.000    0.000    0.000    0.000 {method 'values' of 'mappingproxy' objects}
        3    0.000    0.000    0.000    0.000 {method 'items' of 'mappingproxy' objects}
        4    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        4    0.000    0.000    0.000    0.000 {method '__exit__' of '_thread.lock' objects}
       10    0.000    0.000    0.000    0.000 inspect.py:2808(kind)
        4    0.000    0.000    0.000    0.000 inspect.py:3089(parameters)
        1    0.000    0.000    0.000    0.000 threading.py:308(_release_save)
        2    0.000    0.000    0.000    0.000 {built-in method builtins.iter}
        4    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
        2    0.000    0.000    0.000    0.000 traitlets.py:3486(validate_elements)
        2    0.000    0.000    0.000    0.000 {method '__enter__' of '_thread.lock' objects}
        1    0.000    0.000    0.000    0.000 threading.py:314(_is_owned)
        2    0.000    0.000    0.000    0.000 {method 'extend' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'discard' of 'set' objects}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        4    0.000    0.000    0.000    0.000 inspect.py:2796(name)
        1    0.000    0.000    0.000    0.000 inspect.py:2888(__init__)
        1    0.000    0.000    0.000    0.000 {method 'append' of 'collections.deque' objects}
        1    0.000    0.000    0.000    0.000 {method 'release' of '_thread.lock' objects}

In [12]:

Activity

  1. Zeroto521 commented on Sep 9, 2025

    @Zeroto521
    ContributorAuthor

    Could speed up via Cythonizing matrix.pxi?

  2. Zeroto521 commented on Sep 9, 2025

    @Zeroto521
    ContributorAuthor

    Or a simple solution to speed up via quicksum while input axis is None

    In [2]: from pyscipopt import Model, quicksum
    
    In [3]: def test_pyscipopt_sum(n):
       ...:     model = Model()
       ...:     sum(model.addMatrixVar((n, n), vtype="I").flat)
       ...:
    
    In [4]: def test_pyscipopt_quicksum(n):
       ...:     model = Model()
       ...:     quicksum(model.addMatrixVar((n, n), vtype="I").flat)
       ...:
    
    In [5]: timeit test_pyscipopt_sum(180)
    9.15 s ± 448 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    
    In [6]: timeit test_pyscipopt_quicksum(180)
    181 ms ± 24.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
    
    In [7]:
  3. changed the title [-]MatrixVariable is slower than list/dict in `sum` operation[/-] [+]`MatrixVariable.sum` is slower than `quicksum`[/+] on Sep 11, 2025
  4. Joao-Dionisio commented on Oct 5, 2025

    @Joao-Dionisio
    Member

    Hey @Zeroto521! We encountered this when first releasing the feature. You'll see there's a disabled test_performance in test_matrix_variable.py.

    You solutions does make sense, can you please open a PR?
    Sorry for taking so long reviewing, it's just a busy time, will continue in the foreseeable future.

  5. Joao-Dionisio commented on Oct 20, 2025

    @Joao-Dionisio
    Member

    Closing this to clear the issue page, but the benefit of the change is not clear, performance-wise.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions