chocoteam/choco-solver

An open-source Java library for Constraint Programming

thomas-bee

@thomas-bee

In particular circumstances the Choco solver for my scheduling problem has rather poor performance and doesn't find solutions to rather simple cases which can easily be solved by hand. I think I need to adapt the search strategy. Is there a structured approach whereby I can analyze the performance of the search strategy and derive suitable changes (as there is for Optaplanner)

1 reply

Andrés Sánchez

@Drisicus

Hello! We have found a situation where there is a "java.lang.ArrayIndexOutOfBoundsException" while performing a "model.unpost(constraint)" where the constraint has been reified and introduced in another constraint.
Example:
Constraint A = model.arithm(...);
Constraint B = model.arithm(...);
Constraint C = model.arithm(A.reify(), "<=", B.refiy());

model.post(C);
model.solve();

model.unpost(C);
model.unpost(A);
model.unpost(B);

We have created a Git Issue: chocoteam/choco-solver#823

As a workaround we have unpost the propagator constraint
Arrays.stream(A.getPropagators()).filter(Objects::nonNull).map(Propagator::getConstraint).forEach(model::unpost);
Arrays.stream(B.getPropagators()).filter(Objects::nonNull).map(Propagator::getConstraint).forEach(model::unpost);

We think that the "ArrayIndexOutOfBoundsException" is a bug, and maybe there is another way of unposting this constraints or we are missing something.
Thank you!

2 replies

thomas-bee

@thomas-bee

@cprudhom This is what I meant in Optaplanner https://docs.optaplanner.org/8.11.1.Final/optaplanner-docs/html_single/index.html#benchmarker We have a really ridiculously simple scheduling example that can be easily solved by a human being in 5 min, to which Choco sometimes finds a solution in less than a second, and sometimes does not find a solution in 5min, and sure we experiment with SearchStrategies but we don't have a good understanding how to do that in a structured fashion.

Charles Prud'homme

@cprudhom

Personnaly, I use iRace for that type of benchmarking.
https://github.com/cran/irace

Can you have a look and tell me if that could fit your need? If so, I can share some configurations (based on slurm and MiniZinc)

thomas-bee

@thomas-bee

@cprudhom Thanks a lot. Sure we could give irace a try, would be great if you could share configurations

1 reply

Charles Prud'homme

@cprudhom

Sure, I will add the file I override to github

Charles Prud'homme

@cprudhom

Hi, that seems to be related to maven, not choco

Mikaël Capelle

@Holt59

Hi, I'm having some issues trying to implement a custom (redundant) propagator and thought someone could give me a hand around here. I want to filter the domain of a set of variables based on the domain of another set of variables, but only one way (e.g. I want to filter the domain of Y based on modifications on the domain of X, but not the opposite). I try creating a propagator by only passing variables X to the constructor but the explain() method fails (weak clause) since the variable whose domain became empty is not in the set of variables of the propagator. I tried passing both set of variables to the constructor, but then the solver seems to enter a broken state (some normal logs appear, and then I only see row with "73 0 NaN% 0 | 1 2s |"). How should I go about implementing such type of propagator?

Charles Prud'homme

@cprudhom

Hi Mickael, there are many things in your question.

The filtering rules
the explaining rules

The former is mandatory, the latter is optional.
Do you need to activate explanation or only filtering is ok?

Mikaël Capelle

@Holt59

Hi Charles, thanks for the response. The filtering is working (if by filtering you mean the filtering of domains inside propagate ?), only the explanation is failing (when I activate that particular propagator). I’d like to have explanations working globally since I had much better performances with them enabled when not using the propagator. I don’t know if it’s possible to disable computation of explanations for that particular propagator? Otherwise if there is a way to fix it?

Charles Prud'homme

@cprudhom

I suppose, a tuto on explanation would be the best option in your case.
I’m quite busy in the following days, so I won’t be able to do that…
Any chance looking at other propagators ‘explain’ method helps?

Mikaël Capelle

@Holt59

I will have a look at them. I’ll try on a toy problem and see if I can reproduce (and fix) the problem.

Charles Prud'homme

@cprudhom

When dealing with explanations, there can be lots of unexpected side-effects when an event is not correcty explained by a cause. And could not find time to develop a test framework for that (I did the same for testing correctness and completness of propagation 10 years ago)

9 4

@bios8086_gitlab

Hi, I want to use maven to compile Choco solver on my computer.
I used this command
mvn clean package -DskipTests
But it does not work. Here is the link of my screenshot.
https://scontent-ham3-1.xx.fbcdn.net/v/t39.30808-6/266220600_10160166406273470_5149142289681304647_n.jpg?_nc_cat=106&ccb=1-5&_nc_sid=730e14&_nc_ohc=hCWIALwXL0kAX8_0K5E&_nc_ht=scontent-ham3-1.xx&oh=00_AT-ovpZpXMOlIPb5ZXsNZmdPx4CUwzRtMvQk6XLEXpLVgg&oe=61B98F7D

Charles Prud'homme

@cprudhom

@bios8086_gitlab I think this is related to a wrong commit. Did you get the last version of the source code?

I just pushed a correction

9 4

@bios8086_gitlab

@cprudhom Thanks for your help. Yes. I get the latest version via git clone https://github.com/chocoteam/choco-solver.git
I am using the latest version. But I believe there is a bug in this latest version. The following code never stops

``` 
    int n = 2;
    Model model = new Model("all different");
    IntVar[] xs = model.intVarArray("Xs", n, 1, n);
    model.allDifferent(xs).post();
    Solver solver = model.getSolver();
    solver.setSearch(Search.activityBasedSearch(xs));
    //solver.setSearch(Search.domOverWDegRefSearch(xs));
    // 6. Launch the resolution process
    while (solver.solve()) {
        for (IntVar x : xs) {
            System.out.format("%3d", x.getValue());
        }
        System.out.println();
    }
```

Charles Prud'homme

@cprudhom

indeed...

Charles Prud'homme

@cprudhom

I have to check when this has stopped working.
In the meantime, you can: open an issue (please) and fix the code with: solver.setNoGoodRecordingFromSolutions(xs);

9 4

@bios8086_gitlab

@cprudhom how to open an issue?

Charles Prud'homme

@cprudhom

Clic on ‘new issue’ here

Charles Prud'homme

@cprudhom

@bios8086_gitlab I will push a fix but you did’nt submit issue

Brecht Derwael

@bderwael_gitlab

Hey guys, I solved a bug we were having in our code by using .eq(0) instead of .not() on a BoolVar. Is there a functional difference between the two?

Charles Prud'homme

@cprudhom

There shouldn’t. I’ll have a look

Charles Prud'homme

@cprudhom

Here are what I’ve found with the 2 models.
As you can see, the models are slightly different but the same solutions are found.
That might come from somewhere else.
If you can give me a minimal working example, that would be great.

Model with not()

Model model = new Model();        
BoolVar x = model.boolVar("x");   
BoolVar y = model.boolVar("y");   
x.not().imp(y.not()).post();         
System.out.printf("%s%n", model); 
Solver solver = model.getSolver();
solver.showShortStatistics();     
solver.findAllSolutions();

outputs:

 Model[Model-0]

[ 4 vars -- 1 cstrs ]
satisfaction  : undefined
== variables ==
x = [0,1]
y = [0,1]
not(x = [0,1])
not(y = [0,1])
== constraints ==
ARITHM ([x + not(y) >= 1])

Model[Model-0], 1 Solutions, Resolution time 0,013s, 3 Nodes (234,2 n/s), 0 Backtracks, 0 Backjumps, 0 Fails, 0 Restarts
Model[Model-0], 2 Solutions, Resolution time 0,021s, 4 Nodes (189,7 n/s), 1 Backtracks, 0 Backjumps, 0 Fails, 0 Restarts
Model[Model-0], 3 Solutions, Resolution time 0,022s, 5 Nodes (230,3 n/s), 3 Backtracks, 0 Backjumps, 0 Fails, 0 Restarts
Model[Model-0], 3 Solutions, Resolution time 0,022s, 5 Nodes (225,3 n/s), 5 Backtracks, 0 Backjumps, 0 Fails, 0 Restarts

Model with eq(0)

Model model = new Model();        
BoolVar x = model.boolVar("x");   
BoolVar y = model.boolVar("y");   
x.eq(0).imp(y.not()).post();         
System.out.printf("%s%n", model); 
Solver solver = model.getSolver();
solver.showShortStatistics();     
solver.findAllSolutions();

outputs:

 Model[Model-0]

[ 5 vars -- 1 cstrs ]
satisfaction  : undefined
== variables ==
x = [0,1]
y = [0,1]
not(y = [0,1])
(x=0) = [0,1]
not((x=0) = [0,1])
== constraints ==
ARITHM ([not((x=0)) + not(y) >= 1])

Model[Model-0], 1 Solutions, Resolution time 0,009s, 2 Nodes (231,4 n/s), 0 Backtracks, 0 Backjumps, 0 Fails, 0 Restarts
Model[Model-0], 2 Solutions, Resolution time 0,015s, 4 Nodes (274,6 n/s), 1 Backtracks, 0 Backjumps, 0 Fails, 0 Restarts
Model[Model-0], 3 Solutions, Resolution time 0,015s, 5 Nodes (333,7 n/s), 2 Backtracks, 0 Backjumps, 0 Fails, 0 Restarts
Model[Model-0], 3 Solutions, Resolution time 0,015s, 5 Nodes (324,6 n/s), 5 Backtracks, 0 Backjumps, 0 Fails, 0 Restarts

Brecht Derwael

@bderwael_gitlab

If you can give me a minimal working example, that would be great.

Alright thanks for checking, I'll try and come up with something and return with it :)

Brecht Derwael

@bderwael_gitlab

Turns out it was a bug in my own code. For context; I rely on variable names to give feedback to the user, but I did not properly traverse cste variables to find their original name. Thanks anyway though! :)

Charles Prud'homme

@cprudhom

👍

Mrunal Patel

@_MrunalPatel__twitter

Hello, I am new to chocosolver and constraint programming in general. I was reading the https://choco-solver.org/docs/modeling/variables/ and couldn't understand why someone would use view? Does defining view make computation faster then declaring variable from an arithmetic expression? Thanks!

Charles Prud'homme

@cprudhom

@_MrunalPatel__twitter Indeed, views limit the memory footprint : there is no need to define a domain for a view since it is mapped to another variable’s domain. That’s also reduce the number of constraints and slightly reduces the propagation loop

Mrunal Patel

@_MrunalPatel__twitter

ah cool, that makes sense. I am trying to model a problem that is a slight variation of bin packing so wanted to understand best practices before I go about coding it. Thanks @cprudhom!!

SysrtN7

@SystrN7

Hi, I'm a beginner with choco-solver and have some difficulties writing a functional model.

my vars

Hello I'm a beginner with choco-solver and I'm currently having trouble writing a working model.

Here is my problem:

I have 5 days of work (in my week).
I have 'b' offices.
I have 'u' user.
I have a boolean matrix that represents the days that users need an office for each day of work.

Each day of the week I have to find a desk for all users who need one.

My constraints:

Each user must have a desk.
Each user can only have one desk per day.
A person may not need a desk one or more days in the week.

Objective:

A user must change desks a minimum number of times in a week.

Here is an example of partially functional code:

//          Model Parameter
int numberOfDayInWeek = 5;

int numberOfDesk = 5;
int numberOfUser = 5;
Boolean[][] userAvaibility = {
       {false, true, true, true, true},
       {true, true, true, true, false},
       {true, true, true, false, true},
       {false, true, true, true, true},
       {true, true, true, true, false},
};

Model model = new Model("Desk attribution");



// Define a desk environment.
IntVar[][] varsDesk = model.intVarMatrix("Desk", numberOfDayInWeek, numberOfDesk, -1, numberOfUser, false); // Fix for desk is not affected

// Each User can be assigned to one desk per day
for (int i = 0 ; i < numberOfDayInWeek ; i++)
{
   model.post(model.allDifferent(varsDesk[i]));
}

//   Remove user for day how is work at home
for (int j = 0 ; j < numberOfDayInWeek ; j++)
{
   for (int i = 0 ; i < numberOfUser ; i++)
   {
       if (!userAvaibility[i][j])
           for (int b = 0 ; b < numberOfDesk ; b++)
               varsDesk[j][b].ne(i).post();
   }
}

Solver solver = model.getSolver();
solver.showStatistics();
solver.showSolutions();
solver.findAllSolutions();

I have two main problems.

I can't model one or more desks without users.
I can't evaluate the number of times a user changes desk in a week

SysrtN7

@SystrN7

I finally found solution.

Moustafa Said Hawchar

@mostafa1685_gitlab

Hello, I am trying to install the chocosolver I installed the maven library and the java but when I type the command make ( because I already have the makefile)
it gives me the following error.

Charles Prud'homme

@cprudhom

@mostafa1685_gitlab I suppose you are working with the source code. If you have installed maven 3+ and Java 8+, calling make should work.
Alternatively, you can run mvn clean install -DskipTests

Moustafa Said Hawchar

@mostafa1685_gitlab

ok thank you but now I tried to use the CHOCO as a library to my java script but it keeps giving me bad class file error

Charles Prud'homme

@cprudhom

Ok so the Makefile is only valuable with the source code.
If you wan’t to use choco as a library (with the jar file so), you have the choice to either download the jar file named choco-solver-4.10.8-jar-with-dependencies.jar (https://github.com/chocoteam/choco-solver/releases) or to define a maven-based project with choco-solver as a dependency (https://choco-solver.org/docs/getting-started/#quick-start)

Moustafa Said Hawchar

@mostafa1685_gitlab

I tried downloading the library but it keeps giving me error when I try to run the java script

Charles Prud'homme

@cprudhom

This is an issue related to Java not Choco specially

I can only encourage you to use an IDE (like Eclipse, Intellij IDEA) and no CLI if you are not familiar with it.

Mrunal Patel

@_MrunalPatel__twitter

Hello, I am getting this strange error when I am trying to maximize objective variable on one particular data set. Following is the code snippet which works correctly for other cases but seem to fail with objective variable not instantiated error on a new data set.

        final IntVar objective = m.intVar("objective", minObjective, maxObjective);
        m.sum(places, "<=", objective, places.length + 1).post();
         final Solution solution = new Solution(m);
        // objective
        m.setObjective(Model.MAXIMIZE, objective);
 // solve
        while (solver.solve()) {
            solution.record();
        }

objective variable (objective = {31..75}) is not instantiated on solution. Check constraints and/or decision variables.

11 replies

^ shouldn't it exit gracefully if solution was not found, or is the error trying to say something different?

Where communities thrive

People

Repo info

Activity