Linear programming combination of variables

Question

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

Answer 1

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}

Answer 2

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.

Answer 3

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}$,