IE$342-$ Spring $2024-$ Composite Exam

Name:

$(30$ points$)$ Due to the explosion of wireless communication activities available today.

companies have been working to determine available frequencies that can be aseigned

to wireless devices in a geographic area so that no interference between nearby desios

in possible. Suppose a communications company has esight towers in a small region.

which are denoted as nodes in the figure below. The edges connect the towers for

which frequencies may interfere.

Suppose that you have to assign two frequency values $($high and low$)$ to each tower,

which are represented by positive integers. These frequencies at each tower must

differ by at least $10.$ Moreover for each edge $(i,j),$ the high frequency of tower i and

the high frequency of tower $j$ must differ by at least $c_{ij}($the $c_{jy}$ values are given above

the edges$).$ Finally, the low frequencies of the towers must be unique.

Formulate an integer program that minimizes the span of frequencies used $($i$.$e$.$ the

lifference between the highest and lowest frequencies that are assigned to any tower$).$