Tham khảo tài liệu 'column generation for wdm optical network design phần 2', kỹ thuật - công nghệ, kĩ thuật viễn thông phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Column Generation - main steps Branching Strategy Efficient branching strategy for ODIMCF problem Barnhart et al. Ệ- Identify 2 fractional paths for the fractional flow with greatest demand and create 2 children nodes using the folloWing rule E C A D B F - Let A be a set of arcs originating at divergence node D . Define 2 subsets of arcs A1 and A2 such that E e A1 F e A2 A1 A2 A1n A2 0 and A1 u A2 A. - Create one child node that does not use any arcs in set A1 and one child node that does not use any arcs in set A2 - Important property Proposed branching strategy does not destroy the structure of the pricing problem. Branching Strategy cont. Since a single flow path in the WDM OND problem may visit the same node more than once we cannot apply similar branching strategy. Example Flow path A B using lps A F A C D F F B F D E B Solution Apply branching strategy that prohibits use of certain arcs only for specific lightpaths of a given commodity D B A C
