# A hack to eliminate the max function in the constraint set

 0 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). $$c_{i}$$ are nonnegative. Thanks asked 05 Jan '12, 20:23 farseeing 53●1●2●6 accept rate: 0% fbahr ♦ 4.6k●7●17 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 3 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

 1 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 Rubin ♦♦ 14.6k●5●13 accept rate: 19% @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 ♦♦
 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:

Seen: 12,933 times

Last updated: 17 May '15, 23:17