# Forcing the value of "consecutive" variables

 7 Sorry I cannot find a clearer title for this question. I have a constraint like the following: $$\sum_{t \in T} w_{t} \cdot y_{t} \geq A$$ where $$w_t$$ are given, positive weights, and $$y_t \in \{0,1\}$$. I want to add (if possible) the following constraint: all the non-zero $$y_t$$ must be consecutive . That is, this is a valid solution: $$y_{t} = \dots 0,0,1,1,1,0,0\dots$$ while this is not: $$y_{t} = \dots 0,1,0,1,1,0,0\dots$$ The problem I find is that I don't know a priori how many $$y$$ will be non-zero. asked 01 Feb '14, 18:27 Libra 209●8 accept rate: 0% Could you please tell me what your application is and why it is important to have consecutive ones? (02 Feb '14, 22:18) Austin Buchanan (03 Feb '14, 05:01) fbahr ♦ @Austin @fbahr yes, I am trying to model a resource scheduling problem. The non pre-emptiveness came as a later requirements. I am looking at different formulations. (03 Feb '14, 06:40) Libra

 11 $T \cdot (1 - x_i + x_{i+1}) ~\geq \sum_{j = i+1}^T x_j \quad, ~\forall ~i = 1 \ldots T-1$ $\begin{array}[t]{cccc} x_i & x_{i+1} & & LHS & & RHS\\ 0 & 0 & \rightarrow & T & \geq & [0, T-1]\\ 0 & 1 & \rightarrow & 2T & \geq & [1, T-1]\\ 1 & 0 & \rightarrow & 0 & \geq & 0\\ 1 & 1 & \rightarrow & T & \geq & [1, T-1]\\ \end{array}$ doesn't introduce aux. variables (just like the approach @Austin suggested), and requires only $$T-1$$ constraints. In fact [and contrary to my initial estimate], this approach is both more memory efficient and faster*. *P.S.: Here, "faster" means: the solvers I've tried (CPLEX, Gurobi) solve [AMPL] model A significantly faster than model B. Model A: set T = 1 .. 100; # solved in a few seconds, # even for |T| = 1000: less than 1 min; Gurobi/NEOS param w {T} = Uniform01(); param A = 10; var y {T} binary; minimize obj: sum {t in T} y[t]; s.t. weight: sum {t in T} w[t] * y[t] >= A; s.t. consecutive_ones {i in T: i < card(T)}: card(T) * (1 - y[i] + y[i+1]) >= sum {t in T: t >= i+1} y[t];  Model B: set T := 1 .. 100; # takes 5-10 times longer than model A, # |T| = 400 >> out of memory @ NEOS param w {T} = Uniform01(); param A = 10; var y {T} binary; minimize obj: sum {t in T} y[t]; s.t. weight: sum {t in T} w[t] * y[t] >= A; s.t. consecutive_ones {i in T, j in T, k in T: i < j < k}: y[j] >= y[i] + y[k] - 1;  P.P.S: Anyhow, if @Libra can "afford" $$T$$ additional binary variables, @leotac's approach is the way to go. Model C: set T = 1 .. 100; param w {T} = Uniform01(); param A = 10; var y {T} binary; var z {T} binary; minimize obj: sum {t in T} y[t]; s.t. weight: sum {t in T} w[t] * y[t] >= A; s.t. consecutive_ones {t in T}: z[t] >= (if t = 1 then y[t] else y[t] - y[t-1]); s.t. SOS1constraint: sum {t in T} z[t] <= 1;  performs best among all three discussed approaches [by far!]. answered 02 Feb '14, 07:06 fbahr ♦ 4.6k●7●16 accept rate: 13% nice. n^3 can be a pain (02 Feb '14, 10:53) Austin Buchanan Interesting indeed. Thank you very much for the extra testing. (02 Feb '14, 12:41) Libra
 5 You could just use a set of (binary) variables, say $$z_t$$, to indicate the first non-zero $$y_t$$ variable. You can do this with something like $$y_t\ge z_t\ge y_t-y_{t-1}$$. Then, bound $$\sum z_t$$ to be (smaller or) equal to 1. answered 01 Feb '14, 20:53 leotac 51●4 accept rate: 0% 1 You don't need the y_t >= z_t inequality (02 Feb '14, 06:45) jfpuget true, that's totally useless in this case. (02 Feb '14, 06:53) leotac
 4 There's no need to introduce new variables. You want to avoid situations where two variables are set to one, but a variable between them is set to zero. So, for each triple $$(i,j,k)$$ with $$1 \le i < j < k \le n:= |T|$$, include the inequality $$y_j \ge y_i + y_k - 1$$. If we have $$y_i = y_k = 1$$ then all variables $$x_j$$ in between (i.e., with $$i < j < k$$) will be forced to one as well. The number of such inequalities is $$n \choose 3$$ which is $$O(n^3)$$. answered 01 Feb '14, 23:31 Austin Buchanan 1.3k●3●13 accept rate: 42%
 3 A couple things. Assuming we ignore the weight A constraint: The constraints proposed by @leotac work so well, due to total unimodularity. The formulation has integer extreme points. If you want a perfectly tight formulation without adding additional variables, you will need a lot of inequalities--many more than in the relaxation proposed in my other answer. We found them all; see Theorem 8 of this paper. answered 05 Feb '15, 11:29 Austin Buchanan 1.3k●3●13 accept rate: 42%
 0 While I agree with all responses so far, I'd like to suggest constraint programming for resource constrained scheduling. You can for instance have a look here. answered 08 Feb '15, 22:46 jfpuget 2.5k●3●10 accept rate: 8%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: