Python: Add many constraints more efficiently

[meyer89]

I use or-tools in Python for a model with many constraints and came across some limitations in the SWIG interface. It takes much longer creating the model than solving it.

I created an extended interface with Cython, which allows the creation of many constraints in a fraction of the previous time. However, I struggle a bit on how to integrate the Cython-Extension with ortools.

Arguments of MakeMatrixConstraint:

• solver: The ortools.linear_solver.pywraplp.Solver instance
• coefficients: double[:,:]/np.ndarray
• lin_expr: list with entry for each column containing anything which implements GetCoeffs()
• lb: double[:]/np.ndarray
• ub: double[:]/np.ndarray

Right now only dense matrices are supported, but scipy.csr_matrix could be also supported with an identical interface. However, that would add an dependency.

I have the Cython source file "ortools/linear_solver/python/matrix_constraints.pyx" and the header file "ortools/linear_solver/python/swigpyobject.h" for Pointer extraction from SWIG. I can build and run this with "python3 setup_extension.py build_ext --inplace" after "make python" and test it, but it should be either a separate package or maybe integrated into the standard ortools package.

You can find the mentioned files attached to this issue as patch file:
matrix_constraints.zip
It is a proof-of-concept and could be improved by using a C-Structure for the LinExpr. Right now there is still a Python call in each loop.

To give you an impression here is the runtime of the naive implementation in Python:

created Test problem with 500 vars
init_mat took 9.53 ms
add_expr took 8.09 ms
add_constraints took **6301.57 ms**

And the much faster version with MakeMatrixConstraint in Cython:

created Test problem with 500 vars
init_mat took 4.69 ms
add_expr took 6.21 ms
add_constraints took **86.67 ms**

The result of ExportModelAsLpFormat() is confirmed to be identical.

Any hint how to proceed on this issue is highly appreciated.

[lperron]

Thanks for the proposal.
We know we need to have a look.

[meyer89]

I just realized that I attached an empty file by accident. My proof of concept is attached to this comment now:
matrix_constraints.zip

[meyer89]

Time is passing on and so knowledge increases. I created a small wrapper in my free time, which works fine on Linux. On Windows the linking to the ortools library does not work.

pip install ortools cython numpy
pip install https://github.com/meyer89/orwrap/archive/master.zip

ref: https://github.com/meyer89/orwrap

Afterwards you can see the speedup with the following small test:

 python -m timeit -n 100 -s "import numpy as np; from orwrap.test.test_matrix_constraints import create_solver_fast as create; coef = np.tril(np.ones((100, 100))); lb = np.zeros(100); ub = np.zeros(100);" "create(coef, lb, ub)"

 python -m timeit -n 100 -s "import numpy as np; from orwrap.test.test_matrix_constraints import create_solver_slow as create; coef = np.tril(np.ones((100, 100))); lb = np.zeros(100); ub = np.zeros(100);" "create(coef, lb, ub)"

Right now I still don't know where this should go and I see multiple options:

• Integrate the feature into the ortools package
• Keep the package separate and add other community-provided functionality around ortools
• Leave this repository as a proof-of-concept how cython can be used to improve execution speed

[MartiMayo]

Any update on this issue? It would be a strong performance enhancer for the LP Solver

[lperron]

I have no knowledge of numpy and I am really not motivated to support cython. I would welcome pull requests to support numpy though :-) Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mer. 17 juin 2020 à 16:25, MartiMayo <notifications@github.com> a écrit :

…

Any update on this issue? It would be a strong performance enhancer for the LP Solver — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1020 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3NGZO7WGJ4ON3J5XB3RXDG5NANCNFSM4GRCU7IA> .

[meyer89]

I totally understand your hesitation to support cython, as it might really complicate building and testing ortools for different architectures and platforms. However, it seems like the easiest way to build a fast interface between Python and ortools backend.

The published code works fine since one year in productive software. The effort made the difference between "way too slow" and "blazing fast" and was definitely worth it.

My hope is that the code is useful for the community, as I benefit so much from the good contributions here and elsewhere. I would like to see it integrated into ortools and willing to improve the quality until it can be merged, but of course the feature must be wanted.

[programsfallapart]

@meyer89 Hi, could you please give me your email adress? I would like to ask you some questions :)

[meyer89]

You can ask any question under this issue, so these answered for everybody. You could also leave me your email adress and I can contact you.

[ssmofidi]

I am dealing with the same issue. building constraints takes a lot of time for large problems. Looking for ways to create constraints through matrices and/or arrays systematically. Has there been any enhancement since the last time?

[Mizux]

FYI:

1. LinearSolver MPsolver is not longer actively in development, but we continue the maintenance, support
2. MPSolver should be replaced with math_opt or model_builder as better alternative but currently both are still in early stage
3. We are moving from SWIG to pybind11 for Python wrappers (which provide support for numpy array)
4. math_opt currently doesn't provide a python pybind11 support

[leeek]

Is it possible to create constraints in a vectorized manner for CP-SAT in Python?

[lperron]

No. The protobuf is in python, and it is not really MT Safe. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le lun. 12 sept. 2022 à 17:29, leeek ***@***.***> a écrit :

…

Is it possible to create constraints in a vectorized manner for CP-SAT in Python? — Reply to this email directly, view it on GitHub <#1020 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3PI5G24CGVFWJGVO5DV55D6RANCNFSM4GRCU7IA> . You are receiving this because you commented.Message ID: ***@***.***>

[ion-elgreco]

How is this still not available? Having to call solver.add is very suboptimal.

[lperron]

as I said, the proto is in python. There are currently no technical solutions to speed up filling the cp-sat model. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le mer. 4 oct. 2023 à 17:09, Ion Koutsouris ***@***.***> a écrit :

…

How is this still not available? Having to call solver.add is very suboptimal. — Reply to this email directly, view it on GitHub <#1020 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3PO7QCQKRP4CS5MFF3X5V33HAVCNFSM4GRCU7IKU5DIOJSWCZC7NNSXTN2JONZXKZKDN5WW2ZLOOQ5TCNZUG4YDCNRYHAYQ> . You are receiving this because you commented.Message ID: ***@***.***>

[lperron]

How is this still not available? Having to call solver.add is very suboptimal.

you can send me a PR that implements it.

[ion-elgreco]

@lperron I don't code in C++, only python and Rust. Also it wouldn't be worthwhile to spend time on it for me since I don't use or-tools often enough :)

[lperron]

So please stay courteous. No sign of exasperation. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le mar. 16 janv. 2024 à 08:45, Ion Koutsouris ***@***.***> a écrit :

…

@lperron <https://github.com/lperron> I don't code in C++, only python and Rust. Also it wouldn't be worthwhile to spend time on it for me since I don't use or-tools often enough :) — Reply to this email directly, view it on GitHub <#1020 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3JUFA5NTNJS4XW2PWLYOYV3BAVCNFSM4GRCU7IKU5DIOJSWCZC7NNSXTN2JONZXKZKDN5WW2ZLOOQ5TCOBZGMZDCNJWGAZQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>