| 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. |
