# How to linearise max min constraints for multiple terms?

 0 Say, min{a_1...a_m} < max{b_1...b_m} asked 21 Jul '17, 07:34 Sulivan Cheung 11●3 accept rate: 0%

 2 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. answered 21 Jul '17, 10:58 Paul Rubin ♦♦ 14.6k●4●13 accept rate: 19%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: