Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
  • Oct 06 11:18
    Travis chocoteam/choco-solver (master) fixed (1908)
  • Oct 06 10:33

    cprudhom on master

    Upgrade ibex-java to 1.2.0 (#74… (compare)

  • Oct 06 10:33
    cprudhom closed #741
  • Oct 05 18:54
    codecov-commenter commented #741
  • Oct 05 18:54
  • Oct 05 18:48
    codecov-commenter commented #741
  • Oct 05 18:47
    codecov-commenter commented #741
  • Oct 05 18:41
    codecov-commenter commented #741
  • Oct 05 18:38
    codecov-commenter commented #741
  • Oct 05 18:37
  • Oct 05 18:35
    codecov-commenter commented #741
  • Oct 05 18:30
    codecov-commenter commented #741
  • Oct 05 18:25
    codecov-commenter commented #741
  • Oct 05 18:19
    codecov-commenter commented #741
  • Oct 05 18:19
    codecov-commenter commented #741
  • Oct 05 18:12
    codecov-commenter commented #741
  • Oct 05 18:10
    codecov-commenter commented #741
  • Oct 05 18:05
    codecov-commenter commented #741
  • Oct 05 17:58
    codecov-commenter commented #741
  • Oct 05 17:58
    schmittjoaopedro synchronize #741
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
Lawrence Wagerfield
@ljwagerfield
What's the most efficient way to tell if a model has at least one solution? I can call model.getSolver.solve() which provides the answer, but is this most efficient, given I don't care about the values produced for any of the variables?
Charles Prud'homme
@cprudhom
@ljwagerfield No there is no alternative but calling solve(). If you are not satisfied by the time required to find such a solution, you can try to override the search strategy.
thomas-bee
@thomas-bee
Please excuse an absolute newbie question. I would like to schedule non-overlapping time intervals (telescope observations). Google's CP SAT solver provides an IntervalVar, consisting of two IntVars from/to and a duration. Would you have any pointer to an example or a hint how to express such intervals in Choco and the fact that they must not overlap?
Charles Prud'homme
@cprudhom
In Choco, we defined Tasks, a tasks is composed of a start, a duration and a end. Then you should have a look at the cumulative constraint
thomas-bee
@thomas-bee
Aah yes. Thanks a lot @cprudhom I will dig around with that
thomas-bee
@thomas-bee
Hmm. Not really getting what to do with the cumulative constraint. I have this (in Groovy), but I need to express that no task overlaps and exclude certain daytime intervals from the available slots.
        List<IntVar> intervalStarts = []
        observations.size().times { i ->
            IntVar start = model.intVar("OB $i from", 0, TOTAL_SLOTS - 1)
            IntVar end = model.intVar("OB $i to", 0,  TOTAL_SLOTS - 1)
            model.taskVar(start, observations[i].requestedNoOfSlots, end)
            intervalStarts.add(start)
        }
        model.allDifferent((IntVar[]) intervalStarts).post()
Charles Prud'homme
@cprudhom
The cumulative constraint is what you need (see, its formal definition here: https://sofdem.github.io/gccat/gccat/Ccumulative.html). If all tasks have a height equal to one and the capacity is set to one too, then you have a dijunctive constraint which ensures no overlapping. If you want to exclude some daytime intervals, simply create fixed task (ie, start time and duration are fixed).
thomas-bee
@thomas-bee
@cprudhom thanks a lot this is working great for me so far.
João Pedro Schmitt
@schmittjoaopedro

Hello,

Is there some kind of operation on choco that changes the behavior of double values? I'm having some troubles when running tests using a docker container (maven:3.6.3-openjdk-11-slim).

System.out.println(10.0, 6); // Prints: 1000000.0
model.getSolver().propagate(); 
System.out.println(10.0, 6); // Prints: 1000000.0000000001
Charles Prud'homme
@cprudhom
I suppose you added some constraints that may have a side effect, didn’t you?
João Pedro Schmitt
@schmittjoaopedro
maybe, I'm debugging to find the cause.
João Pedro Schmitt
@schmittjoaopedro
The cause is Ibex, I've made some tests, and after calling the build method from ibex it mess with java double definition.
Charles Prud'homme
@cprudhom
I suppose it refines the domain wrt to constraints...
João Pedro Schmitt
@schmittjoaopedro
What do you get for the following sysouts on your Linux environment?
Ibex ibex = new Ibex(new double[]{0.000001, 0.000001});
ibex.add_ctr("{0}=acos({1})");
System.out.println(Math.pow(10, 6)); // Prints: 1000000.0
ibex.build();
System.out.println(Math.pow(10, 6)); // Prints: 1000000.0000000001
Charles Prud'homme
@cprudhom
On Mac OSX:
1000000.0
1000000.0000000001
([-10000.0,10000.0] ; [-0.6,0.6])
After contract:
([0.9272952180016122,2.2142974355881813] ; [-0.6,0.6])
João Pedro Schmitt
@schmittjoaopedro
I see that it's a problem
I've no idea how to handle it in ibex integration
I will open a issue in GIT for this
thomas-bee
@thomas-bee
Hi. I am scheduling observations of variable duration into hourly slots, each night has 10 slots or so. This works beautifully using only IntVar and the cumulative constraint. Now some of those observations belong to groups that should be scheduled strictly together filling up one or several consecutive nights. Is there an obvious way to express this?
Charles Prud'homme
@cprudhom
you can try to link them together with some constraints (like conditional constraints)?
thomas-bee
@thomas-bee
Hmm. I was thinking that maybe, if, I have N observations that have to be consecutive and they require a total of M slots, and starts[index] represents the respective start of observation IntVars, would it then not work to require that the max(starts) - min(starts) === (M - 1). I just have no clue how to extract such max of IntVars as an intermediate, "fresh" variable? Maybe the distance constraint, but since it only takes 2 variables would I have to add a constraint for each combination?
Charles Prud'homme
@cprudhom
If you already know which observations have to be consecutive, you can consider creating a meta-observation, whose start=min(start) and end=start+sum(durations)
thomas-bee
@thomas-bee
Got it. Will try, thanks a lot.
thomas-bee
@thomas-bee
I am experiencing a weird issue, surely I am doing something really wrong. I am holding two not one references to the same IntVar, initialized before invoking the solver. After invoking the solver and finding a solution (returns true) the values of the two references are not the same anymore. Is the solver doing some magic to those variables?
Charles Prud'homme
@cprudhom
it shouldn’t
if you can define a MWE, that would be helpful
thomas-bee
@thomas-bee
will try
thomas-bee
@thomas-bee
never mind, my bad
bigangswan
@bigangswan

Dear All, I am currently try to solve a new problem using Choco solver which needs to use the core idea from classic example Traveling Salesman Problem in tutorials. The example will be modified to given a start city and find a path traverse all cities to the end given city. For example, define a start city0 and the end the path travel all cities to city1.
Based on the current example code, I introduced the code like
model.arithm(succ[0], "=", 0).post();
model.arithm(succ[C - 1], "=", 1).post();
but solver.solve() didn't find any solution. I even replaced the code
model.subCircuit(succ, 0, model.intVar(C)).post();

to:

model.subPath(succ, model.intVar(0), model.intVar(1), 0, model.intVar(C)).post();

but again solver.solve() didn't find any solution.

does any one can give idea how to modify the code to solve this problem change?