I have formulated a problem with a max function (nonlinear function) in one of the constraints. Based on the techniques posted here, I try to convert the constraint with the max function to several linear constraints with the introduction of a binary decision variable.

This gives me a MIP.

I wonder whether i can solve its relexed LP and claim the optimal solution returned by the LP is also the optimal solution to the MIP.

So here comes my question shown in the title.

I find that i am done if i can prove that the integrality gap of the MIP and its relaxed LP is 1 (or 0 depending on the different favor of definition of the integrality gap).

alt text

alt text

\(c_{i}\) are nonnegative.


asked 05 Jan '12, 20:23

farseeing's gravatar image

accept rate: 0%

edited 12 Oct '12, 05:40

fbahr's gravatar image

fbahr ♦

could you please give a little more detail of what exactly your question is? do you try to access the integrality gap from a solver? or is this a theoretical question?

(05 Jan '12, 20:32) Marco Luebbecke ♦

@Marco Thanks for your comment. I have edited my post. I think it is a theoretical question brought up by a practical problem :)

(05 Jan '12, 22:30) farseeing

Based on constraint 1.3, value of variable x' is always defined by variable x and you could omit it from your model via replacing it with bx/p. In addition, if the ratio of b and p is known to be less than or greater than one, you might be able to omit the max function via necessary modification as well.

(06 Jan '12, 01:30) Ehsan ♦

@Ehsan is right. According to your model, it is possible to infer wheter X_i or X'_i is the biggest in advance. If we got it right, I suggest that @Ehsan upgrades his comment to the status of an answer.

(06 Jan '12, 06:30) Thiago Serra

@Ehsan @Thiago Serra: Great insight! I think you are right. That is really the silver bullet i need to solve my problem. I will edit the title of my post to make it match my initial problem.

(06 Jan '12, 11:12) farseeing

Separate from Ehsan's comment (with which I agree), if the coefficients (c_i) are nonnegative, you do not need the binary variables. Assuming (c_ige 0 forall i), (2.4)-(2.6) and (2.9)-(2.10) should be sufficient. You don't need (y_i=max{x_i,x'_i}); you just need (y_igemax{x_i,x'_i}).


answered 06 Jan '12, 18:12

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 06 Jan '12, 18:13

@Paul Rubin, thanks for your answer. Yes, (c_i) are nonnegative. Can you elaborate a little more on why (y_i ge max{x_i, x'_i}) is sufficient and the binary variables are not needed, i.e., (2.7) (2.8) are not needed? I thought about it before but am not quite sure about it.

(06 Jan '12, 21:36) farseeing

Sorry; to be clear(er), you need the left halves of (2.7) and (2.8) to get (y_ige max{x_i,x'_i}). The binary variables are used to force (y_i) to equal the maximum, but you don't need it equal; it's sufficient that it provides an upper bound for the max.

(07 Jan '12, 10:41) Paul Rubin ♦♦
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: 05 Jan '12, 20:23

Seen: 12,933 times

Last updated: 17 May '15, 23:17

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