3
$\begingroup$

My optimisation problem has a constraint in the form

\begin{equation} \begin{array}{*{35}{l}} \text{}\hspace{16.5mm}\text{ C4:} \hspace{2mm}\sum_{u=1}^U d_{u,1}L_{u}:\sum_{u=1}^U d_{u,2}L_{u}:\cdots:\sum_{u=1}^U d_{u,C}L_{u}=\psi_1:\psi_2:\cdots:\psi_C \end{array} \end{equation}

This nonlinear and makes the problem even more complex.

Here $L_{u}$ and $\psi_{c}$ are known parameters.

I will be satisfied with approximate proportional relation, e..g, C4 can be

$\text{ C4:} \hspace{2mm}\sum_{u=1}^U d_{u,1}L_{u}:\sum_{u=1}^U d_{u,2}L_{u}:\cdots:\sum_{u=1}^U d_{u,C}L_{u}\approx\psi_1:\psi_2:\cdots:\psi_C$

How can I deal with this nonlinear constraint?

$\endgroup$
3
  • 1
    $\begingroup$ I'm not sure Iunderstand what C4 is. Is it that the first sum divided by the second sum equals $\psi_1$, the seconds sum divided by the third sum equals $\psi_2$, etc.? if so, just multiply out the denominator, i.e., first sum equals $\psi_1$ times second sum, etc. If that is not what C4 is, you need to make it clear. $\endgroup$ Mar 5, 2021 at 1:56
  • 4
    $\begingroup$ @MarkL.Stone I think it means that the ratio of the $i$th sum to the $j$th sum is $\psi_i/\psi_j$, but your idea to clear the denominator still applies. $\endgroup$
    – RobPratt
    Mar 5, 2021 at 2:04
  • $\begingroup$ @MarkL.Stone, RobPratt is correct. Lets say for example, $\psi_1=\psi_2=\cdots=\psi_C$, then all the summations on the left should be equal to each other. $\endgroup$
    – KGM
    Mar 5, 2021 at 2:10

1 Answer 1

7
$\begingroup$

Based on the comments (thanks @RobPratt), C4 looks like $$\frac{\sum_{u=1}^U d_{u,1}L_{u}}{\sum_{u=1}^U d_{u,2}L_{u}} = \frac{\psi_1}{\psi_2}$$ with similar constraints for other ratios.

Just multiply both sides by the denominator, which males it a linear constraint. $$\sum_{u=1}^U d_{u,1}L_{u} = \frac{\psi_1}{\psi_2}\sum_{u=1}^U d_{u,2}L_{u}$$ Similarly with the other constraints in C4.

This is then a MILP.

If you only require the proportions to be approximately satisfied, one way of doing that is to add a term $a_i$ (declared as an optimization variable) on the right-hand side of the ith of these constraints, and add the inequality constraints $-f \le a_i \le f$ where $f$ is the allowed fudge (tolerance) factor for constraint satisfaction. This is still a MILP.

You could instead make the tolerance a multiplicative factor of the ratios of the $\psi 's$. This introduces binary, continuous product terms, which can be linearized using standard techniques well-covered in this forum.

Or change the equality constraints to double-sided inequality constraints building in the allowable tolerance, rather than introducing new variables. This can be done with either the additive or multiplicative tolerance.

$\endgroup$
5
  • $\begingroup$ thanks for your answer. Please see my edit. I have slightly modified my objective. $\endgroup$
    – KGM
    Mar 5, 2021 at 14:25
  • $\begingroup$ That's a very different problem. I suggest you ask a new question. $\endgroup$ Mar 5, 2021 at 15:07
  • $\begingroup$ since $d_{u,c}$ is a binary variable, looks that equality constraint will provide infeasible solution most of the times. So, we may need to minimise the value of $f$ (the allowed tolerance). How can we achieve that? $\endgroup$
    – KGM
    Mar 8, 2021 at 19:51
  • $\begingroup$ since $d_{u,c}$ is a binary variable, looks that equality constraint will provide infeasible solution most of the times. So, we may need to minimise the value of $f$ (the allowed tolerance). How can we achieve that? I mean how can I minimise $f$ with $\frac{\psi_1}{\psi_2}\sum_{u=1}^U d_{u,2}L_{u}-f\le \sum_{u=1}^U d_{u,1}L_{u} \le \frac{\psi_1}{\psi_2}\sum_{u=1}^U d_{u,2}L_{u}+f$ $\endgroup$
    – KGM
    Mar 8, 2021 at 20:09
  • $\begingroup$ You can add a penalty term to the objective function. You will have to decide the scale factor, and perhaps which norm of f to use 9for instance (1, 2, inf0, which all consider in different ways the errors across the individual constraints. Or, as I suggested, pick an allowable tolerance, then optimize using that tolerance with no penalty term on objective. $\endgroup$ Mar 8, 2021 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.