9
$\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$

3 Answers 3

Reset to default
14
+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$
3
  • $\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$ Commented Dec 17, 2016 at 21:20
  • $\begingroup$ @Frank No this is not necessary, this will be automatic since you are minimizing $z$. $\endgroup$ Commented Dec 20, 2016 at 13:27
  • $\begingroup$ Thanks a lot! Can I have a reference for this? $\endgroup$ Commented Aug 21, 2024 at 0:34
3
$\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$
4
  • 1
    $\begingroup$ How to deal with tightness of $A_i$ is what that stills needs to be worked out. $\endgroup$ Commented Jul 14, 2016 at 0:48
  • $\begingroup$ thank you so much! what do you mean by "tightness" here $\endgroup$ Commented Jul 14, 2016 at 3:25
  • 1
    $\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$ Commented Jul 15, 2016 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$ Commented Jul 15, 2016 at 20:01
1
$\begingroup$

In http://arxiv.org/abs/2302.09322 a reachability problem in robotics is discussed and solved by formulating a min-min-problem $\min_{x\in R^n} \min_{i=1, \ldots, N}{ f_i(x)} $ in several houndred variables and constraints (a PUMA-like industrial robot with 6 rotational axes plus a virtual axis, 8 solutions of the inverse transform for each pose, typical problem size 20 poses giving 7 x 8 x 20= 1120 variables with bound constraints, plus user constraints). The solution is based on a general transformation to a optimization that uses a convex combination of the $f_i$, that is linear constraints. Of course the problem remains nonlinear if the $f_i$ are nonlinear.

In the Greg Glockner example above we have $n=3$, $N=3$ and $f_i(x) = x_i$. Instead of binary variables $y_i \in {0,1}$ with integer constraints for selection of the function giving the minimum, we introduce real variables $0\leq w_i \leq 1$, and have the following Lemma; the set $C$ in the paper corresponds to an index set like $C={1, \ldots, N}$ for the constraints:

Lemma: Consider $f_c: R^n\to R$ for $c \in C$, $C$ a finite set. Consider the unconstrained minimization problem $$ \min_{{x}\in R^n} \min_{c\in C} f_c({x}) $$ and the constrained problem $$ \min_{{x}\in R^n,w\in R^{C}} \sum_{c\in C} w_c f_c({x}) $$ $$ \text{under } \sum_{c\in C} w_c = 1, \qquad 0 \leq w_c\leq 1 \qquad \text{ for all } c\in C $$ Then the problems are equivalent: The unconstrained min-min-problem is unbounded iff the constrained problem is. If the problems are bounded, then the minimum and infimum values are the same, and $m^\star=f_{c^\star}({x^\star})$ for some ${x^\star}, c^\star$ if the minimum $m^\star$ is attained.

The intuition is: Components of the solution $w^\star$ with $w^\star_c > 0$ correspond to functions giving the minimum.
Components of the solution $w^\star$ with $w^\star_c = 0$ cancel out non-minimum values in the objective function.

The convex combination is well behaved and can be handled efficiently by standard numerical algorithms available e.g. in the MATLAB Optimization Toolbox. No special algorithms for mixed integer-real problems are needed.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.