[Beginner] Constraint on array index

[Rémi]

Hello, I'm getting started with Choco3 (version 3.3.0) and constraint programming in general, and I'm having some trouble creating "good" constraints.

My actual problem is the following :
I have an array of objects which I have to sort, based on one of their property. Considering this property, some of the objects must be one after an other, while some of them can be anywhere.

It will probably be clearer with this simplified example :
You have an array of 10 objects [a,b,c,d,e,f,g,h,i,j] that you have to sort, and theses objects have a property which informs us about the order. So we know that :
- 'b' must be right after 'f'
- 'a' must be right after 'b'
- 'h' must be right after 'a'
- 'c' must be right after 'e'
- 'j' must be right after 'c'

Assuming this, we know that somewhere in the sorted array we must find theses two sequences : "f,b,a,h" and "e,c,j". Besides, 'd', 'g' and 'i' can be found at any place.
(this is NOT a problem about alphabetical sorting, theses are just placeholders objects names).

Possible correct outputs could be :
- [g,i,f,b,a,h,d,e,c,j]
- [f,b,a,h,i,d,g,e,c,j]
- [e,c,j,f,b,a,h,g,i,d]
- ...

So, from a code perspective, I was working with this :
MyObject objectList[] = {a,b,c,d,e,f,g,h,i,j};
IntVar result[] = VariableFactory.enumeratedArray("result", 10, 0, 9, solver); // with 0 <=> a, 1 <=> b, 2 <=> c, etc

The property is represented as an int which can take the following values :
- -1 : place doesn't matter
- any positive number : if there is an other object with a consecutive number, this object must be directly after the first one

In the previous example, we could have something like :
a = 16
b = 15
c = 5
d = -1
e = 4
f = 14
g = -1
h = 17
i = -1
j = 6

So there's what I was trying to implement (hence the name of the topic) :
for(int i = 0; i < objectList.lenght() - 1; i++)
{
for(int j = i + 1; j < objectList.lenght(); j++)
{
if(objectList[i].property == objectList[j].property + 1)
{
// TODO : Constraint implying that two "positions" within result, which would take the value of objectList[i] and objectList[j], would have to have two consecutive index values.
}
}
}

And I can't find out how to do this.
I think that the problem I have probably comes from the fact that I'm not going in the right direction. Maybe I should model the problem differently, maybe I'm trying to do something that's not possible with Choco3, maybe I've overlooked some basic stuff in Choco3 usage... That's why I'm here : finding answers :)

I know that the constraint can be made really simply by considering that result index corresponds to a specific object and that its value corresponds to the "order value", and then doing something like

solver.post(IntConstraintFactory.arithm(result[i], ">", result[j]));

But doing it in this way would cause me to have the same problem later for an other constraint, whereas with the way I presented first, the next constraint would be much easier to implement.
Maybe my whole problem modelling isn't good, and I shouldn't be in this situation. I really need advises here :)

[Charles Prud'homme]

HI Remi,

Sorry for the late reply, but this forum is dedicated to choco2, and not well watched.
In the future, prefer the forums of http://choco-solver.org/ or https://github.com/chocoteam/choco3.

Your request now. You tried to define conditions on activating constraints, that's typically related to reification.
Reifying a constraint consists in associated a boolean variable to the constraint which indicates whether (when equals to 1) or not (when equals to 0) the constraint is satisfied. Have a look at: http://choco-solver.org/user_guide/2_modelling.html#reifying-constraints

However, as far as I understand your problem, I would suggest to use a global constraint, such as regular, or cost-regular, in addition to reified constraints to model your problem. Or, if you feel like implementing your own constraint, it is certainly worth the cost.

Hope it helps,
CP

[Rémi]

Hello and thanks for your answer.

Yeah, I realized a bit late that it was a choco2 forum, but I didn't want to duplicate my post on an other forum since this one might have been (and have effectively been) answered :)

Thanks a lot for your lead on reification, that's going to help me a lot. I was feeling like I had missed something important, but since I couldn't put a name on it, it was hard to gather information about it.

See you around !