Originally posted by: Nodame

I have a List of variables

x_j and Binaries B_j

  I would like to write a Linear constraint that says that if B_ j = 1 for some j, then max x_ j  >= 1000  (Note: taking the max over all indices j).

[Or in other words, the constraint is: If B_j = 1 for some j, then there exists an index k such that x_k >= 1000].

One way I was thinking about writing this constraint is:

max { x_ j }  >= B_ j * 1000    However, I am not sure how to write this constraint in cplex in a Linear form

Originally posted by: davidoff

Using the same index j for both the condition and the variables is a little bit confusing so I answer here with the assumption that we have one given binary B that is the condition that must hold to have one of the x_j greater than 1000

Add one binary B_k to write a constraint x_k>=1000 - M(1-B_k)

M must be chosen so that 1000-M is a valid lower bound for x_k

Then add the constraint

sum(B_k) >= B

If B is true, then one (at least) of the B_k will be also true, and that will enforce the related constraints x_k>=1000

Originally posted by: Nodame

Thanks for your reply davidoff.

Quick question from your comments:

1) "Add one binary B_k to write a constraint x_k>=1000 - M(1-B_k)"

what  is B_k here? Is it a totally different Binary Variable ? If so, what is its definition (When is it = 1 and when is it = 0)?

Otherwise, if B_k is the same Binary variable as the B_j I mentioned earlier (with just a different index), then  I don't think I can use the constraint  

x_k>=1000 - M(1-B_k)

Because, that would imply that If B_k = 1, then the corresponding x_k must be >= 1000. But that's not what I want. All I need is that some x_j (where j could be different than k) is greater than 1000.

2) "Then add the constraint sum(B_k) >= B"

I am not sure  that I can make sense of your last statement unless I understand well what your first statement meant.

Also, notice that what you're calling B here is really B_m for some m (m is not known).

3)I realize there was some confusion in how I formulated the problem the first time. So let me reformulate it again:

Let I be a finite set of Indices,

If B_j = 1 for some index j in I, then there exists an index t in I such that x_t >= 1000

I would like to write the above in the form of Linear constraint(s).

Originally posted by: minyivg

Let me try:

define n= |I|, i.e., the number of indices

define n additional binary variables, say, lambda_1,… , lambda_n in {0,1}

define an additional variable y (with x's range, e.g., y >=0)

The constraints are:

y = \sum_{i=1}^n lambda_i * x_i     (1)

\sum_{i=1}^n lambda_i = 1              (2)

y >= B_j * 1000                                   (3)

lambda_i in {0,1}     for all i in I         (4)

Constraint (1)-(2) impose y is one of {x}. Constraint (3) ensures if B_j =1, there exists a y >= 1000. 

My opinion.

Ming

Originally posted by: Nodame

Thank you for your reply Ming.

However, I think constraint (1)  y = \sum_{i=1}^n lambda_i * x_i    is quadratic. Unfortunately, I can only use Linear constraints.

Originally posted by: minyivg

OK……..

Let me give it another try.

The key is to linearize items "lambda_i * x_i" in constraint (1).

We define a new variable alpha_i, with "meaning" that alpha_i =  lambda_i * x_i. Note that we will use linear constraints to express such relation. Typically alpha_i >= 0, x_i >=0. We use "M" to denote a sufficient lager integer.

Look at the following constraints:

alpha_i <= lambda_i * M,      for all i                          (5)

alpha_i >= x_i - (1 - lambda_i) * M,      for all i         (6)

alpha_i <= x_i + (1 - lambda_i) * M,      for all i        (7)

Moreover, we change constraint (1) to be:    

y = \sum_{i=1}^n alpha_i                                             (1')

Constraint (5) imposes that if lambda_i = 0, alpha_i = 0. The remaining case is lambda_i = 1. Constraints (6)-(7) guarantee that if lambda_i = 1, then alpha_i = x_i. In addition, if lambda_i = 0, constraints (6)-(7) impose nothing, and if lambda_i = 1, constraint (5) imposes nothing.

Ming

Originally posted by: Nodame

Thanks again for your reply Ming. Just to make sure I understand your reasoning.

You are introducing 2 new sets of variables: lambda_i 's (Binary) and alpha_i 's  (i = 1,...,n) where alpha_i >= 0 for each i.

New Constraints to introduce:

(i) alpha_i <= lambda_i * M, for each i

(ii) | alpha_i - x_i | <= (1 - lambda_i) * M , for each i

(iii) \sum_{i=1}^n alpha_i   >= B_j * 1000, for each j

(iv) \sum_{i=1}^n lambda_i  = 1

My understanding of the above:

We know from (iv) and from the definition of the lambda_i's that there is a unique index i such that lambda_i = 1. Let's call this 'special unique' index h. We have that

 lambda_h = 1, and lambda_i = 0 for all i != h   (!= meaning not equal to)

From (i), alpha_h <= M (where M is a Large positive number), and from (ii), we get that alpha_h = x_h

Now Let's assume B_j = 1 for some j . It follows from (iii) that 

\sum_{i=1}^n alpha_i  = alpha_h + 0  >= 1000.

And so x_h >= 1000.

In the case B_j = 0 for all j. It follows that x_h >= 0 (which does not hurt).

I think this works.