3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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$
$\endgroup$
11
  • $\begingroup$ Can you please be more precise in your notations and correct use of Mathjax? It would benefit the comment a lot. Also, I assume you replace the function $g$ in the constraint, like $\sum_{i=1}^n D_i\sum_{j=1}^3 a_jx_j = \beta\sum_{i=1}^n D_i$ ? $\endgroup$ Commented Dec 1, 2022 at 10:49
  • $\begingroup$ Cleaned up a bit. Lhs of first constraint is like $\sum_{i}^n D_i \sum_{i}^n z_i$. Is $\sum_i D_i$ the same on both sides? Then you can check if eliminating it in the first constraint makes any difference to the solution. $\endgroup$ Commented Dec 1, 2022 at 12:26
  • $\begingroup$ I find it hard to see how this would work, let alone implement.. I get the idea, but the answer is just written really confusing. Also, your notation is mixed up, sometimes you say $b_i$, while you mean $b_1$ for example. Please take your time to check notations and it's also a small effort to use Mathjax correctly, eg $\beta$ and $beta$ is only a slash away. Then if you could show how the objective function is written, which decision variables there are and what the complete set of constraints is, I'm glad to accept. $\endgroup$ Commented Dec 1, 2022 at 14:35
  • $\begingroup$ I have edited my answer $\endgroup$ Commented Dec 1, 2022 at 15:02
  • $\begingroup$ a's are like dummy/temp variables that make $z_i$ take one of the x's. If $a_1$ is 1 then $z_i = x_1$. $\endgroup$ Commented Dec 1, 2022 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.