This thesis considers the problem of designing local networks with ring structures. For a given local network with a hub, central offices, and conduits which connect them, the problem is to find an optimal combination of ring structures which satisfies the given traffic requirements between all pairs of central offices and minimize total cost.
We decompose the problem into master problem and subproblem and formulate them as integer programming models. To solve the linear programming relaxation of the master problem, we develop a column generation procedure. We classify the subproblem into 12 problem categories depending on the types of ring structures and capacities. We solve subproblems to find the ring structures that can be added to the master problem as entering columns. Subproblems are solved by branch and cut algorithm which uses several valid inequalities. Computational results show that our algorithm can solve practically-sized problems to optimality or near optimality within reasonable time.
