1
$\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$ – Mark L. Stone Mar 5 at 1:56
  • 3
    $\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 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$ – dipak narayanan Mar 5 at 2:10
5
$\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$ – dipak narayanan Mar 5 at 14:25
  • $\begingroup$ That's a very different problem. I suggest you ask a new question. $\endgroup$ – Mark L. Stone Mar 5 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$ – dipak narayanan Mar 8 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$ – dipak narayanan Mar 8 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$ – Mark L. Stone Mar 8 at 21:02

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.