The ring/ring problem is a hierarchical network design problem that uses a two-level network, in which each level is a ring with limited capacity. It is related to other hierarchical design problems and also to the vehicle routing problem. Rings are used in telecommunications because of their survivability, while hierarchical networks are useful for large networks. We propose an extended integer programming formulation for the problem and a branch-and-price algorithm to solve it. A relaxation of the pricing problem is considered and also primal and pricing heuristics to improve the performance of the algorithm. Computational experiments were conducted on instances derived from the literature and show the hardness to solve instances with high capacity.

BACKGROUND: The genomic similarity is a large-scale measure for comparing two given genomes. In this work we study the (NP-hard) problem of computing the genomic similarity under the DCJ model in a setting that does not assume that the genes of the compared genomes are grouped into gene families. This problem is called family-free DCJ similarity. RESULTS: We propose an exact ILP algorithm to solve the family-free DCJ similarity problem, then we show its APX-hardness and present four combinatorial heuristics with computational experiments comparing their results to the ILP. CONCLUSIONS: We show that the family-free DCJ similarity can be computed in reasonable time, although for larger genomes it is necessary to resort to heuristics. This provides a basis for further studies on the applicability and model refinement of family-free whole genome similarity measures.