# Multidimensional optimization problem

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?

• unless each $f_i$ is piecewise linear convex, solve it as MIP Nov 20, 2019 at 18:48

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}
• By the way, this formulation is a good candidate for Dantzig-Wolfe decomposition with three linking constraints and a subproblem for each $i$. Nov 22, 2019 at 18:24