An important problem that arises in the design of packet radio networks is that of scheduling access to the high speed communications channel in such a way as to avoid interference while keeping the frame length to a minimum. The broadcast scheduling problem is known to be NP-hard and to date, this problem has been formulated as a nonlinear discrete optimization problem for a given frame length, and solved via heuristic approaches by parametrically varying the length of the frame. This paper presents a linear integer programming formulation for the composite problem of maximizing channel utilization while minimizing the length of the frame. It then introduces a solution approach based on solving two relatively easier (though still NP-complete) integer programs in succession. Computational experiments are conducted on a set of benchmark cases and additional randomly generated problem instances. Results show that this sequential integer programming approach is very effective, solving all the problems optimally within a few seconds. These results imply that optimal solutions can be identified in very little time for problems of realistic size, and that heuristic approaches will be needed only when problems get much larger than those considered in the literature to date.

Packet radio networks use spatial time-division multiple-access to enable multiple network stations to communicate via the same frequency within the same time slot. Stations in close proximity are not allowed to use the same frequency, as their signals would interfere with each other. In this context, an important design problem is that of scheduling access to the high-speed communications channel in such a way as to maximize the utilization while avoiding interference and keeping the frame length to a minimum. This is frequently referred to as the broadcast scheduling problem and is known to be NP-hard. It is often formulated as a nonlinear discrete optimization problem for a given frame length and solved via heuristic approaches by parametrically varying the length of the frame. Despite this, the sizes of the problems solved have been small, with the solution times becoming prohibitive with increasing problem size. This paper introduces a set covering formulation for the problem and solves it optimally using branch and price. Columns are generated using a simple pricing heuristic whenever possible. A branching strategy adapted from [Vance, P. 1998. Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optim. Appl. 9 211–228] is used, while branching first on the number of time slots used. Extensive computational results show that this approach is very effective, identifying optimal solutions quickly even on problems significantly larger than those solved previously.

Online advertising continues to be a significant source of income for many Internet-based organizations. Recent indications of improved economic growth are having an impact on advertisement revenue, with the estimated online advertising revenue in the United States for the fourth quarter of 2003 totaling a record of $2.2 billion. A substantial portion of this income comes from banner advertisements, and efficient scheduling of these advertisements could result in a considerable increase in profits. The problem of scheduling banner advertisements has been observed to be intractable via traditional optimization techniques and has received only limited attention in the literature. In addition, all past attempts to address this problem have been based on an "all-or-nothing" framework, where a customer specifies the exact number of copies of the ad to be displayed over the planning horizon, if it is selected for display by the provider of the advertisement space. This paper extends it to a more realistic setting, where the customer is allowed to specify a set of acceptable display frequencies. The Lagrangian decomposition-based solution approaches presented in this paper are observed to provide good schedules in a reasonable period of time.

Cellular telecommunications systems tend to be more flexible than traditional ones. As a result, traditional approaches to telecommunications network design are often inappropriate for the design of cellular networks, and approaches that explicitly incorporate the increased flexibility into the design process need to be developed. This paper presents one such multiperiod cellular network design problem and solves it via a hybrid heuristic that incorporates ideas from linear programming (LP) and simulated annealing (SA). Extensive computational results comparing the performance of the heuristic with the lower bound obtained from the LP relaxation are presented. These results indicate that this price-influenced simulated annealing (PISA) procedure is extremely efficient, consistently providing solutions with average gaps of 0.30% or less in fewer than 30 s.

For a distributed database system to function efficiently, the fragments of the database need to be located, judiciously at various sites across the relevant communications network. The problem of allocating these fragments to the most appropriate sites is a difficult one to solve, however, with most approaches available relying on heuristic techniques. Optimal approaches are usually based on mathematical programming, and formulations available for this problem are based on the linearization of nonlinear binary integer programs and have been observed to be ineffective except on very small problems. This paper presents new integer programming formulations for the nonredundant version of the fragment allocation problem. This formulation is extended to address problems which have both storage and processing capacity constraints; the approach is observed to be particularly effective in the presence of capacity restrictions. Extensive computational tests conducted over a variety of parameter values indicate that the reformulations are very effective even on relatively large problems, thereby reducing the need for heuristic approaches.

Despite the slowdown in the economy, advertisement revenue remains a significant source of income for many Internet-based organizations. Banner advertisements form a critical component of this income, accounting for 40 to 50% of the total revenue. There are considerable gains to be realized through the efficient scheduling of banner advertisements. This problem has received only limited attention in the literature. This paper introduces formulations for an important version of the banner advertisement scheduling problem. Two solution approaches, one based on Lagrangean decomposition and the other based on column generation, are presented, along with extensive results based on 1,500 randomly generated data sets. These results suggest that, while both approaches do very well in general, column generation consistently performs better than Lagrangean decomposition, giving gaps of 0.0004% or better in 4.4 seconds or less, even on relatively large problem instances.

In any distributed processing environment, decisions need to be made concerning the assignment of computational task modules to various processors. Many versions of the task allocation problem have appeared in the literature. Intertask communication makes the assignment decision difficult; capacity limitations at the processors increase the difficulty. This problem is naturally formulated as a nonlinear integer program, but can be linearized to take advantage of commercial integer programming solvers. While traditional approaches to linearizing the problem perform well when only a few tasks communicate, they have considerable difficulty solving problems involving a large number of intercommunicating tasks. This paper introduces new mixed integer formulations for three variations of the task allocation problem. Results from extensive computational tests conducted over real and generated data indicate that the reformulations are particularly efficient when a large number of tasks communicate, solving reasonablylarge problems faster than other exact approaches available.

Handoff and cabling costs play key roles in the design of cellular telecommunications networks. Efficient homing of cells to switches can have a significant impact on each of these costs. In the presence of capacity constraints at the switches, the problem of assigning cells to switches becomes a difficult one to solve, with all effective solution approaches being based on heuristic techniques. This paper presents a hybrid heuristic which integrates ideas from linear programming into a simulated annealing framework. Extensive computational results are presented comparing the performance of the heuristic with the lower bound obtained from the linear programming relaxation. These results indicate that this price influenced simulated annealing (PISA) procedure is extremely efficient, usually providing solutions with gaps around 1% in less than 1 s.

Despite the slowdown in the economy, advertisement revenue remains a significant source of income for many Internet-based organizations. Banner advertisements form a critical component of this income, accounting for 40 to 50 percent of the total revenue. There are considerable gains to be realized through the efficient scheduling of banner advertisements. This problem has been observed to be intractable via traditional optimization techniques, and has received only limited attention in the literature. This paper presents a procedure to generate advertisement schedules under the most commonly used advertisement pricing scheme---the CPM model. The solution approach is based on Lagrangean decomposition and is seen to provide extremely good advertisement schedules in a relatively short period of time, taking only a few hundred seconds of elapsed time on a 450 MHz PC compared to a few thousand seconds of CPU time on a workstation that other approaches need. Additionally, this approach can be incorporated into an actual implementation with minimal alterations and hence is of particular interest.