Is it somehow possible to apply local branching in branch-and-price?

In branch-and-bound it is easy to add a constraint that allows at most k decision variables to change compared to a given solution.

However, in branch-and-price we have to deal with fractional solutions. I don't know how to add a constraint in the master and pricing problem such that at most k decision variables differ compared to the given solution due to fractional solutions.

Is it possible at all? Or is the master and pricing problem the wrong place and including such a constraint somehow in the branching rule is more reasonable?

Does anyone successfully integrated local branching into branch-and-price? It would be nice to see some approaches or at least to have a fruitful discussion about this topic!

Lets consider the Cutting Stock Problem.

Gilmore & Gomory formulation of the restricted master problem is

$$ min\sum_{p\in P'}\lambda_p$$

$$ s.t. \quad \sum_{p\in P'}a_{ip}\lambda_p = d_i \quad [\pi_i] \quad i \in [n]$$

$$ \lambda_p \geq 0 \quad\quad\quad p\in P'$$


$$ P' \subseteq P=\{(a_1,\ldots,a_n)^t \in \mathbb{Z}_+^n | \sum\limits_{i=1}^n l_ia_i \leq L\}$$

a subset of variables.

Optimal dual

$$\pi^t = (\pi_1,\ldots,\pi_n)$$

Pricing problem

$$ z = \min_{p \in P} \bar{c}_p = \min_{p \in P} 1 - (\pi_1,\ldots,\pi_n)\cdot (a_{1p},a_{2p},\ldots,a_{np})^t$$

$$ = 1 - max\sum\limits_{i=1}^n \pi_i x_i$$

$$ s.t. \quad \sum\limits_{i=1}^n l_i x_i \leq L $$

$$ x_i \in \mathbb{Z}_+ \quad i\in [n]$$

Let $a^* = (a^*_1,\ldots,a^*_n)^t$ be a solution to the master problem.

What constraint (if possible and reasonable?) to add such that at most k variables differ from a*?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.