Mathematical Foundations for Signal Processing, Communications, and Networking

However, when pricing involves the integer variables, the branching rule may compromise the tractability of the pricing process which is otherwise easy when the main LP relaxation is considered. To illustrate this important issue, consider the following nonbifurcated version of the noncompact L-P formulation (18.16):

$\min z$

(18.41a)

$\begin{array}{ll}{\displaystyle \sum _{p\in P_d}{u}_{dp}=1}\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.41b)

${\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_d}{h}_d{u}_{dp}\le }}\begin{array}{ll}{c}_e+z\hfill & e\in ℰ\hfill \end{array}$

(18.41c)

$\begin{array}{ll}{u}_{dp}\in \left\{0,1\right\}\hfill & d\in \mathcal{D},p\hfill \end{array}\in P_d.$

(18.41d)

with a hop-limit imposed on the paths in $\mathcal{P}$. Note that this time (18.41) has its compact N-L counterpart (see the remark after formulation (18.8) in Subsection 18.2.2). Still, the N-L formulation provides a worse lower bound than the LP relaxation of (18.41), since the former actually admits paths longer ...