1
$\begingroup$

In an NLP, I have a constraint that I would like to formulate in a convex manner preferably without introducing binary variables and/or big M formulations if possible. The actual problem is non-convex and I am happy with a local solution but I want to avoid any integer variables as there is not a good choice of open-source solvers for nonlinear problems. But of course, if it is not possible to avoid binary variables then it should be fine. The issue is to reformulate IF-THEN-ELSE condition of the type below to determine the appropriate parameter to use: $ IF \hspace{0.5mm}\ \sum_{i=1}^{n}\left(x_i{\ c}_i^t\ \ -{\ L}_t\right)\ <0$ Then $\hspace{0.5mm}\ r_t\ =\ s_t \hspace{0.5mm}\ Else \hspace{0.5mm}\ r_t\ =\ g_t$

where

  • r, s , g and L are constant parameters (time dependent)
  • $x_i$ is a vector of optimisation variables (continuous)
  • ${\ c}_i^t$ are coefficients of $x_i$

The actual constraint is given by: $\sum_{t=1}^{T}{EP}_t=0\ $

where ${EP}_0\ =\ 0$

${EP}_1\ =\ \sum_{i=1}^{n}{x_ic_i^1} - L_1$

${EP}_2\ =\ \sum_{i=1}^{n}{x_ic_i^2} - L_2\ +\ {EP}_1\ r_1\ $

${EP}_3\ =\ \sum_{i=1}^{n}{x_ic_i^3} - L_3\ +\ {EP}_2\ r_2\ $

${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t} - L_t\ +\ {EP}_{t-1}\ r_t\ $

$If\ {EP}_{t-1}\ <0\ then \hspace{0.5mm}\ r_t\ =\ s_t \hspace{0.5mm}\ Else \hspace{0.5mm}\ r_t\ =\ g_t$

where

  • $r_t, \hspace{0.5mm}\ s_t , \hspace{0.5mm}\ g_t and \hspace{0.5mm}\ L_t$ are constants
  • $0\leq x_i \leq 1$ $\hspace{5mm}\ i \in {1,2...n}$
  • ${\ c}_i^t$ are coefficients of $x_i$
  • Only $x_i$ are the optimisation variables

How can this constraint be reformulated either using Big M /binary variables or using some other formulation? I don't want to use IF in the constraint as it will make the problem hard to solve. Please note that there are a number of other nonlinear constraints in the model. I was thinking that we may be able to write it using min and max, e.g., ${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t}\ +\ min\left\{0,{EP}_{t-1}\ \right\}\ s_t\ \ +\ max\left\{0,{EP}_{t-1}\ \right\}\ g_t$ and then introduce some auxiliary variables but I am not sure where to go next.

I have given a numerical example in the attached image which explains how this constraint is constructed and where we have determined value of x.

$c = \begin{pmatrix} 1 & 20 & 30 & 40\\ 1 & 2 & 60 & 2\\ 5 & 3 & 2 & 1\\ 10 & 8 & 5 & 40\\ 3 & 6 & 2 & 3 \end{pmatrix} , \hspace{0.5mm}\ L = \begin{pmatrix} 30\\ 60\\ 30\\ 20\\ 1 \end{pmatrix} , \hspace{0.5mm}\ x = \begin{pmatrix} x_1\\ x_2\\ x_3\\ x_4 \end{pmatrix}, s = \begin{pmatrix} 0.001\\ 0.002\\ 0.003\\ 0.004\\ 0.005 \end{pmatrix} , g = \begin{pmatrix} 0.006\\ 0.050\\ 0.009\\ 0.010\\ 0.020 \end{pmatrix}$

The above constraint will be satisfied for the following values of $x = \begin{pmatrix} 0.363034965\\ 0.514820246\\ 0.539183467\\ 0.856864726\\ \end{pmatrix}$

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ As far as I can see the model is linear (besides the logical constraint) so adding the formulation with min and max in your proposal is going to end up being a big-M based MILP representation anyway (since you have to represent those operators somehow, and if you use MILP it will be a big-M method). Probably better to go for the obvious big-M model instead of hiding it in the min/max models. A convex reformulation is not possible. $\endgroup$ – Johan Löfberg Apr 2 at 10:33
  • $\begingroup$ Thank you @JohanLöfberg I have a number of other non-linear constraints in the model. I have just shown this constraint as it is causing me a problem. I don't know how to use Big M method in this case either. I have added more explanation in the question. $\endgroup$ – Marry Apr 2 at 10:54
  • $\begingroup$ I came across this post on stackoverflow which uses something similar to min max: stackoverflow.com/questions/58756084/… $\endgroup$ – Marry Apr 2 at 10:56
4
$\begingroup$

Introduce a binary variable $\delta_t$ to represent which case it is and $z_t$ to represent the modelled product, and your MILP model of the piecewise-affine dynamics would be

${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t}\ -L_t + z_t\\ {EP}_{t-1}\leq (1-\delta_t)M, -(1-\delta_t)M \leq z_t - s_t{EP}_{t-1}\leq (1-\delta_t)M\\ ~{EP}_{t-1}\geq -\delta_t M, -\delta_tM \leq z_t - g_t{EP}_{t-1}\leq \delta_t M$

$\endgroup$
2
  • $\begingroup$ Thank you @JohanLöfberg. I was wondering whether the last inequality should be written as: $-\delta_tM \leq z_t - g_t{EP}_{t-1}\leq \delta_t M$ and also the first equation should be: ${EP}_t\ =\ \sum_{i=1}^{n}{x_ic_i^t}\ -L_t + z_t$ $\endgroup$ – Marry Apr 5 at 11:44
  • $\begingroup$ Yes, fixed typos $\endgroup$ – Johan Löfberg Apr 5 at 12:00

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.