The usual location models contain a set of binary variables Yi indicating whether or not, a facility is built at location i. In this talk we discuss models using binary variables Ziq indicating whether a facility is built at location i AND is serving q clients. We relate formulations involving the new set of variables with previous known formulations. We also present and discuss a set of inequalities using the new set of variables and generated by the Chvatal-Gomory rounding method. We also discuss variations of the problem with nonlinear costs at the facilities (as these are easily modelled by the new variables). Computational results taken from instances with up to 100 client nodes and 20 facility nodes are presented for several variations of the location problem.

The size of the branch and bound tree for a mixed-integer solution can be signficantly reduced if a reasonably accurate estimate of the optimum objective function value is available early in the search process. We develop algorithms for providing such early estimates and show preliminary empirical evidence in support of the effectiveness of the method.

We first give a flow formulation for the problem of minimizing energy in multicast sessions in wireless ad hoc networks. This formulation is strengthened, and some alternative flow formulations of equal strength are constructed. Finally, computational results comparing the performance of these are given.

By various network extensions, we demonstrate how the minimum-energy problem introduced in the previous talk (Bauer) can be formulated as a minimum Steiner tree problem. We analyze the strength of the formulations hence obtained, and we show that the Steiner and flow models are equally strong.