0
$\begingroup$

I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.

In $F_2$, I want it to be included only when its expression violates a certain quantity. In fact, $F_2$ involves the product of two decision variables to be specific and its quantity should be multiplied by a penalty parameter say $\sigma$ only when it is greater than another quantity say $\alpha_i^{k,l}$.

$$F_2=\sigma \sum_{\mathcal{R}_i \in \mathcal{R}}\sum_{p^j_{(s^j, d^j)} \in \mathcal{P}} \sum_{(v^i_k, v^i_l) \in \mathcal{L}^i} x^{i, k}_{s^j}\times x^{i, l}_{d^j} d^j_{(s^j, d^j)}.$$

$x$ is a binary decision variable, $d$ is a constant.

How do I model this and what should be the constraints I need to add into the set of existing constraints?

Improve this question
$\endgroup$
2
  • $\begingroup$ @RobPratt, the const function F_2 is now explicitly defined. $\endgroup$ Commented Dec 1, 2023 at 21:18
  • $\begingroup$ @RobPratt, x is a binary decision variable and d is a constant. $\endgroup$ Commented Dec 1, 2023 at 21:28

1 Answer 1

Reset to default
2
$\begingroup$

I will simplify the notation to illustrate the idea. You want to minimize $$\sigma \max\left(\sum_{i,j} d_{ij} x_i x_j - \alpha, 0\right).$$ Introduce binary decision variable $y_{ij}$ to represent the product $x_i x_j$, and introduce nonnegative decision variable $z$ to represent the $\max$. Now minimize $\sigma z$ subject to linear constraints \begin{align} y_{ij} &\ge x_i + x_j - 1 \\ z &\ge \sum_{i,j} d_{ij} y_{ij} - \alpha \end{align}

Improve this answer
$\endgroup$
8
  • $\begingroup$ I will implement it and let you know if it worked. Thanks ! $\endgroup$ Commented Dec 1, 2023 at 21:49
  • $\begingroup$ it did not actually work as expected. Is there something I need to consider as well ? $\endgroup$ Commented Dec 11, 2023 at 16:45
  • $\begingroup$ @LyLa What unexpected behavior did you see? $\endgroup$ Commented Dec 11, 2023 at 17:15
  • $\begingroup$ I am solving a relaxed version of the problem where I introduced the McCormick envelope for the product of the x^{i, k}_{s^j} by x^{i, l}_{d^j}. So, I ended up in a relaxed version that I round off but the cost function value (F1+F2) is lesser in the rounded solution than in the optimal one with your suggestion. $\endgroup$ Commented Dec 11, 2023 at 17:26
  • $\begingroup$ One possible source of discrepancy is that my suggestion penalizes only the part above $\alpha$ rather than the whole sum if it is at least $\alpha$, but that would tend to yield a smaller cost for my suggestion (the opposite of what you are seeing). Are you sure that the rounded solution satisfies all the constraints? $\endgroup$ Commented Dec 11, 2023 at 18:11

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.