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's gravatar image

Libra
2098
accept rate: 0%

edited 01 Feb '14, 19:50

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

@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

\[ 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!].

link

answered 02 Feb '14, 07:06

fbahr's gravatar image

fbahr ♦
4.6k716
accept rate: 13%

edited 02 Feb '14, 10:48

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

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.

link

answered 01 Feb '14, 20:53

leotac's gravatar image

leotac
514
accept rate: 0%

edited 01 Feb '14, 21:06

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

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)\).

link

answered 01 Feb '14, 23:31

Austin%20Buchanan's gravatar image

Austin Buchanan
1.3k313
accept rate: 42%

edited 02 Feb '14, 00:16

A couple things. Assuming we ignore the weight A constraint:

  1. The constraints proposed by @leotac work so well, due to total unimodularity. The formulation has integer extreme points.
  2. 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.
link

answered 05 Feb '15, 11:29

Austin%20Buchanan's gravatar image

Austin Buchanan
1.3k313
accept rate: 42%

edited 05 Feb '15, 11:41

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.

link

answered 08 Feb '15, 22:46

jfpuget's gravatar image

jfpuget
2.5k310
accept rate: 8%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×231
×127
×27
×22

Asked: 01 Feb '14, 18:27

Seen: 2,211 times

Last updated: 08 Feb '15, 22:46

OR-Exchange! Your site for questions, answers, and announcements about operations research.