How can the formulation of $P2$ guarantee that it is a relaxation of $P1$? (if $w=0$, $1$ is much bigger than $2$).
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Adding a variable does have an important effect on the solution space. Just as a numerical test, the solution space of $P_2$ is around twice greater than $P_1$. However, what you mean by relaxation? I think, by omitting the variable $w$ still those can not be equivalent. $\endgroup$A.Omidi– A.Omidi2024-10-30 07:17:47 +00:00Commented Oct 30, 2024 at 7:17
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
First, rewrite $P_1$ by expressing the coefficient of the nearest integer:
$$P_1 = \left\{\left(x_1-x_2+2x_3-x_4+3x_5\right) + \left(\frac{3}{4}x_1 + \frac{1}{3}x_2 + \frac{1}{2}x_3 +\frac{7}{12}x_4 + \frac{1}{6}x_5\right) = 2 + \frac{2}{3} \right\}$$
where the first term, $\left(x_1 - x_2 + 2x_3 - x_4 + 3x_5\right)$, is an integer since $x \in Z_+^5$.
Hence, the equality above can be rearranged as:
$$ \bar{P}_1 = \left\{\left(\frac{3}{4}x_1 + \frac{1}{3}x_2 + \frac{1}{2}x_3+ \frac{7}{12}x_4 + \frac{1}{6}x_5\right) = w + \frac{2}{3}, \forall w \in Z_1^+ \right\} = P_2$$
Thus, we have shown that any solution $\bar{x}$ from $P_1$ satisfies $\bar{x} \in P_2$.
Next, find a counterexample ($\hat{x}$) such that $\hat{v} \in P_2$ but $\hat{x} \notin P_1$:
$\hat{x} = (0, 0, 0, 0, 10)$ and $w = 1$ is $\in P_2 \notin P_1$
Hence, $P_1 \subset P_2$, which is equivalent to saying that $P_2$ is a relaxation of $P_1$.
$\begingroup$
$\endgroup$
You can answer the question by considering the following rephrasing: given any feasible solution $x$ to $(P_1),$ does there exist a nonnegative integer $w$ such that $(x,w)$ is feasible in $(P_2)?$
