Modelling a nonlinear minimization problem with a nested function

Question

I'm thinking about the following problem:

Suppose you have $n$ items and every item $i$ has constants $D_i, p_i$ and $c_i$. $D_i$ is the demand for an item and $p_i$ is the price for that item. Now $c_i$ is the cumulative demand, so $c_i = \sum_{j=1}^i D_i$ for $i = 1, 2, \dots, n$ and all the items are ranked in a descending order in function of $D_i$, so $D_i \ge D_{i+1}$ and $c_n = 1$, $c_1 = \frac{D_1}{\sum_{i=1}^n D_i}$.

Then I got a function $g$ that takes in as arguments $c_i, b_1, b_2, x_1, x_2$ and $x_3$, where $b_1, b_2, x_1, x_2$ and $x_3$ will be my decision variables.

This function $g$ returns a number for every item $i$ based on the cumulative demand $c_i$, 2 boundary variables $b_1, b_2$ and 3 variables $x_1, x_2, x_3$ that are linked to $b_1$ and $b_2$ via a logical, conditional expression. Let $b_1, b_2 \in [0, 1 ]$ and $b_1 \le b_2$. For $x_1, x_2, x_3$, there is the constraint $0 \le x_1, x_2, x_3 \lt 1$.

To show the output of the function $g$, say

$b_1 = 0.80, b_2 = 0.95$

and

$x_1 = 0.99, x_2 = 0.96, x_3 = 0.92$

, then for an item $i$, if we have $c_i = 0.82$, then $g_i(c_i, b_1, b_2, x_1, x_2, x_3) = 0.96$ So the function $g$ evaluates $c_i$ by performing the following if statement:

if $c_i \le b_1$ then $x_1$, if $b_1 \lt c_i \le b_2$ then $x_2$, else $x_3$.

The function $g$ thus returns one of the variables $x_1, x_2$ or $x_2$. Now the cost function that I want to minimize is a nonlinear function $f$ that takes arguments $D_i, p_i$ and the function $g$ and I want to minimize wrt $b_1, b_2, x_1, x_2$ and $x_3$.

One major constraint is $$\frac{\sum_{i=1}^n D_i g_i(c_i, b_1, b_2, x_1, x_2, x_3)}{\sum_{i=1}^n D_i} = \beta$$ , where $0 \le \beta \lt 1$.

So if I think about it, I would write this minimization problem as:

$$\min_{x_1, x_2, x_3, b_1, b_2} \sum_{i=1}^n f(D_i, p_i, g_i(c_i, b_1, b_2, x_1, x_2, x_3))$$

s.t.

$$\frac{\sum_{i=1}^n D_i g_i(c_i, b_1, b_2, x_1, x_2, x_3)}{\sum_{i=1}^n D_i} = \beta$$

$$0 \le b_1 \le b_2 \le 1$$ $$0\le x_1, x_2, x_3 \lt 1$$

However, is this something feasible?

Answer 1

Change the const:
$\frac{\sum_{i=1}^n D_i g_i(c_i, b_1, b_2, x_1, x_2, x_3)}{\sum_{i=1}^n D_i} = \beta$ to $\sum_{i=1}^n D_i g_i(c_i, b_1, b_2, x_1, x_2, x_3) = \beta \sum_{i=1}^n D_i$

Your $g(x)$ can be expressed as constraints instead of writing a func.
Initialize 3 binary variables $a_i$ to 0.
For all i introduce the following constraints:

C1 = $b_1 - c_i \le Ma_1$ with M just big enough, say 10 or slightly more than $max(c_i, b_2,b_1)$.

C2 = $(c_i-b_1)(b_2-c_i) \le Ma_2$.

C3 = $c_i-b_2 \le Ma_3$

C4 = $\sum_{j}^3 a_j = 1$

C5 = $z_i = \sum_{j}^3 a_jx_j \ \forall i$: This will choose one of x's when corresponding a = 1.

Replace g(x,c,b) with z in the objective and first constraint.
First constraint turns to:
$\sum_{i=1}^n D_{i} z_{i} = \beta \sum_{i=1}^n D_i$

Objective: $\min_{x_1, x_2, x_3, b_1, b_2} \sum_{i=1}^n f(D_i, p_i, z_i)$

In case you want to linearize C2, then taking cue from here:
Two constraints: $c_i-b_i \le Mk_1$ and $b_2-c_i \le Mk_2$
Then $k_1+k_2 -1 \le a_2$. k's are also binary initialized to 0.

Summarized this would look like the following optimization problem:

Variables

$a_{i1}, a_{i2}, a_{i3} \in \{0, 1\}$ and initialized to $0$,

$0 \le x_1, x_2, x_3 \lt 1$,

$b_1, b_2 \in [0, 1]$

$k_{i1}, k_{i2} \in \{0, 1\}$ and initialized to $0$,

$0 \le z_i \lt 1$

Constants

$M = 10$.

Objective function

$$\min f(D_i, P_i, z_i)$$

Constraints

• $z_i = a_{i1}x_1 + a_{i2}x_2 +a_{i3}x_3$
• $b_1-c_i \le a_{i1}M$
• $c_i -b_2 \le a_{i3}M$
• $a_{i1}+a_{i2}+a_{i3} = 1$
• $c_i-b_1 \le Mk_{i1}$
• $b_2 - c_i \le Mk_{i2}$
• $k_{i1}+ k_{i2} - 1 \le a_{i2}$
• $\sum_{i=1}^n D_iz_i = \beta \sum_{i=1}^n D_i$