1
$\begingroup$

Suppose we have $N > 2$ functions $f_1, ..., f_N$ with $f_i: \mathbb{R}^{2}_{\geq 0} \to \mathbb{R}_{\geq 0}$ where:

$f_i(x,y) = \alpha_i x \times \mathbb{1}_{\{x\geq A_i\}} + \delta_i y \times \mathbb{1}_{\{y\geq B_i\}} + C_i$

with $A_i, B_i, C_i \in \mathbb{R}_{\geq 0}$ and $\alpha_i, \delta_i \in [0,1] \ \forall i = 1,\dots,N$.

For given $n \in \{2, \ldots, N\}$ and $X, Y \in \mathbb{R}_{\geq 0}$, consider the following optimization problem:

$$ \underset{m \in \{1,\dots,n\}}{\min} \begin{align} \underset{\substack{i_1, \dots, i_m \in \{1, ..., N\}, \ i_1 \neq \ldots \neq i_m \\ x_{i_1}, \ldots, x_{i_m} \in \mathbb{R}_{\geq 0} \\ y_{i_1}, \ldots, y_{i_m} \in \mathbb{R}_{\geq 0}}}{\min} & \sum_{i \in \{i_1, \dots, i_m\}} f_i(x_{i},y_{i}) \\ & \sum_{i \in \{i_1, \dots, i_m\}} x_i = X \\ & \sum_{i \in \{i_1, \dots, i_m\}} y_i = Y \end{align} $$

What would be the most efficient way of solving this numerically?

$\endgroup$
1
  • $\begingroup$ unless each $f_i$ is piecewise linear convex, solve it as MIP $\endgroup$
    – LinAlg
    Nov 20, 2019 at 18:48

1 Answer 1

2
$\begingroup$

You can solve this problem via mixed integer linear programming as follows. Let binary decision variable $z_i$ indicate whether function $f_i$ is selected, let binary decision variable $u_i$ indicate whether $x_i > A_i$, and let binary decision variable $v_i$ indicate whether $y_i > B_i$. Let $w_i$ represent $z_i\cdot f_i(x_i,y_i)$, to be linearized. The problem is to minimize $\sum_{i=1}^N w_i$ subject to: \begin{align} \sum_{i=1}^N x_i &= X\\ \sum_{i=1}^N y_i &= Y\\ 1 \le \sum_{i=1}^N z_i &\le n\\ 0 \le x_i &\le X z_i &\text{for $i\in\{1,\dots,N\}$} \\ 0 \le y_i &\le Y z_i &\text{for $i\in\{1,\dots,N\}$} \\ x_i - A_i &\le (X - A_i) u_i &\text{for $i\in\{1,\dots,N\}$} \\ y_i - B_i &\le (Y - B_i) v_i &\text{for $i\in\{1,\dots,N\}$} \\ \alpha_i x_i - r_i &\le \alpha_i A_i(1 - u_i) &\text{for $i\in\{1,\dots,N\}$}\\ \delta_i y_i - s_i &\le \delta_i B_i(1 - v_i) &\text{for $i\in\{1,\dots,N\}$}\\ r_i + s_i + C_i - w_i &\le C_i(1 - z_i) &\text{for $i\in\{1,\dots,N\}$}\\ r_i, s_i, w_i &\ge 0 &\text{for $i\in\{1,\dots,N\}$} \end{align} The final three families of "big-M" constraints enforce the following three implications: \begin{align} u_i = 1 &\implies r_i \ge \alpha_i x_i \\ v_i = 1 &\implies s_i \ge \delta_i y_i \\ z_i = 1 &\implies w_i \ge r_i + s_i + C_i \end{align}

$\endgroup$
1
  • $\begingroup$ By the way, this formulation is a good candidate for Dantzig-Wolfe decomposition with three linking constraints and a subproblem for each $i$. $\endgroup$
    – RobPratt
    Nov 22, 2019 at 18:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .