# 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●5●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:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.882391631603241, "perplexity": 2820.5832636738096}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-34/segments/1596439739347.81/warc/CC-MAIN-20200814160701-20200814190701-00312.warc.gz"}