Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
9 4
@bios8086_gitlab
@cprudhom Yes, I did this before, But I do not know how express not sub-sequence by group of element constraints
Charles Prud'homme
@cprudhom
the negation is related to pi variables. The element constraints remain the same but instead of (‘p1 < p2’ /\ ‘p2<p3’) you should post not(‘p1 < p2’ /\ ‘p2<p3’), that is: (‘p1 > p2’ or ‘p2>p3')
(in that case, pi can never be equal to pj)
9 4
@bios8086_gitlab
My concern is that using the element constraint will lose some values when the subarray's definition field is larger than the parent array. Let me use a simple example,
Here, the values 5,6 for the intVar are missing.
This is why I think it is impossible to obtain negation when using element constraints.
Charles Prud'homme
@cprudhom
then you should defined domain with all values but limit index to those possible
9 4
@bios8086_gitlab
Did you mean both IntVar[] have the same domain?
    IntVar intVar = choco_Model.intVar(1,longsize+2);
    IntVar[] intVars2Long =choco_Model.intVarArray(longsize,1, longsize+2);
Charles Prud'homme
@cprudhom
Well, the subsequence constraint, as I gave to you, consider that domains are equivalent
IntVar[] pos = ref().intVarArray(subsequence.length, 0, sequence.length);
        for (int i = 0; i < subsequence.length; i++) {
            ref().element(subsequence[i], sequence, pos[i], 0).post();
            if(i > 0){
                ref().arithm(pos[i-1], "<", pos[i]).post();
            }
        }
otherwise, indeed, you have a pb
9 4
@bios8086_gitlab
Yes, that is the point. if both IntVar[] have the same domain, there is no problem.
Charles Prud'homme
@cprudhom
but, your formulation is quite differente since you don’t want subsquence to be a subsequence of sequence (I should have chosen other names)
so I try something
9 4
@bios8086_gitlab
This formulation can give what I want
Is it possible to create a constraint using such code, instead of extending Propagator<IntVar>? If we can, we can directly using the not constraint.
Charles Prud'homme
@cprudhom
but that subsequence, right?
you can but if you look for performances, you will be disappointed
9 4
@bios8086_gitlab

I think so.

4,5,1, --- 3,2,4,5,1,
1,5,4, --- 3,2,1,5,4,
2,5,1, --- 3,4,2,5,1,
1,5,2, --- 3,4,1,5,2,
1,5,3, --- 4,2,1,5,3,
1,5,2, --- 4,3,1,5,2,
2,5,3, --- 4,1,2,5,3,
2,5,1, --- 4,3,2,5,1,
3,5,2, --- 4,1,3,5,2,
3,5,1, --- 4,2,3,5,1,

some solutions
Charles Prud'homme
@cprudhom
Here is my attempt (not tested):
// Collect all values
        IntIterableRangeSet set = new IntIterableRangeSet();
        for (int i = 0; i < sequence.length; i++) {
            set.addAll(sequence[i]);
            if (i < subsequence.length) {
                set.addAll(subsequence[i]);
            }
        }
        IntVar[] allValues = ArrayUtils.concat(sequence, Arrays.stream(set.toArray()).mapToObj(k -> ref().intVar(k)).toArray(IntVar[]::new));
        IntVar[] pos = ref().intVarArray(subsequence.length, 0, allValues.length);
        BoolVar[] lt = ref().boolVarArray(pos.length);
        for (int i = 0; i < subsequence.length; i++) {
            ref().element(subsequence[i], allValues, pos[i], 0).post();
            if (i > 0) {
                ref().reifyXgeY(pos[i - 1], pos[i], lt[i]);
            } else {
                ref().reifyXgtC(pos[0], sequence.length - 1, lt[i]);
            }
        }
        ref().addClausesBoolOrArrayEqualTrue(lt);
9 4
@bios8086_gitlab
I have never used ref() before.
Charles Prud'homme
@cprudhom
replaced it by model
there is a bug
9 4
@bios8086_gitlab
I have to leave, I will test your idea
Charles Prud'homme
@cprudhom
Well, the decomposition of notSubSequence is not straightforward. If I were you, I would rely on SetVar
9 4
@bios8086_gitlab
As far as I can imagine, SetVar cannot handle such a situation
1 2 3
3 2 1 4 5 7
If I use the intersection constraint, [1,2,3] and [3,2,1] will result in the same intersection
Charles Prud'homme
@cprudhom
You are right, the order is important (and I think we already talk about that)
9 4
@bios8086_gitlab
Yes, so SetVar is not useful in our case.
Charles Prud'homme
@cprudhom
// Collect all from sequence
        IntIterableRangeSet values = Arrays.stream(sequence)
                .map(IntIterableRangeSet::new)
                .collect(IntIterableRangeSet::new,
                        IntIterableRangeSet::addAll,
                        IntIterableRangeSet::addAll);
        IntVar[] copySsq = Arrays.stream(subsequence).map(v -> ref().intVar("C_" + v.getName(), values.toArray())).toArray(IntVar[]::new);
        IntVar[] pos = ref().intVarArray("P", subsequence.length, 0, copySsq.length);
        BoolVar[] nq = ref().boolVarArray("nq", subsequence.length);
        BoolVar[] np = ref().boolVarArray("np", subsequence.length-1);
        for (int i = 0; i < subsequence.length; i++) {
            ref().element(copySsq[i], sequence, pos[i], 0).post();
            ref().reifyXneY(subsequence[i], copySsq[i], nq[i]);
            if(i < subsequence.length - 1){
                ref().reifyXgtY(pos[i], pos[i+1], np[i]);
            }
        }
        ref().addClausesBoolOrArrayEqualTrue(ArrayUtils.concat(np, nq));
I think this one is correct
9 4
@bios8086_gitlab
OK. I will test it today
Thanks
By the way, do you think is it possible to apply count or among on SetVar without using auxiliary IntVar[] and Union?
Charles Prud'homme
@cprudhom
Could you be more precise?
Charles Prud'homme
@cprudhom
The last decomposition is not correct
9 4
@bios8086_gitlab
For a SetVar, how do I restrict the number of elements in the SetVar whose value are greater than x?
Charles Prud'homme
@cprudhom
I don’t know :)
9 4
@bios8086_gitlab
@cprudhom Thanks
9 4
@bios8086_gitlab
    Model model = new Model("Two");
    BoolVar g1 = model.boolVar("g1");
    BoolVar g2 = model.boolVar("g2");

    model.addClausesBoolOrArrayEqualTrue(new BoolVar[] {g1,g2});
    model.or(new BoolVar[] {g1,g2}).post();
What is the difference between addClausesBoolOrArrayEqualTrue and Or? I tested them and they give the same result. Could it be that addClausesBoolOrArrayEqualTrue is using SAT solver?
Charles Prud'homme
@cprudhom
That is exactly that
9 4
@bios8086_gitlab
@cprudhom So addClausesBoolOrArrayEqualTrue has better performance?
The implantation of Or uses the sum constraint
9 4
@bios8086_gitlab

What is the purpose of the constraint?

model.lexChainLess(intVars2Long).post();

The above constraint does not filter out any possible permutations. The solution set is not changed, compare to not posting this constraint.

9 4
@bios8086_gitlab
Does Choco have the weights constraints that is defined for SetVar? Gecode (see Page 90 of the user guide) has it.
It works like this way:
For example, the upper bound of the set = {1,3,4,5,7,9}, it's corresponding coefficients is {-1.4.1.1.3.3}
if the set variable is {3,7,9}, then the sum of the set is
4+3+3
9 4
@bios8086_gitlab
@cprudhom I cheeked the link before you gave me. It seems the choco implementation is different from the link. I will check it again.
Charles Prud'homme
@cprudhom
@bios8086_gitlab you are right, there is no weight for setvars (yet?)
@bios8086_gitlab watch out, there are 2 constraints with close names: lexChainLess and lexLess