Upgrading a highway system in a developing country. The highway system in many developing countries may be a tree-shaped structure only. By tree we mean a network with no loops, or one in which only one route exists between any two cities of the network. We begin by assuming that such a tree network connects the major cities in such a country. The highways are currently in very poor condition, but a modest deposit of oil has been discovered offshore and a highway upgrading is desired.
The Transport Ministry has been allotted B units of money for highway improvement and wishes to spend it in a way that connects the maximum population with the improved highway system, which radiates out from the coastal city at point P. The population is assumed to be concentrated al the junction points of the tree network. Each link j that is improved connects a new increment of population ai to the system.
Further, no link can be constructed unless the link that immediately precedes it en route to the coastal city at P is also built.
Structure this problem as a zero-one programming problem with the objective of achieving the largest possible population on the continuous improved network subject to a budget constraint. By continuous network, we mean that no gaps are allowed m which an improved highway exists on one link and unimproved highway on an adjacent link and then improved highway on the other side of the unimproved link. Use the diagram to guide your constraints.
