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.
