0

There is a constraint

c[i]=j iff b[i][j]=1

where i, j are integers larger than 0, and b[i][j] is a binary.

Any idea how to formulate this constraint in linear programming ? Thank you!

1
  • i > 0 AND j > 0 AND c[i] = j AND b[i][j] = 1 Commented Feb 26, 2021 at 17:02

1 Answer 1

3

The question is not as clear as one would think. The best answer is: "it depends".

Looking at

  c[i]=j iff b[i][j]=1            (1)

in isolation, we would need to implement the implications:

  b[i][j]=1  =>  c[i]=j           (2)
  b[i][j]=0  =>  c[i]<>j          (3)

(2) can be implemented using an indicator constraint. The second one (3) is more complicated as we would need to do something like:

  b[i][j]=0  =>  c[i]<j or c[i]>j    (4)

This would require at least one extra binary variable to handle the "or". One way would be:

  b[i][j]=0  =>  c[i]<=j-1+M⋅δ        (5)
  b[i][j]=0  =>  c[i]>=j+1-M⋅(1-δ)    (6)
  δ ∈ {0,1}                           (7)
  M = card(j)                         (8)

M=card(j) is just a constant indicating the size of set j. Of course, this is not the only way to implement this. Note that I used a mixture of indicator constraints and big-M constraints. This can also be formulated completely with indicator constraints (extra binary variables are needed) or only with big-M constraints.

Although we can implement (3) (with some effort), most likely we don't need it. In all likelihood, the only thing we need is the implication (2). As with most of these questions, without looking at the rest of the model, it is just very difficult to give good answers.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.