## 5 Price-and-Branch FMP Solution Algorithm
### Algorithm Description  
As already mentioned, the size of family \(\widehat{\mathcal{C}}\), i.e., the number of all valid c-sets, increases exponentially with respect to the network size. That is why the formulation of \(\text{FMP}(\mathcal{C})\) is non-compact, with the number of variables and constraints growing exponentially with the network size. Thus, to find a globally optimal solution of FMP, i.e., when all c-sets in \(\widehat{\mathcal{C}}\) are considered, we need a way for generating the c-sets needed for achieving such a solution. Our approach is to apply the column and constraint generation method to the liner relaxation of the MIP formulation (3) of \(\text{FMP}(\mathcal{C})\). Such a linear relaxation is obtained from formulation (3) by relaxing variables \(y_{sa}\) and \(T_{c}\), i.e, by letting them to be continuous. (Note that in this relaxation constraint \(y_{sa}\leq 1\) has not be added since in optimal solutions this condition will be fulfilled.) The problem dual to the considered relaxation is as follows. \[\text{DFMP}(\mathcal{C})\text{: max }W=\sum_{s\in\mathcal{S}}\sum_{w\in \mathcal{D}(s)}(\varphi_{sws}-\varphi_{sww}) \tag{4a}\] \[\sum_{w\in D(s)}\sigma_{swa}\leq n(s)\lambda_{sa},\quad s\in \mathcal{S},a\in\mathcal{A}\] (4b) \[\varphi_{swb(a)}-\varphi_{sww}(a)\leq\sigma_{swa},\quad s\in \mathcal{S},w\in\mathcal{D}(s),a\in\mathcal{A}\] (4c) \[\sum_{w\in\mathcal{W}(c)}B(m(c,w))\pi_{cw}=1,\quad c\in\mathcal{C}\] (4d) \[\sum_{w\in\mathcal{U}(c,w)}\lambda_{s(w,c)}\leq\pi_{cw},\quad s\in \mathcal{S},c\in\mathcal{C},w\in\mathcal{W}(c)\] (4e) \[\varphi_{sww}\in\mathbb{R},\quad s\in\mathcal{S},w\in\mathcal{D} (s),v\in\mathcal{V}\] (4f) \[\sigma_{swa}\in\mathbb{R}_{+},\quad s\in\mathcal{S},w\in \mathcal{D}(s),a\in\mathcal{A}\] (4g) \[\lambda_{sa}\in\mathbb{R}_{+},\quad s\in\mathcal{S},a\in\mathcal{A}\] (4h) \[\pi_{cw}\in\mathbb{R}_{+},\quad c\in\mathcal{C},w\in\mathcal{W}( c), \tag{4i}\]  
where the dual variables \(\varphi_{sww},\sigma_{swa},\lambda_{sa},\pi_{cw}\) correspond, respectively, to the primal constraints (3b)-(3e). At this point we note that, as it commonly happens in the case of dual problems, DFMP and in particular its objective function (4a), can hardly be interpreted in a rigid but understandable way. Thus, although some helpful intuition could be developed, it is virtually impossible to explain the interpretation of DFMP in a compact manner. Suppose that \(\lambda=(\lambda_{sa}^{*})_{s\in\mathcal{S},a\in\mathcal{A}}\) is a vector of optimal values of dual variables \(\lambda_{sa}\) and consider the following expression:  
\[P(c,\lambda^{*}):=\min_{\pi\geq 0,\sum_{w\in\mathcal{W}(c)}B(m(c,w))\pi_{w}=1}Q( \pi;c) \tag{5}\]  
where \(\pi=(\pi_{w})_{w\in\mathcal{W}(c)}\) and  
\[ \begin{split}& Q(\pi;c):=\\ &\sum_{w\in\mathcal{W}(c)}\sum_{s\in\mathcal{S}}\max\big{\{}0,\sum _{u\in\mathcal{U}(c,w)}\lambda_{s(w,u)}^{*}-\pi_{w}\big{\}}.\end{split}  \tag{6}\]  
Now consider the (dual) polytope of DFMP(\(\mathcal{C}\cup\{c\}\)), i.e., the domain of DFMP(\(\mathcal{C}\cup\{c\}\)), for a given c-set \(c\in\widehat{\mathcal{C}}\setminus\mathcal{C}\). Observe that \(P(c)\) expresses the sum of violation of the constraints (4e) corresponding to \(c\) in this polytope by the vector \(\lambda^{*}\) which is optimal for DFMP(\(\mathcal{C}\)). (Note that the rest of the constraints are not violated in the new polytope.) Finally, let \(c^{*}\in\widehat{\mathcal{C}}\setminus\mathcal{C}\) be a c-set that solves the so called pricing problem (PP):PP(\(\lambda^{*}\)): Find a c-set \(c\) in \(\widehat{C}\setminus\mathcal{C}\) that maximizes the value of \(P(c,\lambda^{*})\) defined in (5). Note that when \(P(c^{*},\lambda^{*})=0\) then no constraint is violated in DFMP(\(\mathcal{C}\cup\{c^{*}\}\)) and optimal solutions of DFMP(\(\mathcal{C}\)) are also optimal for DFMP(\(\widehat{C}\)), and the same holds for the considered linear relaxation of FMP(\(\mathcal{C}\)).