Originally posted by: qtbgo

Hello, all.
I have a non negative integer decision variable array X_i in domain 0..100. I want to implement a constraint on it such that all positive value are connected together without 0 in between.
For example, 000213300 is valid, 002013300 is invalid.
Sorry for my poor English and hope you can understand me.

Thanks in advance.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi

You can use the same practice as in Math Programming to model an interval on a line of integer. That is compute the minimum position, the maximum position and the length of the interval and tell max = min + length - 1. To achieve it you need to have a Boolean variable that expresses the fact the position is in the interval.

int N = ...; 

int ub = ... dvar 

int line[1..N] in 0..ub;   dexpr 

int isIn[p in 1..N] (line[p] != 0); dexpr minp = min(p in 1..N) (p - N - 1)*isIn[p] + (N+1) 
// isIn[p] ? p : N+1; dexpr maxp = max(p in 1..N) p*isIn[p]; dexpr len = sum(p in 1..N) isIn[p];   subject to 
{ maxp + 1 = minp + len; 
// the length

Anyway, this model supposes that at least one of the line variable is non zero. If you do not assume it, you must relax the constraint. As for the minp expression, we use a kind of bigM relaxation.

int N = ...; 

int ub = ... dvar 

int line[1..N] in 0..ub;   dexpr 

int isIn[p in 1..N] (line[p] != 0); dexpr minp = min(p in 1..N) (p - N - 1)*isIn[p] + (N+1) 
// isIn[p] ? p : N+1; dexpr maxp = max(p in 1..N) p*isIn[p];   dexpr present = max (p in 1..N) isIn[p]; 
// if not present min = N, max = 0 dexpr len = present*((sum(p in 1..N) isIn[p]) + N - 1) - N + 1; 
// present ? sum(p in 1..N) isIn[p] : -N + 1;   subject to 
{ maxp + 1 = minp + len; 
// the length

Hope that helps
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: qtbgo

Thank you very much, ggr.
It seems that it is more complex than I had expected according to your reply.
I had thought of using some logical constraints to express it, do you think if it is possible or less efficient?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi

Basically the piece of model I gave is standard for Integer Programming (whatever you use a MIP or CP techniques to solve it). If you need to limit yourself to a <<linear>> number of constraints (because N to big): I am not sure you can do better.

Anyway one could add a cubic redundant term in the model:

forall(i in 1..N, j in 1..N, k in 1 ..N: i < j && i < k && k < j) (isIn[i]*isIn[j] == 1) <= (isIn[k] == 1);

Actually, CPO allows to declare a model using temporal (scheduling) concepts that will do the job. That is, use the analogy between the line of integer and a temporal axis, and the continuity of Non Zero values with an interval variable.

int N = ...; 

int ub = ... dvar 

int line[1..N] in 0..ub;     dvar interval isIn[p in 1..N] optional in p..p+1 size 1; dvar interval beforeNonZero in 1..N+1; dvar interval nonZero in 1..N+1; dvar interval afterNonZero in 1..N+1;   
// the line as a cumulative function dexpr cumulFunction presence = sum (i in 1..N) pulse(isIn, 1);   subject to 
{   
// the line shape endAtStart(beforeNonZero, nonZero); endAtStart(nonZero, afterNonZero); alwaysIn(presence, nonZero, 1, 1); alwaysIn(presence, beforeNonZero, 0, 0); alwaysIn(presence, afterNonZero, 0, 0);   
// the connection between the cumulative function and the variables   forall(i in 1..N) presenceOf(isIn[i]) == (line[i] > 0); span(nonZero, isIn); 
// continuity constraint 
}

Anyway, the last model requires a search phase that excludes the interval variables from the search.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: qtbgo

Thank you, ggr. I get much from you. I wonder which method is more efficient when using cpo to solve.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: qtbgo

Hi, GGR, I figured out a way as following and it seems work.

forall(i in  1..N - 2) (line[i] != 0 && line[i + 1] == 0)  => sum(j in i+1..N)line[j] == 0;

It seems a more simple form. But I donnot know which method is most efficient.Any hints?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi

Actually, you're redundant constraint is quadratic. Simply weaker than the cubic redundant ones. That seems a quite good compromise. Do you try to also add the backward one?

forall(i in  3..N) (line[i-1] == 0 && line[i] != 0)  => sum(j in 1..i-2) line[j] == 0;

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi

I forgot something important in the discussion. In fact the best way is certainly the scheduling model for the continuity constraint but you actually do not need to use a interval based model that is, the code should be

forall(i in 1..N) (line[i] == 1) == ((minp <= i) && (i <= maxp))

Sorry for the mess.
#DecisionOptimization
#OPLusingCPOptimizer