Time filter

Source Type

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.

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.

Anjos M.F.,GERAD | Anjos M.F.,Ecole Polytechnique de Montréal | Chang X.-W.,McGill University | Ku W.-Y.,University of Toronto
Journal of Global Optimization | Year: 2014

The integer least squares problem is an important problem that arises in numerous applications.We propose a real relaxation-based branch-and-bound (RRBB) method for this problem. First, we define a quantity called the distance to integrality, propose it as a measure of the number of nodes in the RRBB enumeration tree, and provide computational evidence that the size of the RRBB tree is proportional to this distance. Since we cannot know the distance to integrality a priori, we prove that the norm of the Moore-Penrose generalized inverse of the matrix of coefficients is a key factor for bounding this distance, and then we propose a preconditioning method to reduce this norm using lattice reduction techniques. We also propose a set of valid box constraints that help accelerate the RRBB method. Our computational results showthat the proposed preconditioning significantly reduces the size of the RRBB enumeration tree, that the preconditioning combined with the proposed set of box constraints can significantly reduce the computational time of RRBB, and that the resulting RRBB method can outperform the Schnorr and Eucher method, a widely used method for solving integer least squares problems, on some types of problem data. © Springer Science+Business Media New York 2014.

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.

Rosat S.,GERAD | Rosat S.,Ecole Polytechnique de Montréal | Elhallaoui I.,GERAD | Elhallaoui I.,Ecole Polytechnique de Montréal | And 3 more authors.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2014

The integral simplex using decomposition (ISUD) algorithm [22] is a dynamic constraint reduction method that aims to solve the popular set partitioning problem (SPP). It is a special case of primal algorithms, i.e. algorithms that furnish an improving sequence of feasible solutions based on the resolution, at each iteration, of an augmentation problem that either determines an improving direction, or asserts that the current solution is optimal. To show how ISUD is related to primal algorithms, we introduce a new augmentation problem, MRA. We show that MRA canonically induces a decomposition of the augmentation problem and deepens the understanding of ISUD. We characterize cuts that adapt to this decomposition and relate them to primal cuts. These cuts yield a major improvement over ISUD, making the mean optimality gap drop from 33.92% to 0.21% on some aircrew scheduling problems. © 2014 Springer International Publishing.

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.