Search

In this work we propose and compare two new models for determining dominating trees (DT) of minimum cost in undirected weighted graphs. One model is based on a new representation of arborescences in digraphs, while the second one is obtained from the generalized spanning tree polytope. Computational results show that our models allow solving instances with up to 100 nodes to optimality, which is not possible to achieve with other models proposed in the literature. [ABSTRACT FROM AUTHOR]

Abstract: Let be a non directed graph with set of nodes V and set of weighted edges . The edges in and have deterministic and uncertain weights, respectively, with . Let be a given set of scenarios for the uncertain weights of the edges in . The stochastic maximum weight forest (SMWF) problem consists in determining a forest of G, one for each scenario , sharing the same deterministic edges and maximizing the sum of the deterministic weights plus the expected weight over all scenarios associated with the uncertain edges. In this work we present two formulations for this problem. The first model has an exponential number of constraints, while the second one is a new compact extended formulation based on a new theorem characterizing forests in graphs. We give a proof of the correctness of the new formulation. It generalizes existing related models from the literature for the spanning tree polytope. Preliminary results evidence that the SMWF problem can be NP-hard. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a two stage stochastic binary quadratic program for OFDMA wireless networks. The aim is to minimize the total power consumption of the network subject to user bit rates, sub-carrier and modulation constraints. We derive from the quadratic model a linear (LP) and a semidefinite programming (SDP) relaxation. Numerical results show tight and near optimal bounds for the SDP relaxation. [Copyright &y& Elsevier]

Abstract: In this paper, we study three robust optimization approaches [Adasme Pablo, Abdel Lisser and Ismael Soto, Robust Semidefinite Relaxations for a New Quadratic OFDMA Resource Allocation Approach, Working Paper Number 1522, LRI, University of Paris Sud, France]. The first one is based on the worst case scenario approach from Kouvelis and Yu [Kouvelis, and G. Yu, Robust discrete optimization and its applications, Kluwer Academic Publishers, 1997]. The second, corresponds to a scaled simplex polyhedral approach due to Bertsimas and Sim [Bertsimas Dimitris, and Melvyn Sim, The Price of Robustness, Operations Research, 52 (2004)] whilst the third, correspond to an ellipsoidal uncertainty approach proposed by Ben Tal and Nemirovski [Ben-Tal Aharon, and Arkadi Nemirovski, Robust solutions of Linear Programming problems contaminated with uncertain data, Mathematical Programming, Springer Berlin-Heidelberg, 88 (2000), 411–424]. The study of the different approaches is made on the basis of a binary quadratic constrained program (BQCP). We derive two semidefinite programming (SDP) relaxations for the first two approaches whilst we use a second order conic program for the last one. Numerical results are given for a resource allocation of OFDMA wireless networks. [ABSTRACT FROM AUTHOR]