SEARCH FILTERS
Time filter
Source Type

Perea-Vega D.,Ecole Polytechnique de Montréal | Girard A.,GERAD | Frigon J.-F.,Ecole Polytechnique de Montréal
IEEE Wireless Communications and Networking Conference, WCNC | Year: 2017

We study fast algorithms for the optimal power allocation in an OFDM-SDMA system when some users have minimum requirements for their downlink transmission rate. We first solve the unconstrained problem for which we propose a fast zero-finding technique that is guaranteed to find an optimal solution, and an approximate algorithm that has lower complexity but is not guaranteed to converge. For the rate-constrained problem, we propose two approximate algorithms. We present numerical results showing that the computation time for the iterative heuristic is about one order of magnitude faster than finding the exact solution with a numerical solver, and the non-iterative technique is an additional order of magnitude faster than the iterative heuristic. We also show that in most cases, the amount of infeasibility with the non-iterative technique is small enough that it can probably be used in practical systems. © 2017 IEEE.

Andres-Domenech P.,French National Institute for Agricultural Research | Martin-Herran G.,GERAD | Martin-Herran G.,University of Valladolid | Zaccour G.,GERAD | Zaccour G.,HEC Montréal
Ecological Economics | Year: 2015

We model the role of the world's forests as a major carbon sink and consider the impact that forest depletion has on the accumulation of CO2 in the atmosphere. Two types of agents are considered: forest owners who exploit the forest and draw economic revenues in the form of timber and agricultural use of deforested land; and a non-forest-owner group who pollutes and suffers the negative externality of having a decreasing forest stock. We retrieve the cooperative solution for this game and show the cases in which cooperation enables a partial reduction in the negative externality. We analyze when it is jointly profitable to abate emissions, when it is profitable to reduce net deforestation, and when it is optimal to do both (abate and reduce net deforestation). Assuming that the players adopt the Nash bargaining solution to share the total dividend of cooperation, we determine the total amount that the non-forest owners have to transfer to forest owners. Next, we define a time-consistent payment schedule that allocates over time the total transfer. © 2015 Elsevier B.V.

Aouchiche M.,GERAD | Hansen P.,HEC Montréal
Discrete Applied Mathematics | Year: 2017

The proximity π of a graph G is the minimum average distance from a vertex of G to all others. Similarly, the remoteness of G is the maximum average distance from a vertex to all others. The girth g of a graph G is the length of its smallest cycle. In this paper, we provide and prove sharp lower and upper bounds, in terms of the order n of G, on the difference, the sum, the ratio and the product of the proximity and the girth. We do the same for the remoteness and the girth, except for the lower bound on ρ/g, which is already known. © 2017 Elsevier B.V.

Ahmadi-Javid A.,Amirkabir University of Technology | Malhame R.,GERAD
Proceedings of the IEEE Conference on Decision and Control | Year: 2013

The optimality of a hedging control policy in a Markovian failure-prone manufacturing system subject to a constant rate of demand for parts is established for a long-run risk-averse criterion, which is the conditional value-at-risk of the steady-state instantaneous running cost. This extends the known classical result of optimality of hedging policies in failure prone manufacturing systems under the longrun average cost that is a risk-neutral criterion. © 2013 IEEE.

Caporossi G.,GERAD | Paiva M.,Federal University of Espirito Santo | Vukicevic D.,University of Split | Segatto M.,Federal University of Espirito Santo
Match | Year: 2012

In this paper, we present an edge and vertex decomposition of the Wiener index (W) that is related to the concept of betweenness centrality used in social networks studies. Some classical methods to compute W could easily be derived from this formulation and novel invariants may be defined by this mean. Another vertex decomposition of W is the transmission. If transmission and centrality are both vertex decompositions of W it seems that they are represent opposite concepts, however the nature of this relation is not always so clear. Some properties obtained with the AutoGraphiX software on betweenness, centrality and their relation to transmission are presented and proved.

Belhaiza S.,King Fahd University of Petroleum and Minerals | Audet C.,Ecole Polytechnique de Montréal | Hansen P.,GERAD
Automatica | Year: 2012

In this paper, we introduce the notion of set of -proper equilibria for a bimatrix game. We define a 01 mixed quadratic program to generate a sequence of -proper Nash equilibria and show that the optimization results provide reliable indications on strategy profiles that could be used to generate proper equilibria analytically. This approach can be generalized in order to find at least one proper equilibrium for any bimatrix game. Finally, we define another 01 mixed quadratic program to identify non-proper extreme Nash equilibria. © 2011 Published by Elsevier Ltd. All rights reserved.

Nourian M.,McGill University | Caines P.E.,University of Melbourne | Malhame R.P.,GERAD | Malhame R.P.,Ecole Polytechnique de Montréal
IEEE Transactions on Automatic Control | Year: 2014

This technical note presents a continuum approach to a non-Gaussian initial mean consensus problem via Mean Field (MF) stochastic control theory. In this problem formulation: (i) each agent has simple stochastic dynamics with inputs directly controlling its state's rate of change and (ii) each agent seeks to minimize by continuous state feedback its individual discounted cost function involving the mean of the states of all other agents. For this dynamic game problem, a set of coupled deterministic (Hamilton-Jacobi-Bellman and Fokker-Planck-Kolmogorov) equations is derived approximating the stochastic system of agents as the population size goes to infinity. In a finite population system (analogous to the MF LQG framework): (i) the resulting decentralized MF control strategies possess an $\epsilon N-Nash equilibrium property where$\epsilon N goes to zero as the population size $N$ approaches infinity and (ii) these MF control strategies steer each individual's state toward the initial state population mean which is reached asymptotically as time goes to infinity. Hence, the system with decentralized MF control strategies reaches mean-consensus on the initial state population mean asymptotically as time goes to infinity. © 1963-2012 IEEE.

Talgorn B.,GERAD | Le Digabel S.,McGill University | Kokkolaras M.,Ecole Polytechnique de Montréal
Journal of Mechanical Design, Transactions of the ASME | Year: 2015

Typical challenges of simulation-based design optimization include unavailable gradients and unreliable approximations thereof, expensive function evaluations, numerical noise, multiple local optima, and the failure of the analysis to return a value to the optimizer. One possible remedy to alleviate these issues is to use surrogate models in lieu of the computational models or simulations and derivative-free optimization algorithms. In this work, we use the R dynaTree package to build statistical surrogates of the blackboxes and the direct search method for derivative-free optimization. We present different formulations for the surrogate problem (SP) considered at each search step of the mesh adaptive direct search (MADS) algorithm using a surrogate management framework. The proposed formulations are tested on 20 analytical benchmark problems and two simulation-based multidisciplinary design optimization (MDO) problems. Numerical results confirm that the use of statistical surrogates in MADS improves the efficiency of the optimization algorithm. Copyright © 2015 by ASME.

Anily S.,Tel Aviv University | Gendreau M.,University of Montréal | Laporte G.,GERAD
Networks | Year: 2011

This article considers the swapping problem on a tree. In this problem at most one object of some type is available at each vertex, and each vertex also requests at most one object of a given type. The total demand and the total supply of each object type are identical. The problem is to determine a minimum cost routing plan starting and ending at a prespecified vertex which is the depot, for a single vehicle of unit capacity and m object types, so that all vertex requests are satisfied. We consider the preemptive mode in which objects may be temporarily dropped along the way. It is shown that this problem is NP-hard. A heuristic with a worst-case performance ratio of 1.5 is developed. Finally, it is shown that the case where m = 1 is polynomially solvable. © 2011 Wiley Periodicals, Inc.

Audet C.,Ecole Polytechnique de Montréal | Dang K.-C.,GERAD | Orban D.,Ecole Polytechnique de Montréal
Mathematical Programming Computation | Year: 2014

Opal is a general-purpose system for modeling and solving algorithm optimization problems. Opal takes an algorithm as input, and as output it suggests parameter values that maximize some user-defined performance measure. In order to achieve this, the user provides a Python script describing how to launch the target algorithm, and defining the performance measure. Opal then models this question as a blackbox optimization problem which is then solved by a state-of-the-art direct search solver. Opal handles a wide variety of parameter types, it can exploit multiple processors in parallel at different levels, and can take advantage of a surrogate blackbox. Several features of Opal are illustrated on a problem consisting in the design of a hybrid sort strategy. © 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.