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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.