# Transforming constraint with max function

 2 1 I have a LP problem with n decision variables, $$x_1, \ldots, x_n$$, and one of the constraints is $\max(x_1, \ldots, x_n) = c$ where $$c$$ is a constant and $$max$$ is the max function (i.e., it returns the highest of the parameters $$x_1, \ldots,x_n$$). Is there a way to cope with this constraint, transforming it in a set of linear constraints and/or enriching the objective function with some penalty? Thanks Update: It's not a homework, actually the "max" constraint comes out from my modelling, which could be bad as well. The original problem is maximising a linear function $f(y_1, y_2, \ldots, y_m)$ where $y_i \in \{0,1\}.$ I want that exactly $$c$$ out of $$m$$ variables value 1, so one constraint is $\sum_{i=1}^m y_i = c$ Additionally, I want these "c" variables to be consecutive, e.g., $$y_1=1, y_3=1, \ldots, y_{c+1}=1$$ is not a valid solution. Thus I was thinking the following: let $x_1 = y_1 + y_2 +\ldots+ y_c$ $x_2 = y_2 + y_3 +...+ y_{c+1}$ $\ldots$ $x_n = y_{m-c+1} + y_{m-c+2} +...+ y_{m}$ To be a valid solution, it must exist only one variable $$x_j$$ such that $$x_j=c$$, while all the other variables necessarily are $$3 Answers:  5 I believe that this could and should be modeled without the x variables altogether. If you would like the ones to appear consecutively in the y variables, you should say so: forbid a "hole" (a 0) in between two ones: $y_i + y_{i+2} \leq 1 + y_{i+1}$ hope this helps. answered 26 Mar '12, 15:12 Marco Luebbecke ♦ 3.4k●1●6●15 accept rate: 16% fbahr ♦ 4.6k●7●16 Thank you a lot (26 Mar '12, 15:26) Matteo  3 Think of the constraint as a disjunction. You want \(x_i \leq c, \forall i$$ (the easy part) and you want $$x_i = c, \exists i$$ (the hard part). You can use an auxiliary binary variable and big-$$M$$ to enforce or not a lower bound. Then you want to enforce just one lower bound. Does that help? answered 26 Mar '12, 11:38 Matthew Salt... ♦ 4.7k●3●10 accept rate: 17% fbahr ♦ 4.6k●7●16 @Matthew: I just came up with a correct answer similar to yours (I checked my model with a solver this time to make sure the constraint is enforced). However, I'm not sure you could do so with just one auxiliary variable. Also, you should enforce at least one lower bound (not just one) as it might be optimal to have more than one X_i to be equal to c. (26 Mar '12, 11:59) Ehsan ♦ 1 You're right. I was being deliberately ambiguous. You need an auxiliary for each bound. I don't think the exactly-one/at-lest-one distinction matters. If you enforce one, any others that want to be the same value will be whether the lower bound is enforced or not. (26 Mar '12, 12:06) Matthew Salt... ♦ I would state that the sum of $$y$$ is $$c$$, which is the easy part. I would also state that there is only one one start of a sequence of 1s. It means that there is at most one $$i$$ such that $$y_i = 0$$ and $$y_{i+1}=1$$. The latter can be modeled with an extra variable $$z_i$$ such that $$z_i \geq y_{i+1} - y_i$$ Then sum of $$z$$ is at most 1. (10 Jun '12, 07:24) jfpuget
 1 In terms of the original problem (the $$y$$ version), why not just introduce binary variables $$z_i, i\in \{1,\dots,m-c+1\}$$, where $$z_i=1$$ if the sequence of unit-value $$y$$ variables starts at $$i$$. The new variables form an SOS1 ($$z_1+\dots+z_{m-c+1}=1$$), and $$y$$ (which can now be declared real rather than binary) is given by $$y_i=z_{i-c+1}+\dots+z_i$$ with appropriate adjustments to the starting index to prevent it from going negative. answered 26 Mar '12, 19:52 Paul Rubin ♦♦ 14.6k●5●13 accept rate: 19% fbahr ♦ 4.6k●7●16
 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: