# constraint satisfaction via an LD solution

I'm going through the article in the following link lately and one point confuses me a lot. https://arxiv.org/pdf/1509.05001.pdf

So, the goal of this paper is to solve the following constrained binary quadratic programming. Here the parameters $A$, $Q$ and $b$ are all of integer values.

max $x^{T}Qx$ $s.t.,$ $Ax\leq b$ $\text{and}$ $x\in \{0,1\}^{n}$.

The authors consider the lagrangian relaxation of this problem in the following.

So, we have the following optimization problem $L_{\lambda}$.

$d(\lambda) = \text{min}_{x} x^{T}Qx+\lambda^{T}(Ax-b)$ $s.t.,$ $x\in \{0,1\}^{n}$.

And the further optimization problem $L$ in the following.

$L:\text{max}_{\lambda \in R_{+}^{m}}$ $d(\lambda)$

Then, a branch-and-bound tree is created (which I do not quite understand why to create the tree). In each node $u$ of the branch-and-bound tree, a lower bound is computed by solving the problem $L$ and the primal-dual pair $(x^{u},\lambda^{u})$ is obtained. we define the slack of constraint $i$ at a point $x$ to be $s_{i}$ = $b_{i} −a_{i}^{T}x$, where $a_{i}$ is the $i$-th row of $A$. Then the set of violated constraints at $x$ is the set $V = {i : si < 0}$. If $x^{u}$ is infeasible for the original problem, it must violate one or more constraints. Additionally, we define the change in slack for constraint $i$ resulting from flipping variable $j$ in $x^{u}$ to be $$\delta_{ij}=a_{ij}(2x_{j}^{u}-1).$$

I do not understand why $\delta_{ij}$ is defined in this way. For my understanding, $x^{u}\in \{0,1\}^{n}$, so when you flip the variable $j$ of $x^{u}$, you change it either from 0 to 1 or from 1 to 0. So, in either case, the change in slack for constraint $i$ can be calculated.

Did I miss something here ? Could anyone shed some light on what shall I do here? Many thanks for your time and attention.

$2x_{j}^{u}-1$ is either $+1$ if $x_{j}^{u}$ is 1 or $-1$ if $x_{j}^{u}$ is 0. Flipping $x_{j}^{u}$ from 0 to 1 or 1 to 0 will always change the contribution of $a_{ij}x_{j}$ to the left hand side of constraint $i$ (either by $+a_{ij}$ or $-a_{ij}$ This formula makes explicit that change in the slack for each constraint $i$.