1
$\begingroup$

Suppose we have an array of binary variables $\{x_{i,t,n}, \ \forall i \in I, t \in T, n \in N \}$. If we want to define a condition as, if any of $x_{i,t,n} = 1$ in an arbitrary index $i$, then the rest of the bigger index $i$ should be one. (E.g. if the card of index I would be six, then one of the possible solutions would be $\{0,0,1,1,1,1\}$. (For simplicity, I omitted the sets $T$ and $N$). I know there is a constraint as $x_{i,t,n} \leq x_{i+1,t,n}$, but as far as I test in some problems, it sorts the variables from the first position. For example in the scheduling problem when we want to deploy the resources respectively. Actually, I am not sure it can be used in general at all. I tried to write that in the following form, and I would like to know other insights regarding that.

$$ ((x_{i} \implies(x_{j} \land x_{k})) \bigvee (x_{j} \implies(\lnot x_{i} \land x_{k})) \bigvee (x_{k} \implies(\lnot x_{i} \land \lnot x_{j}))) \quad \forall i,j,k \in I: (i\lt j \lt k) $$

$\endgroup$
2
  • $\begingroup$ Is $I$ a set of consecutive integers? $\endgroup$
    – RobPratt
    Commented Sep 5, 2023 at 15:35
  • $\begingroup$ Dear @RobPratt, it may be or may not. For some of the examples it is and for others it is a set of strings. e.g. jobs ID. $\endgroup$
    – A.Omidi
    Commented Sep 5, 2023 at 16:19

1 Answer 1

2
$\begingroup$

Introduce an ordering $\text{ord}: I \to \{1,\dots,|I|\}$ and impose $$x_i \le x_j$$ for all $i\in I$ and $j\in I$ such that $\text{ord}_i + 1 = \text{ord}_j$.

An alternative, less efficient, approach with $O(|I|^2)$ constraints is $$x_i \le x_j$$ for all $i\in I$ and $j\in I$ such that $\text{ord}_i < \text{ord}_j$.

$\endgroup$
10
  • $\begingroup$ Dear @RobPratt, thank you so much for your attention. Would you please, how is it possible to use this when the set $I$ is strings? $\endgroup$
    – A.Omidi
    Commented Sep 5, 2023 at 19:20
  • $\begingroup$ And also may I have your insight about what I proposed? $\endgroup$
    – A.Omidi
    Commented Sep 5, 2023 at 19:21
  • 1
    $\begingroup$ The set $I$ can have arbitrary types (numbers, strings, tuples, etc.). You just need to define the ord mapping to indicate what it means for one index $i$ to be higher or lower than another. For strings, alphabetical order seems natural, but does that match your business rule? $\endgroup$
    – RobPratt
    Commented Sep 5, 2023 at 19:42
  • 1
    $\begingroup$ No, I mean to change the two $\bigvee$ symbols (logical OR) to $\bigwedge$ (logical AND) because each of the three clauses must hold independently. $\endgroup$
    – RobPratt
    Commented Sep 5, 2023 at 19:51
  • 2
    $\begingroup$ Glad to help. Minor quibble: that correction of $\bigvee$ to $\bigwedge$ would not still prohibit $(1,0)$ in the $|I|=2$ case because there is no $i<j<k$. $\endgroup$
    – RobPratt
    Commented Sep 5, 2023 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.