3

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?

Steven01123581321
  • 1,043
  • 6
  • 12

1 Answers1

2

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$
Steven01123581321
  • 1,043
  • 6
  • 12
Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11
  • 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$ ? – Steven01123581321 Dec 01 '22 at 10:49
  • 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. – Sutanu Majumdar Dec 01 '22 at 12:26
  • 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. – Steven01123581321 Dec 01 '22 at 14:35
  • I have edited my answer – Sutanu Majumdar Dec 01 '22 at 15:02
  • 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$. – Sutanu Majumdar Dec 01 '22 at 18:55
  • Those constraints C1-C4 should help in that. – Sutanu Majumdar Dec 01 '22 at 19:02
  • I edited your answer with a summary on how I understand it. Could you please check and tell me if this is correct or if there are any mistakes. – Steven01123581321 Dec 01 '22 at 19:59
  • Looks ok to me. Thank you – Sutanu Majumdar Dec 01 '22 at 20:01
  • Shouldn't the binary variable $a$ be indexed on $i$ as well? – Steven01123581321 Dec 02 '22 at 09:32
  • Agreed. I made it like for $\forall i$ and while coding it would be automatically clear to the programmer. But definitely yes if it makes easy to read and implement the model. – Sutanu Majumdar Dec 02 '22 at 12:02
  • Also, $k_1$ and $k_2$ should get indexed on $i$ – Steven01123581321 Dec 02 '22 at 18:54