Friday, January 7, 2011

Max and Min Functions in a MIP

Previously I wrote about how to work the "positive part" function ($y^+=\max(y,0)$) into a mixed integer programming model. More general uses of the $\max$ and $\min$ functions are really just an extension of this, but the extension may not be entirely obvious. In this post I'll explain how to set $z=\max(x,y)$ in a MIP model, where $x$, $y$ and $z$ are all variables. If the model was in fact a linear program before introducing the $\max$ or $\min$ function, it may remain an LP, or it may become a MIP, depending on exactly what you are doing.  I'll use the $\max$ function for explanatory purposes; the necessary tweaks to deal with the $\min$ function are left to the reader as an exercise.

Let's start with the obvious part: if $z=\max(x,y)$ then $$z\ge x$$ and $$z \ge y.$$In fact, adding those two constraints will be sufficient if the nature of the model ensures that the smallest feasible value of $z$ will always be chosen  Typically this means that (a) $z$ has a positive coefficient in an objective function being minimized, or a negative coefficient in an objective function being maximized, and (b) $z$ does not connect to other variables, through constraints, in a way that might allow an inflated value of $z$ to cause other variables to change enough that their improved objective contribution would more than pay for the damage done by inflating $z$.

There are also occasional cases where inflation of $z$ is not actually a concern: you need $z$ to be at least as big as both $x$ and $y$ (which the constraints ensure), but a larger than necessary value of $z$ will not affect the objective function or the values of other variables, and can be corrected manually once a solution is found.

The (slightly) tricky case is when you cannot be sure that the "pressure" of the  objective function will prevent inflated values of $z$ from occurring, and you really do need the value of $z$ to be correct.  To handle this case, we will need finite bounds for $x$ and $y$, so from here on I will assume that $L_x \le x \le U_x$ and $L_y \le y \le U_y$.  We have to introduce a new binary variable $w$, which will switch values depending on whether $x$ or $y$ is the larger of the two. In addition to the two previous constraints, we add the following:$$z \le x + (U_y - L_x)w$$and$$z \le y + (U_x-L_y)(1-w).$$The combined effect of the constraints is that $w=0\implies z=x\ge y$ and $w=1\implies z=y\ge x$.

12 comments:

  1. Can you shed me a light on this subject regarding my problem? I need to find PoverBudget, which is PoverBudget = (summation_t=1:24) Pbattery - Pbudget . I want the PoverBudget to be zero, if the resulting value is negative or else keep the value if its positive. I am confused how to formulate it, as a constraint or as an objective function. Actually, I need to minimize (Cost_battery * PoverBudget) in the objective function, and I cannot find ways to model that in CPLEX.
    Any help will be greatly appreciated.

    ReplyDelete
    Replies
    1. Assuming that Cost_battery > 0, the solver will want to give it the smallest value possible (given the rest of the solution). That means you can declare PoverBudget to be a nonnegative variable and then constrain it to be >= the summation you gave. If the sum is negative, the solver will set it to zero, the smallest feasible solution (given the sign restriction).

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Very useful !

    It seems to work for several variables :

    z0=max(a,b)
    z1=max(z0,c)
    z2=max(z1,d)
    ....

    a,b,c have same bounds

    Isn't it ?

    Regards

    ReplyDelete
    Replies
    1. Yes, you can "chain" max operations as you described, adding one binary variable for each $z_j$. You can equivalently start with one binary variable for each original variable ($w_a$ corresponding to $a$, $w_b$ corresponding to $b$, ...) with the constraint $w_a + w_b + ... = 1$ (exactly one variable is picked to be maximal), and similar upper bound constraints as before (where the original $w$ would now be $w_y$ and $1-w$ would be $w_x$). The lower bounds $L_a$ etc. would be as before, while the upper bounds would change so that, for example, $U_y$ in the first upper limit constraint would be replaced by the largest upper bound of any variable other than $x$, while $U_x$ would be replaced by the largest upper bound of any variable other than $y$. Either approach should work.

      Delete
  4. Dear Dr. Rubin
    Would you please provide a reference for your claim? Especially I am looking to read more about the first statement.
    Thank you

    ReplyDelete
    Replies
    1. Sorry, I don't have a reference at hand. It's not to hard to prove mathematically, and I suspect it has been used as a homework assignment on more than one occasion. You may be able to find a version of it in the book "Model Building in Mathematical Programming" by H. P. Williams, but I'm not positive it's covered there.

      Delete
  5. Dear Dr. Rubin.
    I have a decision variable 'Pow' and another one 'Incentive'. The latter is inside the objective function and takes into account 'Pow' only if it is positive. What we've done is to divide 'Pow' into two variables 'Pow_pos' and 'Pow_neg'. We've done this by using binary variables which constrain one of both to be null, but we would like very much to keep the linearity of the problem. We thought of using a function such as 'Pow_pos=max(0,Pow)' and 'Pow_neg=min(0,Pow)', but we didn't find a way to express max and min as linear functions. Do you have anything in mind that could help us?
    One way to do it is to put 'Pow_pos>=0' and 'Pow_pos>=Pow' and then minimizing 'Pow_pos'. Vice versa for 'Pow_neg'. Of course this constrains us to increase the complexity of the objective function. We were looking for a more fancy way.
    Thank you very much.

    ReplyDelete
    Replies
    1. This comes down to how "Pow_pos" affects the objective function. Writing Pow = Pow_pos - Pow_neg (with all variables >= 0) is the correct start. If smaller values of Pow_pos are always better for the objective function, that's all you need. If the objective function "prefers" larger values of Pow_pos, though, then I do not think there is any way to avoid introducing a binary variable to prevent Pow_pos and Pow_neg from both being nonzero. I think (but I'm not sure) that some solvers will let you add the complementarity constraint Pow_pos * Pow_neg = 0 instead, but internally the solver will most likely either branch on the product (Pow_pos = 0 in one child, Pow_neg = 0 in the other) or add a binary variable anyway, so I don't think you gain anything over putting the binary variable in yourself.

      Delete
    2. Actually, the objective function is a sum of revenues in time, each of them depending on the amount of injected power to the network (Pow_pos) among other variables. Also, Pow_pos has to complaint with other constraints such as power balance in a network (generated power and load must be the same). So, I think the binary variables are unavoidable, unless we use the strategy of putting 'Pow_pos>=0' and 'Pow_pos>=Pow' and then minimizing 'Pow_pos', so it is either null (if Pow is negative) or Pow (if Pow is positive).
      Thank you anyway Dr. Rubin.

      Delete
  6. Dr. Rubin, thank you for your very clear explanation. Best wishes from a 1st year Ph.D. student.

    ReplyDelete

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.