for $u \geq 0$ the Lagrangian relaxed problem becomes

\begin{array}{l} \text{minimize} \quad -2x_1 - x_2 - x_3 - 0.5x_5 - u(-x_1 - x_3 + 1) \\ (P_u) \quad \text{subject to} \quad x_1 + x_2 \leq 1, \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x_3 + x_4 + x_5 = 1, \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x_j \in \{0, 1\}, \quad j = 1, \dots, 5. \end{array}

For $u = 1$ we get

\begin{array}{l} \text{minimize} \quad -x_1 - x_2 - 0.5x_5 - 1 \\ (P_1) \quad \text{subject to} \quad x_1 + x_2 \leq 1, \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x_3 + x_4 + x_5 = 1, \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x_j \in \{0, 1\}, \quad j = 1, \dots, 5. \end{array}

Note, there is no constraint connecting the variables $x_1, x_2$ with the variables $x_3, x_4, x_5$ . We can, therefore, consider $(P_1)$ as two independent problems

\begin{array}{l} \text{minimize} \quad -x_1 - x_2 - 1 \\ \text{subject to} \quad x_1 + x_2 \leq 1, \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x_j \in \{0, 1\}, \quad j = 1, 2 \end{array} \begin{array}{l} \text{minimize} \quad -0.5x_5 \\ \text{subject to} \quad x_3 + x_4 + x_5 = 1, \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x_j \in \{0, 1\}, \quad j = 3, 4, 5, \end{array}

and finding optimal solutions to these becomes trivial. The two optimal solutions are

x^1 = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \end{pmatrix} \quad \text{and} \quad x^2 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 1 \end{pmatrix}.