Stochastic Value-at-Risk-Based Optimization and Independent Dominating Sets for Wireless Network Design

This paper studies new deterministic optimization models for wireless network design based on the Independent Dominating Set (IDS) structure. We first present deterministic formulations of the IDS and then extend them with risk-aware objectives using Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR) under the normal distribution. We compare all the proposed models in terms of solution quality and computational performance metrics such as branch and bound nodes, CPU time in seconds, and MIPGaps in percentages of the best solutions obtained in one hour of CPU time limit compared to the lower bounds reported by the Gurobi solver. Thus, we highlight the trade-offs between deterministic and risk-based formulations. Our contribution also lies in emphasizing the importance of an IDS-based structure as a flexible framework for network design. Subsequently, we show how VaR and CVaR capture uncertainty in transmission distance costs while maintaining tractable deterministic reformulations. Next, we demonstrate empirically that the deterministic solutions can be used as a warm start for the stochastic formulations. This leads to tight near-optimal solutions in a fraction of a second. Consequently, we further propose logic bender decomposition algorithms for the deterministic models to study the scalability of the proposed deterministic models, which allows one to obtain high-quality near-optimal solutions that can also be used as a warm start for stochastic models. Our numerical results confirm that the proposed models and algorithms provide near-optimal and optimal solutions for most of the instances tested, and a flexible and stochastic design framework. © 2013 IEEE.