1 Use the branch and bound method to solve the following Integer Programming problem:
2 Water from a proposed desalination plant is to be pumped through an existing network of pipes leading from the plant to a storage dam. The map in Figure 1 below represents the network of pipes where the nodes (2 – 13) represent pumping stations and node (1) is the desalination plant and node (14) is the storage dam. The numbers on the arcs denote the maximum flow for each pipe in Megalitres per day. Moreover, flow in each pipe is restricted to one way but can be in either direction (see Figure 1 below).
Figure 1: Map of water pipeline network showing maximum flow restriction in each pipeline section.
(a) What is the maximum volume of water (in Megalitres) that can be pumped per day from the desalination plant to the storage dam?
(b) Indicate clearly on a diagram the direction in which the water should be pumped in the network in order to maximize the volume of water pumped per day.
(c) To satisfy the manufacturers specifications each pumping station must be connected to a network of higher quality pipes. The costs for upgrading each section of pipeline to the higher quality pipeline (in millions of dollars) are shown in Figure 2. The local council proposes to only initially upgrade some of the pipes so that the plant, dam and each pumping station, (1) through (14), is linked to every other location by sections consisting of only upgraded pipes.
Which pipes should be upgraded if costs are to be minimized?
3. A manager of theme park needs to check the paths between the park’s attractions are clean and tidy before opening for the day. To do this the manager will choose a route such that she travels along each path once and once only to see and check if it is suitably clean. She does not mind if she has to pass through an attraction more than once as long she only travels along each path once and that the route begins and ends at the main gate located at L. Figure 3 shows the main areas of the theme park with the main gate designated as L and the attractions denoted by A, B, C, . . . , K, M. The paths between each of the attractions and with the main gate are
denoted as a, b, c, . . . , w.
Figure 3: A map of the theme park with the gate L and attractions at A, B, C,. . . , K, M.
(a) Determine the route (if possible) that would satisfy manager’s requirements. Draw this route. What type of path is this route?
(b) A visitor to the theme park wants to see all the attractions at A, B, C, . . . , K, and M by beginning at the main gate L and finishing at L. However the visitor gets easily bored and so only wants to visit each attraction once and once only.
Determine the route (if possible) that would satisfy visitor’s requirements. Draw this route.
What type of path is this route?
4. Figure 4 below shows the travel times between 14 customer locations, and the travel times between some of these locations and the warehouse (W). What is the shortest travel time from the warehousento each of the customers? Present your answer in a table with three columns showing:
Customer number,
The shortest time, and,
The associated route.
