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

\[\max(x_1,...,x_n)=c\]

asked 26 Mar '12, 08:50

Matteo's gravatar image

Matteo
213
accept rate: 0%

edited 06 Oct '13, 09:36

fbahr's gravatar image

fbahr ♦
4.6k716

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

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... ♦
3

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

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

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.

link

answered 26 Mar '12, 15:12

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

edited 06 Oct '13, 09:29

fbahr's gravatar image

fbahr ♦
4.6k716

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?

link

answered 26 Mar '12, 11:38

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

edited 06 Oct '13, 09:31

fbahr's gravatar image

fbahr ♦
4.6k716

@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

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.

link

answered 26 Mar '12, 19:52

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 06 Oct '13, 09:34

fbahr's gravatar image

fbahr ♦
4.6k716

Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×65

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.