chocoteam/pychoco

PyChoco

Python bindings for the Choco Constraint programming solver (https://choco-solver.org/).

Choco-solver is an open-source Java library for Constraint Programming (see https://choco-solver.org/). It comes with many features such as various types of variables, various state-of-the-art constraint, various search strategies, etc.

The PyChoco library uses a native-build of the original Java Choco-solver library, in the form of a shared library, which means that it can be used without any JVM. This native-build is created with GraalVM native-image tool.

We heavily relied on JGraphT Python bindings source code to understand how such a thing could be achieved, so many thanks to JGraphT authors!

Installation

We automatically build 64-bit wheels for Python versions 3.6, 3.7, 3.8, 3.9, and 3.10 on Linux, Windows and MacOSX. They can be directly downloaded from PyPI (https://pypi.org/project/pychoco/) or using pip:

pip install pychoco

Documentation

If you do not have any knowledge about Constraint Programming (CP) and Choco-solver, you can have a look at https://choco-solver.org/tutos/ for a quick introduction to CP and to Choco-solver features. For this Python API, we also provide an API documentation which is available online at https://pychoco.readthedocs.io/ .

Quickstart

Pychoco's API is quite close to Choco's Java API. The first thing to do is to import the library and create a model object:

from pychoco import Model

model = Model("My Choco Model")

Then, you can use this model object to create variables:

intvars = model.intvars(10, 0, 10)
sum_var = model.intvar(0, 100)

You can also create views from this Model object:

b6 = model.int_ge_view(intvars[6], 6)

Create and post (or reify) constraints:

model.all_different(intvars).post()
model.sum(intvars, "=", sum_var).post()
b7 = model.arithm(intvars[7], ">=", 7).reify()

Solve your problem:

model.get_solver().solve()

And retrieve the solution:

print("intvars = {}".format([i.get_value() for i in intvars]))
print("sum = {}".format(sum_var.get_value()))
print("intvar[6] >= 6 ? {}".format(b6.get_value()))
print("intvar[7] >= 7 ? {}".format(b7.get_value()))

> intvars = [3, 5, 9, 6, 7, 2, 0, 1, 4, 8]
> sum = 45
> intvar[6] >= 6 ? False
> intvar[7] >= 7 ? False

Build from source

The following system dependencies are required to build PyChco from sources:

• GraalVM >= 22 (see https://www.graalvm.org/)
• Native Image component for GraalVM (see https://www.graalvm.org/22.1/reference-manual/native-image/)
• Apache Maven (see https://maven.apache.org/)
• Python >= 3.6 (see https://www.python.org/)
• SWIG >= 3 (see https://www.swig.org/)

Once these dependencies are satisfied, clone the current repository:

git clone --recurse-submodules https://github.com/chocoteam/pychoco.git

The --recurse-submodules is necessary as the choco-solver-capi is a separate git project included as a submodule (see https://github.com/chocoteam/choco-solver-capi). It contains all the necessary to compile Choco-solver as a shared native library using GraalVM native-image.

Ensure that the $JAVA_HOME environment variable is pointing to GraalVM, and from the cloned repository execute the following command:

sh build.sh

This command will compile Choco-solver into a shared native library and compile the Python bindings to this native API using SWIG.

Finally, run:

pip install .

And voilà !

Citation

Coming soon.

Getting help or contribute

If you have any questions about using the library, suggestions for improvements, or if you detect a bug, please open an issue.

pychoco's Issues

Error in propagation of Increasing and Decreasing global constraints when in negative context

The increasing and decreasing global constraints are not working properly when used in negative context, in implication and reification. A false value in the bv associated with it does not propagate a false value in the constraint.

I noticed that with the following constraint: increasing(x,y,z) -> p. The constraint is not satisfied in the resulting solution, with"increasing" being true while p being false.

I reduced it to just enforcing ~increasing(x,y,z) (reifying increasing(x,y,z) and then enforcing the bv to false), but it is still satisfied in the solution given.

Solution hinting

I saw that solution hinting is supported in JAVA.

Is it possible to have this also in the python API?

Currently adding Choco solver in CPMpy modeling library for python, and as CPMpy supports solution hinting, it would be nice to also have it with Choco.

Calling `y = model.setvar({}, {1,2,3,5,12}, name="y")` throws an error

This is because the fallback case does not manage the name:

def setvar(self, lb_or_value: Union[set, list], ub: Union[set, list, None] = None, name: Union[str, None] = None):
        """
        Creates a set variable taking its domain in [lb, ub], or a a constant setvar if ub is None.
        For instance [{0,3},{-2,0,2,3}] means the variable must include both 0 and 3 and can additionally include -2
        and 2.

        :param lb_or_value: Initial domain lower bound (contains mandatory elements that should be present in
            every solution). If ub is None, corresponds to the constant value of this variable.
        :param ub: Initial domain upper bound (contains potential elements)
        :param name: Name of the variable (optional).
        :return: A SetVar.
        """
        lb_handle = make_int_array(list(lb_or_value))
        if ub is None:
            if name is None:
                handle = backend.setvar_iv(self.handle, lb_handle)
            else:
                handle = backend.setvar_s_iv(self.handle, name, lb_handle)
        else:
            ub_handle = make_int_array(list(ub))
            if name is None:
                handle = backend.setvar_iviv(self.handle, lb_handle, ub_handle)
            else:

                handle = backend.setvar_s_iviv(self.handle, 
#--> here <--#, 
                                lb_handle, ub_handle) 
        return SetVar(handle, self)

Pip install problem on Mac M3 osx-arm64

Hi,

Problem with pip install pychoco :
ERROR: Could not find a version that satisfies the requirement pychoco (from versions: none)
ERROR: No matching distribution found for pychoco

Using Mac OS Apple Silicon M3 osx-arm64
python 3.10.13

ERROR: pychoco-0.1.2-cp310-cp310-macosx_12_0_x86_64.whl is not a supported wheel on this platform
(tried to run conda config --env --set subdir osx-64 but no effects)

No support for `IntExpressions`

https://choco-solver.org/docs/modeling/intexpressions/

`model.intvar` does not admit `bounded=True` parameter

This is not consistent with the Java API.
BUT, I can live with that.

Add entrypoints to IReificationFactory constraints

These are missing in the current version (https://github.com/chocoteam/choco-solver/blob/master/solver/src/main/java/org/chocosolver/solver/constraints/IReificationFactory.java)

To do this it will be necessary to:
- Implement entrypoints in the choco-solver-capi repository
- Add these entrypoints to the C backend and SWIG interface of pychoco (backend.h, backend.c, backend.i)
- Implement, document and test python methods relying on these entrypoints.

One can do`t = model.boolvar(2)`..

...Which does not seem very relevant.
Should be add some tests?

Unify solving methods

The current Python API is quite similar to the Java one. It might be nice to think about a unified solving API for Python, associated with only one documentation. Ideally, it should be easy to :

• Find one solution and get the values of any variable in the model.
• Find and store several solutions, and for each solution store the values of any variable in the model.
• Find one or several optimal solutions, retrieve the best solutions' variables' values, and eventually intermediary solutions.
• ... Any other idea ?

It may be worth it to think about a Pythonic way of doing it, maybe something not possible in Java, or not easily, but much more convenient and easy to remember for users.

Implies constraint

Currently in the Python API there is no constraint for implying. We have reification, but the ifThen etc constraints described in https://choco-solver.org/docs/modeling/constraints/ are not included.

Currently, to implement it in, I reify the lhs and rhs expressions and create an arithm constraint .arithm(lhs, "<=", rhs). However, this is not efficient, as it already has 2 reifications.

I think this and the time limit would be the 2 things that we would like more to be included, followed by the solution hinting maybe later.

We already have a working version, and we can update it when they are added.

Thank you a lot.

`model.intvars` with shape ?

Could this API be useful?

ws = model.intvars((5,6), -1, 1, name="ws")

instead of:

ws = [ model.intvars(6, -1, 1, name="ws_"+str(i)) for i in range(5) ]

Allow retrieval of setvar and graphvar values from solution objects

Currently this is only possible with intvars, which is problematic for optimization problems, where get_value() does not work.

Manage with enumerated

It should be possible to declare an int var with an enumerated domain like:

x = model.intvar([1,3,5])

No support for `model.addClauses`

https://choco-solver.org/docs/modeling/intconstraints/#sat-constraints

Make unit of time limit clearer

There is a time limit parameter in findSolution, findOptimalSolution and co, but the unit of this time limit is not indicated in the doc, nor configurable. I'm adding the timeLimit(String limit) version, but it would be nice to make this feature simple and clear, with only one option in the Python API.

`model.table` does not support universal values

See https://choco-solver.org/docs/modeling/intconstraints/#universal-value

Implement `set_objective()` in Model API

This is currently missing, and can be needed for optimization and visualization / analysis of intermediary solutions.

Printing variable domain by default

In the current version, when a variable is printed, it returns Choco IntVar ('IV_1') but it could be more convenient to print its domain, like 0 or [0,4] or {1, 3, 5}.

find_all_optimal_solutions bug

Running find_all_optimal_solutions gives the following error, which is due to a typo

solutions_list_handle = backend.find_all_optimal_solution(self.handle, objective.handle, maximize, stop)
E AttributeError: module 'pychoco.backend' has no attribute 'find_all_optimal_solution'. Did you mean: 'find_all_optimal_solutions'?

........\AppData\Roaming\Python\Python310\site-packages\pychoco\solver.py:204: AttributeError

Implement methods to instantiate Choco graph objects from networkx object

This will be very useful !

time_limit not working properly

One would expect that the time_limit parameter would be in seconds. However, it seems that it is in nanoseconds, meaning that in order to set a limit to 1 second, you need to specify time_limit = 1000000000.

Besides the fact that this can be confusing to users, it is also not handy as if you set the limit more than 2 seconds, as this is more than the maximum positive integer value that can be represented in 32 bits (i.e., 2147483647), which is the max int value in C and Java.

If I try to specify a limit more than 2147483647, I get the following error:

File "C:\Users\DTAI\AppData\Roaming\Python\Python310\site-packages\pychoco\backend.py", line 111, in time_counter
return _backend.time_counter(arg1, arg2)
OverflowError: in method 'time_counter', argument 2 of type 'long'

This makes the time_limit parameter not usable in practice.

name in `model.intvars`

When calling

vs = model.intvars(5, -1, 1,name="vs")
print(vs)

it shows:

[IntVar 'vs' = [-1, 0, 1],
 IntVar 'vs' = [-1, 0, 1],
 IntVar 'vs' = [-1, 0, 1],
 IntVar 'vs' = [-1, 0, 1],
 IntVar 'vs' = [-1, 0, 1]]

The expected names should be:

[IntVar 'vs_0' = [-1, 0, 1],
 IntVar 'vs_1' = [-1, 0, 1],
 IntVar 'vs_2' = [-1, 0, 1],
 IntVar 'vs_3' = [-1, 0, 1],
 IntVar 'vs_4' = [-1, 0, 1]]

like in the Java version.

Btw, I'm not sure all method names are consistent with Python snake-casing...

update .gitignore

Hi

Am i wrong to say that some files can be included in the .gitignore file ?
For instance:

• pychoco/backend.py
• pychoco/backend_wrap.c
• pychoco/*.so
  They are built each time build.sh is called and thus should not be parted of comited files.

Propagate method in python API

I saw that in the python api we cannot use the propagate function component. One may want to propagate all constraints without search for a solution, as it is described in the docs. Conveniently, in Java we can do it, using the propagate function via the solver. Can this be part of the python API too?