0
$\begingroup$

I am trying to formulate the following linear programming problem.

My inputs are the following:

  • A set of $N$ tables $\Pi_1, \dots, \Pi_N$
  • A cost budget $G$

I have the following decision variables:

  • $X_i$, $i \in [1, N]$ for whether or not we will perform transformation $X$ on table $\Pi_i$
  • $Y_i$, $i \in [1, N]$ for whether or not we will perform transformation $Y$ on table $\Pi_i$
  • $Z_i$, $i \in [1, N]$ for whether or not we will perform transformation $Z$ on table $\Pi_i$

The objective function is as follows:

min: $A_i\cdot X_i + B_i \cdot Y_i + C_i \cdot Z_i + D_i \cdot X_i + E_i \cdot Y_i + F_i \cdot Z_i$

where $A_i, B_i, C_i$ constants that influence the runtime of the original workload and $D_i, E_i, F_i$ calculate the runtime of the transformation.

And here are my constraints:

  • $X_i, Y_i, Z_i \in \{0, 1\}$
  • $Y_i + Z_i \leq 1$ as we do not want to both perform transformation $Y$ and $Z$ on a table
  • $Y_i \leq X_i$, as we have an advantage by applying transformation $Y$ only if we have performed transformation $X$ first
  • $T_i\cdot X_i + U_i\cdot Y_i + V_i\cdot Z_i \leq G$, where $G$ is a cost budget and $T_i, U_i, V_i$ is the cost of a transformation $X_i, Y_i, Z_i$ for $\Pi_i$ respectively.

My problem is the following: If we apply more than one transformations on a table, let's say $X$ and $Z$ for convenience then we have a discount factor, meaning that we won't have to pay both $A_i$ and $C_i$ runtime wise and $T_i$ and $V_i$ cost-wise. We will have a constant that is smaller than the sum of these two constants. I can calculate how much smaller this would be. How can we represent this in the problem? Should I have combined variables $XY$, $XZ$, $YZ$, $XYZ$ that are indicator variables that represent the combinations? Or is there another way to solve this type of linear programming problems?

Thanks a lot

$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

Out of the $2^3=8$ combinations $(X_i,Y_i,Z_i)$, only $5$ are feasible: \begin{matrix} X_i & Y_i & Z_i \\ \hline 0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} So introduce binary variables $w_{ij}$ for $i\in\{1,\dots,N\}$ and $j\in\{1,\dots,5\}$, precompute the objective coefficients $c_{ij}$ and constraint coefficients $a_{ij}$, and minimize $\sum_{i,j} c_{ij} w_{ij}$ subject to linear constraints \begin{align} \sum_j w_{ij} &= 1 &&\text{for all $i$} \\ \sum_{i,j} a_{ij} w_{ij} &\le G \end{align}

$\endgroup$
1
  • $\begingroup$ Thanks! That's what I ended up doing. $\endgroup$ Commented Mar 7, 2023 at 7:40
0
$\begingroup$

It seems you need a binary variable for each table, that is $0$ if no transformation happened, and $1$ if at least 1 transformation happened. equivalently you mean : $$ \gamma_i \equiv X_i \lor Y_i \lor Z_i \quad \forall i. $$ So this can be added to model by $$ X_i \leq \gamma_i \\ Y_i \leq \gamma_i \\ Z_i \leq \gamma_i \\ \gamma_i \leq X_i+Y_i+Z_i. $$ These constraints force $\gamma_i$ to be 1 if even one of transformations is supposed to apply. and make it $0$ if $X_i=Y_i=Z_i=0$.
therefore in cost function and runtime budget just use $\gamma_i$ for table $i$ instead of all transformation variables.

$\endgroup$
2
  • $\begingroup$ Thanks! Then how should I incorporate the constants if multiple transformations are applied to a table? Because the $A_i$ for example is different if we apply only $X_i$ or $X_i$ and $Y_i$ together. $\endgroup$ Commented Mar 3, 2023 at 10:37
  • 1
    $\begingroup$ if for constant $i$ , $A_i$, $B_i$ and $C_i$ are not same so it means it's important which combination of transformations are applied. and if you apply for example $X_i$ and $Y_i$ but the runtime isn't $A_i+B_i$ so it means the optimization model is not correct for problem and you should break the problem into more microstate detailed cases. for example for Table $i$ the states are $\{ 0,X_i,Y_i,Z_i,X_iY_i,X_iZ_i,Y_i,Z_i,X_iY_iZ_i \}$. and you should define a cost (and budget) for each one of these 8 states! $\endgroup$ Commented Mar 3, 2023 at 11:18
0
$\begingroup$

If i understand your problem you may need binary variables like $ \delta_{i,xy},\delta_{i,xz},\delta_{i,yz}$ and following constraints
$ x_i + y_i -1 \le \delta_{i,xy}$ (1)
$ \delta_{i,xy} \le x_i$ (2)
$ \delta_{i,xy} \le y_i$ (3)
Likewise for $ \delta_{i,yz}, \delta_{i,xz}$ assuming your $ x,y,z$ are binary.
So your $ \delta_{xy} = 1$ only when corresponding variables $ x,y = 1$

If $ x,y,z$ are continuous then constr (1) can be
$ x_{i}+y_{i}-M \le M\delta_{i,xy}$ where $x_i, y_i \le M \le max(x_i+y_i,0)$

Assuming $ ab$ is your discount cost, in your objective you can replace $ x,y$ part with
$ a_i(x_i-\delta_{i,xy}) + b_i(y_i -\delta_{i,xy}) + ab\delta_{i,xy}$+.....continue with $c,d,e,f$ with $ \delta_{xz},\delta_{yz}$,

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.