2
$\begingroup$

We have a table of data as follows $$\begin{array}{c|c|c|c|c} & b \leqslant a & a < b \leqslant 2a & 2a < b \leqslant 3a & 3a < b \leqslant 4a \\ \hline i=1 & e & 2d & 2d & 2d \\ \hline i=2 & - & e & d & d \\ \hline i=3 & - & - & e & \frac{2}{3}d \\ \hline i=4 & - & - & - & e \\ \hline \end{array}$$

The data inside every cell of this table corresponds to a parameter of the problem which we show by $c_i$.

How can we formulate $c_i$ without adding another index to $c$?

There seems to be a connection between the value of $i$ and the interval to which $b$ belongs (the coefficient of $a$) but I don't know how to model it.

EDIT

I think I should have mentioned that $a, b, e, d$ and $c_i$ are all parameters of the problem.

$\endgroup$

1 Answer 1

4
$\begingroup$

$z_{j} \in \{0,1\}$ equals 1 represents variable $b$ belongs to interval $j$. You can linearize interval relation as follows: $$ A_{j-1} \cdot z_{j} + \epsilon \cdot z_{j} \le b_{j} \le A_{j} \cdot z_{j} \quad \forall j \in {1,2,3,4} $$ Here, this leads to 4 binary variables $z_{j}$ and values of ${A_0}$,${A_1}$,${A_2}$,${A_3}$,${A_4}$ are $0$, $a$, $2a$, $3a$ and $4a$ respectively (assuming 0 to be lower bound of variable $b$). $\epsilon$ is introduced on LHS to handle strict less than condition.

variable $b$ is to be defined as $$ b = \sum_{j} b_{j} $$ and only one of the intervals has to be selected $$ \sum_{j} z_{j} = 1 $$ To achieve above linearization, you might consider using SOS Type-1 relation as well. If a is also a variable, you might have to write some Big-M constraints to linearize the same. finally, $c_{i}$ can be defined as follows: $$ c_{i} = \sum_{j\mid j\ge i} W_{ij} z_{j} $$ where $W_{ij}$ represents tabular parameters corresponding to row $i$ and column $j$

$\endgroup$
4
  • $\begingroup$ Thank you. As I mentioned in the edited question, $a,b,c,d,e$ are all parameters. Based on the problem instance, we know which column (interval) $b$ belongs to. Can't we simplify $c_i$ formulation? $\endgroup$
    – Vitamin Z
    Commented Jan 18, 2022 at 23:11
  • $\begingroup$ If c is a parameter and b's interval is known. Then, It is just looking up values in the table which can be pre-processed. Is this part of any mathematical/optimization model? $\endgroup$
    – anjikum
    Commented Jan 19, 2022 at 5:44
  • $\begingroup$ That is correct. Both $c$ and $b$ are known in advance. $c_i$ is the coefficient of a decision variable and we do look up the values in the table but I was thinking about how to write it because for each $i$, for any interval of $b$, when $i$ is equal to the coefficient of $a$ on the RHS, $c_i=e$ but when $i$ is less than the coefficient of $a$, $c_i=\frac{2}{\text{coefficient of $a$ on the LHS}}$. But I don't know to write this mathematically. $\endgroup$
    – Vitamin Z
    Commented Jan 19, 2022 at 9:46
  • $\begingroup$ Can you tell the usage of $c_i$? Is it part of any optimization model? $\endgroup$
    – anjikum
    Commented Jan 21, 2022 at 4:18

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.