I have the following optimization problem:
$\min J = \sum_{i=0}^{N} k_i = k_0 + k_1 +\dots+ k_N$
s.t:
$k_i = f_i(z_i)$
where
$f_i(x) = \begin{cases}
x,& \text{if } x\leq P_i\\
P_i, & \text{otherwise}
\end{cases} = \min(x, P_i)$
and $z_i$ is a linear combination of other constants and decision variables $z_i = \sum_{j=0}^{M} K_{ij}(Y_{ij} – y_{ij})$
- $P_i >0, \, K_{ij}>0, Y_{ij}>0$ are constants
- $y_{ij} \geq 0,\, k_i \geq 0$ are continuous decision variables
I do not know how to write the minimization problem containing the Objective with the summation over min functions into a Mixed Integer programming problem suitable for Pythons pulp package for example.
I do not have a mathematics background and did my research for many days on this topic, reading papers or articles, but it is difficult to correctly identify the problem when not coming from a mathematics background.
Does anyone know how to solve this and/or how to translate this into a MIP formulation?
Best Answer
You want to minimize $$\sum_{i=0}^N \min\left(\sum_{j=0}^M K_{ij}(Y_{ij}-y_{ij}), P_i\right).$$ Introduce a continuous variable $s_i$ to represent the outer summand and a binary variable $b_i$ to indicate which minimand is active. Let $M^1_i$ be a small constant upper bound on $\sum_{j=0}^M K_{ij}(Y_{ij}-y_{ij}) - s_i$, and let $M^2_i$ be a small constant upper bound on $P_i - s_i$. The problem is to minimize $\sum_{i=0}^N s_i$ subject to linear constraints \begin{align} s_i &\le \sum_{j=0}^M K_{ij}(Y_{ij}-y_{ij}) \tag1 \\ s_i &\le P_i \tag2 \\ s_i &\ge \sum_{j=0}^M K_{ij}(Y_{ij}-y_{ij}) - M^1_i b_i \tag3 \\ s_i &\ge P_i - M^2_i (1-b_i) \tag4 \\ \end{align} Constraint $(3)$ enforces $b_i=0 \implies s_i \ge \sum_{j=0}^M K_{ij}(Y_{ij}-y_{ij})$. Constraint $(4)$ enforces $b_i=1 \implies s_i \ge P_i$.
Given $0 \le y_{ij} \le Y_{ij}$, you can take $$M^1_i = \sum_{j=0}^M K_{ij}(Y_{ij}-0) - P_i = \sum_{j=0}^M K_{ij}Y_{ij} - P_i$$ and $$M^2_i = P_i - \sum_{j=0}^M K_{ij}(Y_{ij}-Y_{ij}) = P_i.$$