Say, min{a_1...a_m} < max{b_1...b_m}

asked 21 Jul '17, 07:34

Sulivan%20Cheung's gravatar image

Sulivan Cheung
113
accept rate: 0%


I assume the \(a_i\) and \(b_i\) are variables.

First, strict inequalities are anathema in optimization models. You need either to switch to a weak inequality (\(\min\{a_1,\dots,a_m\}\le \max\{b_1,\dots,b_m\}\)) or else specify a minimum acceptable difference (\(\min\{a_1,\dots,a_m\}\le \max\{b_1,\dots,b_m\}-\epsilon\) for some \(\epsilon > 0\)).

Second, I don't think there is any way to linearize this without introducing binary variables. What you are saying equates to \(a_i \le b_j\) for some \(i\) and \(j\). You can introduce binary variables \(x_{ij},\,1\le i,j\le m\), constraints \(a_i\le b_j + M(1-x_{ij})\,\forall i,j\) and one more constraint \(\sum_{i=1}^m \sum_{j=1}^m x_{ij} \ge 1\), where \(M\) is some sufficiently large positive constant.

link

answered 21 Jul '17, 10:58

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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

Asked: 21 Jul '17, 07:34

Seen: 336 times

Last updated: 21 Jul '17, 10:58

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