Let \(x_i\) be binary variables and \(a_i\) given positive integers.

I have an equality constraint like the following \[x_i\left(\sum_{j=1}^nx_{j}\right)=a_ix_i,\] for all \(i\).

This means that if \(x_i=1\), then there must exists a set \(S\) with cardinality \(|S|=a_i-1\) such that \(x_j=1\) for all \(j\in S\).

How can I linearize these constraints? If the constraints were of type inequality I could use a large (or small) number and write it as:

\[\left(\sum_{j=1}^nx_{j}\right)\leq a_ix_i+M(1-x_i),\] for all \(i\).

asked 18 Jan '18, 11:15

zbir's gravatar image

accept rate: 0%

edited 18 Jan '18, 11:21

Hint: Think of your equality as two inequalities and apply your big-M approach twice.

Also, for numerical reasons be sure to choose \(M\) as small as possible.


answered 18 Jan '18, 11:21

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

edited 18 Jan '18, 11:22

Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 18 Jan '18, 11:15

Seen: 464 times

Last updated: 18 Jan '18, 11:22

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