Analysis of some combinatorial optimization problems in telecommunication and transportation

We study three combinatorial problems arising in telecommunication and transportation. First, the bulk cargo ship scheduling problem, faced by the Military Sealift Command during war-time exercises and in the event of war, deals with the transportation of oil cargos using a fleet of tankers. Second, the fiber optic network design problem arising due to unique technological and cost characteristics of the fiber optic technology. The combinatorial problem is a network design problem where there are costs associated with construction of edges, and rewards accrue by providing a connection (i.e., an undirected path) between pairs of nodes. The objective is to find the set of edges that maximizes the net reward. Third, the 1-tree relaxation of the symmetric traveling salesman problem (TSP) is a well-known and much-investigated lower bounding relaxation for the TSP. We develop a dual ascent algorithm to optimize the 1-tree relaxation bound. All the three problems are solved computationally and results presented