6
$\begingroup$

I have the following problem: set $P=\{1,2,3...,n\}$ for index $i$, set $K=\{1,2,3,...,m\}$ for index $k$. Value $B_i^k$ is indexed by both $i$ and $k$, while value $l_i$ is indexed by only $i$. Here the objective is that for any $i$ we find the minimum $B^k_i$ value $\mathop {\min }\limits_{k \in K} B_i^k$, minus $l_i$, then accumulate it over $i$. I don't mention the constraints here because they are at least 10 constraint equations on $B_i^k$ and other decision variables that are not included in the objective function, such as binary variables $x_{ij}$, etc. All the constraints can be converted to linear constraints. Is there a way to convert the objective function to standard LP format? Thank you.

The objective is :

$\min \sum\limits_{i \in P}^{} {\left( {\left( {\mathop {\min }\limits_{k \in K} B_i^k} \right) - {l_i}} \right)} $

===============================================================

Update: I still need help with this problem. As @user25004 pointed, naively I can define a new variable $A_i=\mathop {\min }\limits_{k \in K} B_i^k$, and add more constraints on $A_i$ : $A_i <=B_i^k$, for any $k$. But this is not correct because the outside is also a $min$, so solver will make $A_i$ infinitely low to get a "minimum".

I have looked up other related "minimizing over minimum" or "maximizing over maximum" problem. Not much luck but in this post https://stackoverflow.com/questions/10792139/using-min-max-within-an-integer-linear-program , which one answer mentioned "min over min". And he suggest, without details, that we should try "defining new binary variables and use the big-M coefficient". I was trying to make $\mathop {\min }\limits_{k \in K} B_i^k = \sum_{k}B_i^k y_k$ , where $y_k$ is binary variables. And then $B_i^k y_k = B_i^k - M_k(1-y_k)$ using the big-M coefficient. But I know this big-M method is useful when it is in the constraints, the problem is it is now in the objective. I just couldn't continue.

Does anybody know how to effectively formulate the inner minimum $\mathop {\min }\limits_{k \in K} B_i^k$ ? Thank you so much.

$\endgroup$
7
+50
$\begingroup$

Greg Glockner showed how to linearize the following example: $$ \min\left\{\min\{x_1,x_2,x_3\}\right\} $$

For the sake of clarity, I will explain how he achieves this. He introduces a variable $z=\min\{x_1,x_2,x_3\}$ and binary variables $y_1,y_2,y_3$ to deactivate extra (big-$M$) constraints : $$ z\ge x_1-My_1\\ z\ge x_2-My_2\\ z\ge x_3-My_3\\ y_1+y_2+y_3=2 $$ Lets analyze these constraints. First $y_1+y_2+y_3=2$ imposes that exactly $2$ binaries equal $1$, so that exactly two constraints are no longer active. The only constraint that will remain active (the one for which $y_i=0$) is the one for which $x_i$ is the minimum.

For example, if $x_1=\min\{x_1,x_2,x_3\}$, then you will have $y_1=0$ and $y_2=y_3=1$, so that the only constraint that remains active is $$ z\ge x_1 $$

And since the solver is minimizing $z$, it will try to fix it to $x_1$ at least, ensuring tightness.

Now, back to your problem, replace constraints $A_i\le B_i^k$ by similar ones, e.g.: $$ A_i\ge B_i^k-My_i\quad \forall i\in P\\ \sum_{i\in P}y_i=|P|-1 $$

$\endgroup$
  • $\begingroup$ In the example of min z where z = min(x1,x2,x3), except for introducing the constraints z >= x1-M y1, z >= x2-M y2, z >= x3-M y3, y1+y2+y3=2 and y1,y2,y3 are binary, do we need to enforce z <= x1, z <= x2, and z <= x3 as well? i think only in this way can we guarantee that z=x1 when y1=0. Please correct me if I am wrong, thanks. $\endgroup$ – Frank Dec 17 '16 at 21:20
  • $\begingroup$ @Frank No this is not necessary, this will be automatic since you are minimizing $z$. $\endgroup$ – Kuifje Dec 20 '16 at 13:27
2
$\begingroup$

The source of nonlinearity here is the inner min. To reformulate it to a linear form, you need to replace that inner min.

For this purpose, you can define a new variable $A_i$ equal to the inner min and substitute it. i.e. replace $A_i = \min_{k \in K} B_i^k$.

Next you need to insert a set of linear constraints to guarantee that $A_i$ is actually the min of $B_i^k$.

Representation of min with a set of linear constraints Hint: The min of a set of variables is smaller than or equal each of those variables.

$\endgroup$
  • 1
    $\begingroup$ How to deal with tightness of $A_i$ is what that stills needs to be worked out. $\endgroup$ – user25004 Jul 14 '16 at 0:48
  • $\begingroup$ thank you so much! what do you mean by "tightness" here $\endgroup$ – daydayup Jul 14 '16 at 3:25
  • $\begingroup$ Once a variable is smaller than or equal to all other variables, that is a lower bound on the minimum of those variables. But it could be smaller than those too. In order to be equal to the minimum and not smaller, the lower bound should be tight. This something to be considered in the model. $\endgroup$ – user25004 Jul 15 '16 at 19:03
  • $\begingroup$ That's so true! Do you know how to solve the issue? I saw another post where people mentioned we need to bring in new binary variables and use the big-M method. Do you know how this works? stackoverflow.com/questions/10792139/…. See Greg Glockner 's comment. Thank you so much $\endgroup$ – daydayup Jul 15 '16 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.