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?


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)\]


\[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 \(<c\). This is the origin of the constraint


asked 26 Mar '12, 08:50

Matteo's gravatar image

accept rate: 0%

edited 06 Oct '13, 09:36

fbahr's gravatar image

fbahr ♦

Is this a homework question? Is the equation exactly as it should be? A variable with largest value will be fixed to a constant?

(26 Mar '12, 10:12) Marco Luebbecke ♦

@Marco: I understand your concern. However, if we want to be too strict then we have to mark all the basic modeling (and perhaps theorem proof questions) marked as homework. I'm not sure this is what really this community is following.

(26 Mar '12, 10:28) Ehsan ♦

The thing about hoemwork is that you want to avoid just giving the answer. For obvious textbook questions, I don't think that it is unreasonable to refuse to answer. For more complex ones, let's try to just give hints unless the poster can convince us that it's not homework.

(26 Mar '12, 10:57) Matthew Salt... ♦

One approach to possible homeworks is simply to wait three days or so, particularly for those whose only interaction with the community is to post the "possibly" homework question. If there is a real interest, a short delay is no problem; if it is a homework, the delay means that they are unable to simply copy the result.

(26 Mar '12, 10:59) Michael Trick ♦♦

I agree with Matt. If the OP has thought about the question and explains where he got stuck and why, I see no reason not to give hints in the right direction or explain some theory. Lame copy paste questions or repeated questions with no progress in between should of course be ignored.

(26 Mar '12, 11:04) Bo Jensen ♦

hey hey, @Mike, this is not my only interaction with the community :-/

(26 Mar '12, 11:12) Marco Luebbecke ♦

Thank you all for the feedback. In particular, I agree with a combination of @Mike's and @Matthew's solutions as it is hard to just hint toward the solution of some of the modeling questions.

(26 Mar '12, 11:20) Ehsan ♦

@marco: I wasn't referring to you (I know you!), but to @matteo, the original poster of the "possibly" homework problem. But, with the longer version, it no longer looks like homework!

(26 Mar '12, 15:05) Michael Trick ♦♦
showing 5 of 8 show 3 more comments

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%20Luebbecke's gravatar image

Marco Luebbecke ♦
accept rate: 16%

edited 06 Oct '13, 09:29

fbahr's gravatar image

fbahr ♦

Thank you a lot

(26 Mar '12, 15:26) Matteo

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%20Saltzman's gravatar image

Matthew Salt... ♦
accept rate: 17%

edited 06 Oct '13, 09:31

fbahr's gravatar image

fbahr ♦

@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 ♦

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

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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 06 Oct '13, 09:34

fbahr's gravatar image

fbahr ♦

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



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



Asked: 26 Mar '12, 08:50

Seen: 2,347 times

Last updated: 06 Oct '13, 09:36

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