by

Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
Charles Prud'homme
@cprudhom
@sudeep30m If you load javadoc in your IDE, you will see the following
A geometrical cutoff strategy. It is based on two parameters: g for geometricalFactor and s for scaleFactor. At step n, the next cutoff is computed with the following function : s*g^n Example with s=1 and g=1.3: 1, 2, 2, 3, 3, 4, 5, 7, 9, 11, 14, 18, 24, 31, 40, ...
JerrySwan
@JerrySwan
Hi! Is there any built-in support in the Java lib for parsing lzma-compressed XML?
Charles Prud'homme
@cprudhom
@JerrySwan Do you intent to parse an XCSP3 file ? If true, you have to install a LZMA lib, that should be enough
Conor McGann
@mcgannc

Hello. I have been using CHOCO for task planning and scheduling and constructed a scenario with inconsistent constrains between time points. It operates in Integer intervals for variables with very large domains.

The following code sample reproduces the problem (MAX_INT is (int) Integer.MAX_VALUE / 2).

Is there a better way to post such constraints to propagate them in aggregate rather than incrementally. For example, in other solvers I have used simple temporal networks which would efficiently detect such a problem.

@Ignore("Does not converge in reasonable time") public void testCycle(){
Model model = new Model("Cycle");

IntVar a = model.intVar("a", 0, EngineUtil.MAX_INT);
IntVar b = model.intVar("b", 0, EngineUtil.MAX_INT);
IntVar c = model.intVar("c", 0, EngineUtil.MAX_INT);

// This is inconsistent but incremental propagation is very bad at converging quickly on a fixed point.
b.gt(a).post();
b.eq(c).post();
a.eq(c).post();

try {
  model.getSolver().propagate();
}
catch(ContradictionException e){
  e.printStackTrace();
}

}

Charles Prud'homme
@cprudhom
@mcgannc Hi, I’m afraid there is no automatic way to tackle this problem. Indeed, your example is stressing the propagation engine: it will need to empty a domain to detect failure. This is achieved at root node (ie, no decision needed) but requires (at least) MAX_INT*3 events. There is no detection of such cases, here you would except choco-solver to induce a = b which is not consistent with b>a (and even if you posted a = b, the failure detection will be very long too). I have no turnkey solution.
Conor McGann
@mcgannc
@cprudhom I figured. A solution would be to use a Simple Temporal Network. For example: https://github.com/nasa/europa/tree/master/src/PLASMA/TemporalNetwork/base.
Charles Prud'homme
@cprudhom
@mcgannc that’s relevant, would you consider contributing to choco-solver ?
Conor McGann
@mcgannc
@cprudhom I would if I implement it - for sure. And if I do go for it I might reach out to you first to check the approach so it is integrated correctly, or however you like to co-ordinate such things :-)
Charles Prud'homme
@cprudhom
@mcgannc Deal! I can check your approach and give you feedback. We now use Pull Request for that kind of integration, but it is not mandatory.
rohel01
@rohel01
Hi, I am considering choco-solver to optimize a resource optimization problem. In my current implementation, I limit the search space by enforcing the zero-sum game in my "decisions". This means my solver must considers several variables at once and update their values such as their sum remain constant.
I know I can enforce the zero-sum game with a constraint, but I found this search method to be most efficient. How would I implement this in choco-solver ?
In the javadoc, AbstractStrategy seems to consider decisions based on single variables. What am I missing ?
Charles Prud'homme
@cprudhom
@rohel01 that will not be easy to achieve this based on a search strategy. Indeed, a search strategy provides a decision (ie, one variable, one operator and one value) on a call to getDecision. This method is called once at a time. In other words, you cannot restrict more than one variable at a time with a search strategy. On the other hand a constraint would be able to filter impossible values.
rohel01
@rohel01
@cprudhom Ok, thank you
Peer Jüttner
@peerjuettner

Hi. I'm new to choco solver. I have a model with the following statistics:

Choco 4.10.2 (2019-10) : Constraint Programming Solver, Copyright (c) 2010-2019
- Model[Model-0] features:
    Variables : 87275
    Constraints : 19585
    Building time : 9.097s
    User-defined search strategy : yes
    Complementary search strategy : no

I'd like to know if the number of Variables and Constraints is problematic. I use

        while(solver.solve()){
            solver.showShortStatistics();
            chocoCallback.OnChocoCallback(....);  // print stuff here
        }

to print out the results of the solution in my custom callback handler.

Addition 1: Also, I have a minimize objective in my code. I consolidate a large number of variables into a single cost variable and try to minimize. I feel like this is the problem, as without it I get solutions in a reasonable amount of time (Start coming in after a few minutes).

Charles Prud'homme
@cprudhom
@peerjuettner haven't you already asked this question on choco’s google group?
Peer Jüttner
@peerjuettner
Yes, In the end I posted there after not recieving an answer here.
João Pedro Schmitt
@schmittjoaopedro

Hello everyone,

Is there a date to release choco 4.10.3? I am waiting for the new equation() API.

Charles Prud'homme
@cprudhom
sorry, not yet. I hope I can find time by the end of June
Fabien Hermenier
@fhermeni
Hello. @cprudhom , there is an idiomatic way to plug constraints only a certain set of variables are instantiated ? So when we backtrack up to the points to at least once is no longer instantiated, the constraints are removed
1 reply
Charles Prud'homme
@cprudhom
@fhermeni I’m affraid there is no such possibility
you can post temporary a constraint based on a monitor
so the constraint will be removed on backtrack
Fabien Hermenier
@fhermeni
I thought about that. I'll have to track the status of the variables I am focusing on
Do you think that using a propagator to do so is more hacky ? Using the propagator, I am notified only when the variables I am interested in are instantiated. Then I can post/unpost accordingly ?
Charles Prud'homme
@cprudhom
Yes, that’s an option
or using a Variable monitor
Fabien Hermenier
@fhermeni
With n variable monitors (on per variable of interest), I am afraid of not being able to unpost the constraints automatically on backtrack
Charles Prud'homme
@cprudhom
that’s true
a propogator is a good trade-off
Fabien Hermenier
@fhermeni
Ok. If it makes sense, I can provide the resulting code to you (or maybe it is too specific)
Charles Prud'homme
@cprudhom
I’m affraid that’s a bit specific
Except if you declare a kind of implication propagator, that sets a boolean variables to True when all are instantiated ?
or a counter variable?
Fabien Hermenier
@fhermeni
what I add in mind is "onInstantiation(IntVar[] vars, () => {})" as I need to interact with plenty of things so I don't think I can just pass the constraints as parameters
In fact, I will generate the constraints
Charles Prud'homme
@cprudhom
but you could reify the constraints..?
Fabien Hermenier
@fhermeni
That was a guess but I am worried about the complexity of the reification. And I still cannot generate the constraints to post temporary upfront
In practice, once a placement decided, some extra scheduling constraint (precedences or cumulatove) to post depending on the resulting placement
Charles Prud'homme
@cprudhom
keep in mind that some constraints have internal data structures that may pollute the memory
Fabien Hermenier
@fhermeni
you mean that once the constraint is removed I may not be able to claim the memory again ?
so unused but not GCeable ?
Charles Prud'homme
@cprudhom
Backtrackable structures are freeed
the root node may be very big
but since no new modifi ation occurs, it's only at root node
João Pedro Schmitt
@schmittjoaopedro

Hello, I've a question related to tuple constraints:

The following source code:

Model model = new Model();
 IntVar x = model.intVar(new int[]{1, 2, 3, 4});
IntVar y = model.intVar(new int[]{1, 2, 3, 4});

Tuples tuples = new Tuples();
tuples.add(1, 1);
tuples.add(1, 2);
tuples.add(1, 3);
tuples.add(1, 4);
model.table(x, y, tuples).reify().eq(0).post();

model.getSolver().propagate();

System.out.println(x);
System.out.println(y);

It shouldn't remove the value 1 from X domain due to the reification to false?

Charles Prud'homme
@cprudhom
No, it can’t. By default a reification constraint only check for a constraint to be satisfied or not, calling the isEntailed of each of its propagators. In some specific cases, we were able to provide the opposite of a constraint. That is not the case of Table constraint. But, since you are using extension constraints, you can programmatically reified them by declaring a new dimension to the tuple, and a new variable as scope like:
Model model = new Model();
        IntVar x = model.intVar(new int[]{1, 2, 3, 4});
        IntVar y = model.intVar(new int[]{1, 2, 3, 4});
        BoolVar b = model.boolVar();
        int STAR = 99;

        Tuples tuples = new Tuples();
        tuples.setUniversalValue(STAR);
        tuples.add(1, 1, 1);
        tuples.add(1, 2, 1);
        tuples.add(1, 3, 1);
        tuples.add(1, 4, 1);
        tuples.add(2, STAR, 0);
        tuples.add(3, STAR, 0);
        tuples.add(4, STAR, 0);
        model.table(new IntVar[]{x, y, b}, tuples).post();
        b.eq(0).post();

        model.getSolver().propagate();

        System.out.println(x);
        System.out.println(y);
João Pedro Schmitt
@schmittjoaopedro

I was confusing about it because of this paper "Efficient Reification of Table Constraints" (10.1109/ICTAI.2017.00029), where the authors present a reification algorithm for table constraints (Algorithm 1). In that algorithm, given c as a table constraint and b as a reification variable of c, they mention the enforcement of GAC on contraint c if b = 1 or not (c) if b = 0.

I'm researching about it because I'm considering integrate the choco-solver with SQL (RDMS) to maintain positive table contraints, the reference is this paper "CSP Techniques for Solving Combinatorial Queries within Relational Databases" (https://doi.org/10.1007/978-3-642-04170-9_6 ), and I was struggling with the implementation of reification.

Based on my research and in choco source code, because my SqlTablePropagator will work the same way asTuples, I decided to implement the same isEntailedlogic of Tuples.java. However, instead of checking the tuples in memory for validation, I query the database to get this information.

@Override
    public ESat isEntailed() {
        ESat entailed;
        if (nbTuples == 0) {
            entailed = ESat.FALSE;
        } else if (!areAllVariablesInstantiated()) {
            entailed = ESat.UNDEFINED;
        } else if (getNumberValidTuples() == 1) {
            entailed = ESat.TRUE;
        } else {
            entailed = ESat.FALSE;
        }
        return entailed;
    }
Charles Prud'homme
@cprudhom
In the first article you pointed, the authors give an algorithm to enforce GAC on a reified table constraint. This algorithm is not part of Choco-solver. If you feel like code it and pushing it, it will be welcome. I believe the most difficult part is to get the tuples, since most of the time, in Choco, we encode them in a more convenient structure...
In addition, you still have to provide the opposite of c