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$.

6 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. telasmosquiteira-sp.com.br

    telas mosquiteira
    telas mosquiteiro

    As telas mosquiteira sp , telas mosquiteiro sp garantem ar puro por toda casa livrando-a completamente dos mosquitos e insetos indesejáveis. As telas mosquiteira garantem um sono tranquilo a toda família, livrando e protegendo-nas dos mais diversos insetos. Muitos destes insetos são transmissores de doenças e a tela mosquiteira é indispensável no combate a mosquitos transmissores de doenças.

    A dengue, por exemplo, já matou centenas de pessoas só na capital de São Paulo e um pequeno investimento em nossas telas mosquiteiras podem salvar vidas. As telas mosquiteiras também impedem a entrada de insetos peçonhentos como as aranhas e os escorpiões, estes insetos também oferecem risco, pois seu veneno em poucos minutos podem levar uma criança a morte.
    telas mosquiteira jundiai
    telas mosquiteiro jundiai
    telas mosquiteira aplhaville
    telas mosquiteiro alphaville
    telas mosquiteira granja viana
    telas mosquiteiro granja vinana
    telas mosquiteira cotia
    telas mosquiteiro cotia
    telas mosquiteira tambore
    telas mosquiteiro tambore

    A chegada da temporada Primavera/Verão traz consigo a elevação da temperatura e a maior ocorrência de chuvas. Mas não é só isso. As estações mais quentes do ano causam muita dor de cabeça e muitos zumbidos indesejáveis em função das pragas urbanas – pernilongos, baratas, cupins e outros insetos -, que afetam todas as regiões brasileiras.

    Nossa missão é oferecer telas mosquiteiras de qualidade a um preço acessível, fazendo com que as telas mosquiteiras sejam uma opção viável para muitas pessoas.

    telas mosquiteiras Jundiaí
    telas mosquiteiro Jundiai
    telas mosquiteiras jundiai
    telas mosquiteiro industria
    telas mosquiteira restaurante
    telas mosquiteiro restaurante
    telas mosquiteira empresa
    telas mosquiteiro empresa

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. 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

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 OR-Exchange.