# Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint

I have a MIP minimization problem where I have a maximization in the constraints:

$$\max(c_1x_2,\, c_2x_2,\, \ldots,\, c_nx_n) \geq q$$

Where:

• $$c_n$$ constants
• $$x_n$$ binary variables
• $$q$$ constant

$$x_n$$ is not part of the objective function. How can I linearize this?

The first step to solve this would be to create a new variable $$z$$ representing the the maximum value. Further I think a Big M should be used. But what would become the constraints?

I found an option that almost does this but it is for two variables instead of $$n$$. For example $$\max(x,y)$$.

Furthermore, this problem is similar but doesn't cover the problem exactly.

You can do this with no new variables. Let $$S=\{k:c_k \ge q\}$$ and add the constraint $$\sum_{k\in S}x_k \ge 1$$.
Assuming that the $$c_i$$ and $$q$$ are all positive you may add one binary variable $$y_i$$ for every $$i=1,\cdots,n$$ then you may do \begin{align}c_i x_i &\geq q y_i \quad\forall i\\\sum_i y_i &\geq 1\end{align}
• By the way, this is the same big-M approach as in the second linked post. Explicitly: $q - c_i x_i \le M(1-y_i)$, with $M=q$, simplifies to this. Nov 14 '19 at 15:28
{"ft_lang_label":"__label__en","ft_lang_prob":0.90574455,"math_prob":0.9999019,"size":638,"snap":"2021-43-2021-49","text_gpt3_token_len":171,"char_repetition_ratio":0.11198738,"word_repetition_ratio":0.0,"special_character_ratio":0.26959246,"punctuation_ratio":0.14173229,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000052,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-20T04:33:11Z\",\"WARC-Record-ID\":\"<urn:uuid:5929dded-eded-4a96-9be2-93f62784cde6>\",\"Content-Length\":\"171520\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:015d94f4-4139-496f-9108-50c9ba8aee1a>\",\"WARC-Concurrent-To\":\"<urn:uuid:0ceba95c-bac2-4267-9317-f30c7dddec5e>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://or.stackexchange.com/questions/3053/linearization-maxc-1-x-2-c-2-x-2-ldots-c-nx-n-geq-q-constraint?noredirect=1\",\"WARC-Payload-Digest\":\"sha1:T5ASBNTFBCMNWNBRIO4NLFJ6UXUMCCC4\",\"WARC-Block-Digest\":\"sha1:RXU6GAYUMZ4MAYUDKJWOOJKH55X42YVE\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585302.56_warc_CC-MAIN-20211020024111-20211020054111-00583.warc.gz\"}"}