tag:www.gerad.ca,2005:/en/papersCahiers du GERAD2019-05-16T15:39:51-04:0020tag:www.gerad.ca,2005:Paper/26802019-05-16T15:36:55-04:002019-05-16T15:39:51-04:00G-2019-29 : Heuristics for the dynamic facility location problem with modular capacitiesDaniel Aloise, Leandro C. Coelho, Caroline Rocha
<p>This paper studies the Dynamic Facility Location Problem with Modular Capacities (DFLPM). We propose a linear relaxation based heuristic (LRH) and an evolutionary heuristic that hybridizes a genetic algorithm with a variable neighborhood descent (GA+VND) to solve it. The problem is a generalization of several facility location problems and consists in determining locations and sizes of facilities to minimize location and demand allocation costs with decisions taken periodically over a planning horizon. The DFLPM is solved using two heuristics tailored for different network configurations and cost structures. Experiments are reported comparing them to a state-of-the-art mixed integer programming (MIP) formulation for the problem from the literature solved by CPLEX. For the existing benchmark instances, the solution generated by LRH improved by VND finds solutions within 0.03% of the optimal ones in less than half of the computation time of the state-of-the-art method from the literature. In order to yield a better representation of real-life scenarios, we introduce a new set of instances for which GA+VND proved to be an effective approach to solve the problem, outperforming both CPLEX and LRH methods.</p>2019-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26792019-05-16T15:32:46-04:002019-05-16T15:40:31-04:00G-2019-28 : Convex fuzzy \(k\)-medoids clusteringDaniel Nobre Pinheiro, Daniel Aloise, Simon Blanchard
<p><code>\(K\)</code>-medoids clustering is among the most popular methods for cluster analysis, but it carries several assumptions about the nature of the latent clusters. In this paper, we introduce the Convex Fuzzy <em>k</em>-Medoids (CFKM) model, whose underlying formulation not only relaxes the assumption that objects must be assigned entirely to one and only one medoid, but also that medoids must be assigned entirely to one and only one cluster. Moreover, due to its convexity, CFKM resolution is completely robust to initialization.
We compare our model with two fuzzy <em>k</em>-medoids clustering models found in the literature: the Fuzzy <em>k</em>-Medoids (FKM) and the Fuzzy Clustering with Multi-Medoids (FMMdd), both solved approximately by heuristics because of their hard computational complexity. Our experiments in synthesized and real-world data sets reveal that our model can uniquely discover
important aspects of clustered data which are inherently fuzzy in nature, besides being more robust regarding the
hyperparameters of the fuzzy clustering task.</p>2019-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26782019-05-16T15:28:48-04:002019-05-16T15:29:49-04:00G-2019-27 : Implementing a smooth exact penalty function for constrained nonlinear optimizationRon Estrin, Michael P. Friedlander, Dominique Orban, Michael A. Saunders
<p>We build upon Estrin et al. (2019) to develop a general
constrained nonlinear optimization algorithm based on a smooth
penalty function proposed by
Fletcher (1970,1973b). Although Fletcher's approach has historically
been considered impractical, we show that the computational kernels required
are no more expensive than those in other widely accepted methods for nonlinear
optimization. The main kernel for evaluating the penalty function and its
derivatives solves structured linear systems. When the matrices are available
explicitly, we store a single factorization each iteration. Otherwise, we
obtain a factorization-free optimization algorithm by solving each linear system
iteratively. The penalty function shows promise in cases where the linear systems
can be solved efficiently, e.g., PDE-constrained optimization problems when
efficient preconditioners exist. We demonstrate the merits of the approach, and
give numerical results on several PDE-constrained and standard test problems.</p>2019-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26772019-04-26T16:52:28-04:002019-04-29T09:40:09-04:00G-2019-30 : Constrained stochastic blackbox optimization using probabilistic estimatesCharles Audet, Kwassi Joseph Dzahini, Sébastien Le Digabel, Michael Kokkolaras
<p>This work introduces Stoch-MADS, a stochastic variant of the mesh adaptive direct search (MADS) algorithm designed for deterministic blackbox optimization. Stoch-MADS considers the constrained optimization of an objective function <code>\(f\)</code> whose values can only be computed through a stochastic blackbox with some random noise of an unknown distribution. The proposed algorithm uses an algorithmic framework similar to that of MADS and utilizes random estimates of true function values obtained from their stochastic observations to ensure improvements since the exact deterministic computable version of <code>\(f\)</code> is not available. Such estimates are required to be accurate with a sufficiently large but fixed probability and satisfy a variance condition. The ability of the proposed algorithm to generate an asymptotically dense set of search directions is then exploited to show that it converges to a Clarke-hypertangent stationary point of <code>\(f\)</code> with probability one, with the help of martingale theory.</p>2019-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26762019-04-10T12:06:55-04:002019-04-10T12:06:55-04:00G-2019-25 : The airline crew pairing problem with language constraintsFrédéric Quesnel, Guy Desaulniers, François Soumis
<p>In large commercial airlines, the monthly schedule (roster) of the crew members is usually determined by solving two problems sequentially, namely, the crew pairing problem (CPP) and the crew rostering problem (CRP). While the CPP finds a set of low-cost feasible anonymous pairings, the CRP assigns these pairings to the crew members to create a valid roster. The CRP often involves language constraints, which request language qualifications among the crew members operating some flights. In this case, the pairings returned by the CPP are not necessarily compatible with the qualifications of the available crew members, resulting in a large number of violated language constraints in the CRP. In this paper, we propose a new CPP variant, called the CPP with language constraints (CPPLC), that takes into account two types of soft language constraints that help producing more suitable pairings for satisfying the CRP language constraints. To solve the CPPLC, we develop a branch-and-price heuristic that includes an efficient partial pricing strategy for handling the large number of subproblems needed to model the language constraints. We also propose an acceleration technique to compute a high-quality (usually fractional) solution at the root node of the search tree. The proposed algorithm is tested on seven real-world datasets. We show that pairings produced by the CPPLC are better-suited for the CRP, resulting in a reduction of the number of violated CRP language constraints that varies between 59% and 96%, when compared to the pairings obtained from the traditional CPP.</p>2019-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26752019-04-10T12:02:43-04:002019-04-10T12:02:43-04:00G-2019-24 : Lagrangian duality for robust problems with decomposable functions: the case of a robust inventory problemFilipe Rodrigues, Agostinho Agra, Cristina Requejo, Erick Delage
<p>We consider a class of min-max robust problems in which the functions that need to be <em>robustified</em> can be decomposed as the sum of arbitrary functions. This class of problems includes many practical problems such as the lot-sizing problem under demand uncertainty.
By considering a Lagrangian relaxation of the uncertainty set we derive a tractable approximation that we relate with the classical dualization approach introduced by Bertsimas and Sim (2004) and also with the exact min-max approach. Moreover we show that the dual Lagrangian approach coincides with the affine approximation of the uncertainty set.</p>
<p>The dual Lagrangian approach is applied to a lot-sizing problem, which motivated our work, where demands are assumed to be uncertain and to belong to the uncertainty set with a budget constraint for each time period introduced by Bertsimas and Sim (2003, 2004).
This approach is also related to two classical robust approaches for this problem, the exact min-max approach introduced by Bienstock and Özbay (2008) and the dualization approach from Bertsimas and Thiele (2006).</p>
<p>Using the insights provided by the interpretation of the Lagrangian multipliers in the proposed dual model as penalties,
two heuristic strategies, a new Guided Iterated Local Search heuristic and a Subgradient Optimization method, are designed to solve more complex lot-sizing problems where additional practical aspects, such as setup costs, are considered. Computational results show the efficiency of the proposed heuristics which provide a good compromise between the quality of the robust solutions and the running time.</p>2019-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26742019-04-10T10:53:02-04:002019-04-10T13:50:46-04:00G-2019-26 : Flight-connection prediction for airline crew scheduling to construct initial clusters for OR optimizerYassine Yaakoubi, Simon Lacoste-Julien, François Soumis
<p>We present a case study of using machine learning classification algorithms to initialize a large scale commercial operations research solver (GENCOL) in the context of the airline crew pairing problem, where small savings of as little as 1% translate to increasing annual revenue by millions of dollars in a large airline.
We focus on the problem of predicting the next connecting flight of a crew, framed as a multiclass classification problem trained from historical data, and design an adapted neural network approach that achieves high accuracy (99.7% overall or 82.5% on harder instances). We demonstrate the usefulness of our approach by using simple heuristics to combine the flight-connection predictions to form initial crew-pairing clusters that can be fed in the GENCOL solver, yielding a 10x speed improvement and up to 0.2% cost saving.</p>2019-04-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26732019-04-05T10:52:10-04:002019-04-05T10:52:31-04:00G-2019-23 : Detecting periodicity from the trajectory of a random walk in random environmentBruno Rémillard, Jean Vaillancourt
<p>For nearest neighbor univariate random walks in a periodic environment, where the probability of moving depends on a periodic function, we show how to estimate the period and the function. For random walks in non-periodic environments, we find that the asymptotic limit of the estimator is constant in the ballistic case, when the random walk is transient and the law of large numbers holds with a non zero limit. Numerical examples are given in the recurrent case, and the sub-ballistic case, where the random walk is transient but the law of large numbers yields a zero limit.</p>2019-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26722019-04-05T10:40:25-04:002019-04-05T10:41:06-04:00G-2019-22 : Decremental clustering for the solution of \(p\)-dispersion problems to proven optimalityClaudio Contardo
<p>Given <code>\(n\)</code> points, a symmetric dissimilarity matrix <code>\(D\)</code> of dimensions <code>\(n\times n\)</code> and an integer <code>\(p\geq 2\)</code>, the <code>\(p\)</code>-dispersion problem (pDP) consists in selecting a subset of exactly <code>\(p\)</code> points in such a way that the minimum dissimilarity between any pair of selected points is maximum. The pDP is <code>\(NP\)</code>-hard when <code>\(p\)</code> is an input of the problem. We propose a decremental clustering method to reduce the problem to the solution of a series of smaller pDPs until reaching proven optimality. The proposed method can handle problems orders of magnitude larger than the limits of the state-of-the-art solver for the pDP for small values of <code>\(p\)</code>.</p>2019-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26712019-04-05T10:33:05-04:002019-04-05T10:33:05-04:00G-2019-21 : Time evolution of a differentiated oligopoly: The case of sustainable wineMichèle Breton, Lucia Sbragia
<p>We study the time evolution of a vertically and horizontally differentiated
oligopolistic industry, where firms compete in quantity and are divided into
groups producing one variety of a substitutable product. We assume that
firms can periodically revise their decision about which variety to produce.
For a general oligopoly with two varieties, we characterize the industry
composition in the steady state as a function of the parameter values. Our
results are applied to the case of the sustainable wine industry.</p>2019-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26702019-04-05T10:27:43-04:002019-04-05T10:27:43-04:00G-2019-03 : Practical guide to establishing a multi-criteria and multi-actor decision-making process: Steps and toolsCécile Aenishaenslin, Denise Bélanger, Camille Fertel, Valérie Hongoh, Bertrand Mareschal, Jean-Philippe Waaub
<p>The purpose of this guide is to present steps and tools to establish a
decision-aid process in an organization linked to public health. This
decision-aid process is based on a multi-criteria analysis and is open
to the potential participation of the actors (also called stakeholders)
involved in the problem being addressed by the decision-making process.</p>2019-01-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26692019-03-29T16:49:57-04:002019-04-01T10:19:55-04:00G-2019-20 : The inventory routing problem with demand movesAnnelieke Baller, Said Dabia, Guy Desaulniers, Wout E. H. Dullaert
<p>In the Inventory Routing Problem customer demand is satisfied from inventory which is replenished with capacitated vehicles. The objective is to minimize total routing and inventory holding cost over a time horizon. If the customers are located relatively close to each other, one has the opportunity to satisfy a part of the demand of a customer by inventory stored at another nearby customer. In the optimization of the customer replenishments, this option can be included to lower total inventory routing costs. This is for example the case for ATMs in urban areas where an ATM-user, that wants to withdraw money, could be redirected to another ATM. To the best of our knowledge, the possibility of redirecting end-users is new to the operations research literature and has not been implemented, but is being considered, in the industry. We formulate the Inventory Routing Problem with Demand Moves in which demand of a customer can (partially) be satisfied by the inventory of a nearby customer at a service cost depending on the quantity and the distance. We propose a branch-price-and-cut solution approach which is evaluated on problem instances derived from the literature. Cost improvements over the classical IRP of up to 10% are observed with average savings around 3%.</p>2019-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26682019-03-29T16:45:33-04:002019-04-12T14:04:01-04:00 G-2019-19 : CONICOPF: A tight-and-cheap conic relaxation with accuracy metrics for single-period and multi-period ACOPF problemsChristian Bingane, Miguel F. Anjos, Sébastien Le Digabel
<p>Computational speed and global optimality are a key need for pratical algorithms of the OPF problem. Recently, we proposed a tight-and-cheap conic relaxation for the ACOPF problem that offers a favourable trade-off between the standard second-order cone and the standard semidefinite relaxations for large-scale meshed networks in terms of optimality gap and computation time. In this paper, we show theoretically and numerically that this relaxation can be exact and can provide a global optimal solution for the ACOPF problem. Thereafter, we propose a multi-period tight-and-cheap relaxation for the multi-period ACOPF problem. Computational experiments using MATPOWER test cases with up to 500 buses show that this new relaxation is promising for real-life applications.</p>2019-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26672019-03-29T16:42:29-04:002019-04-03T16:20:18-04:00G-2019-02 : Guide pratique de mise en place d'un processus décisionnel multicritère et multi-acteurs : étapes et outilsCécile Aenishaenslin, Camille Fertel, Denise Bélanger, Bertrand Mareschal, Valérie Hongoh, Jean-Philippe Waaub
<p>Ce guide vise à présenter les différentes étapes et outils de mise en
place d'un processus d'aide à la décision, au sein d'une organisation
liée à la santé publique, basé sur une approche d'analyse multicritère
et ouvert à la participation potentielle des acteurs, parfois appelés
aussi parties prenantes, reliés au problème abordé par le processus
décisionnel.</p>2019-01-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26662019-03-22T11:09:41-04:002019-03-22T11:13:45-04:00G-2019-00 : Review of the book ``Derivative-Free and Blackbox Optimization'' by C. Audet and W. Hare, Springer Series in Operations Research and Financial Engineering, 2017, 302 pages, DOI 10.1007/978-3-319-68913-5Michael Kokkolaras
<p>In the interest of full disclosure, the reader is advised that I am biased positively towards the book considered here as I have collaborated with its first author several times during the last 19 years. In fact, the two of us served as guest editors of the last special issue on derivative-free and blackbox optimization appeared in this journal Audet and Kokkolaras (2016).</p>
<p>As an engineer, my primary appreciation of this book pertains to its invaluable contribution to the field of engineering design optimization. Numerical optimization problems in the modern era of computer-aided engineering design rely almost exclusively on simulation models to evaluate objective and constraint functions. Therefore, gradients may either not exist or require unreasonable and unjustifiable effort to be approximated with adequate precision if automatic differentiation is not an option. This is frequently the case with so called blackboxes, i.e., computational (we use the terms "computational" and "simulation" interchangeably to characterize a model) models that the user does not have access to. The only resort then is to use derivative-free optimization algorithms.</p>2019-01-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26652019-03-20T16:45:35-04:002019-03-20T16:48:33-04:00G-2019-17 : A regularization method for constrained nonlinear least squaresDominique Orban, Abel Soares Siquiera
<p>We propose a regularization method for nonlinear least-squares problems with equality constraints.
Our approach is modeled after those of Arreckx and Orban (2018) and Dehghani et al.
(2019), and applies a selective regularization scheme that may be viewed as a reformulation of an augmented Lagrangian.
Our formulation avoids the occurrence of the operator <code>\(A(x)^T A(x)\)</code>, where <code>\(A\)</code> is the Jacobian of the nonlinear residual, which typically contributes to the density and ill conditioning of subproblems.
Under boundedness of the derivatives, we establish global convergence to a KKT point or a stationary point of an infeasibility measure.
If second derivatives are Lipschitz continuous and a second-order sufficient condition is satisfied, we establish superlinear convergence without requiring a constraint qualification to hold.
The convergence rate is determined by a Dennis-Moré-type condition.
We describe our implementation in the Julia language, which supports multiple floating-point systems.
We illustrate a simple progressive scheme to obtain solutions in quadruple precision.
Because our approach is similar to applying an SQP method with an exact merit function on a related problem, we show that our implementation compares favorably to IPOPT in IEEE double precision.</p>2019-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26642019-03-20T16:42:11-04:002019-03-20T16:42:11-04:00G-2019-16 : A framework for peak shaving through the coordination of smart homesMichael David De Souza Dutra, Miguel F. Anjos, Sébastien Le Digabel
<p>In demand-response programs, aggregators balance the needs of generation companies and end-users. This work proposes a two-phase framework that shaves the aggregated peak loads while maintaining the desired comfort level for users. In the first phase, the users determine their planned consumption. For the second phase, we develop a bilevel model with mixed-integer variables and reformulate it as a single-level model. We propose an exact centralized algorithm and a decentralized heuristic. Our computational results show that the heuristic gives small optimality gaps and is much faster than the centralized approach.</p>2019-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26632019-03-20T16:39:13-04:002019-03-20T16:39:13-04:00G-2019-15 : Monotonic grey box optimizationCharles Audet, Pascal Côté, Catherine Poissant, Christophe Tribes
<p>We are interested in blackbox optimization for which the user is aware of monotonic behaviour of some constraints defining the problem.
That is, when increasing a variable,
the user is able to predict if a function increases or decreases,
but is unable to quantify the amount by which it varies.
We refer to this type of problems as "monotonic grey box" optimization problems.
Our objective is to develop an algorithmic mechanism that exploits this monotonic information
to find a feasible solution as quickly as possible.
With this goal in mind, we have built a theoretical foundation through a thorough study of monotonicity on cones of multivariate functions.
We introduce a trend matrix and two types of trend directions to guide the Mesh Adaptive Direct Search (MADS) algorithm when optimizing a monotonic grey box optimization problem.<br/>
Different strategies are tested on analytical test problems,
and on a real hydroelectric dam optimization problem.</p>2019-02-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26622019-03-15T10:00:36-04:002019-03-15T10:03:59-04:00G-2019-18 : Reinforcement learning in stationary mean-field gamesJayakumar Subramanian, Aditya Mahajan
<p>Multi-agent reinforcement learning has made significant progress in recent years,
but it remains a hard problem. Hence, one often resorts to developing learning algorithms
for specific classes of multi-agent systems. In this paper we study reinforcement
learning in a specific class of multi-agent systems systems called mean-field games.
In particular, we consider learning in stationary mean-field games. We identify two
different solution concepts -stationary mean-field equilibrium and stationary
mean-field social-welfare optimal policy- for such games based on whether the agents
are non-cooperative or cooperative, respectively. We then generalize these solution
concepts to their local variants using bounded rationality based arguments. For these
two local solution concepts, we present two reinforcement learning algorithms. We show
that the algorithms converge to the right solution under mild technical conditions and
demonstrate this using two numerical examples.</p>2019-03-01GERADinfo@gerad.catag:www.gerad.ca,2005:Paper/26612019-03-15T09:58:26-04:002019-03-15T09:58:26-04:00G-2019-14 : Long-term planning of a flexible generation portfolioNavdeep Dhaliwal, François Bouffard, Mark O'Malley
<p>We are witnessing an acceleration in the uptake of renewable energy in power
systems. Because of the associated variability and uncertainty of renewables, power systems need to
have an adequate supply of flexibility to allow for suitable management of short-term operations. So far
most of the work in this area has neglected how flexibility needs associated with renewables are fulfilled
as part of dispatchable generation capital investments decisions. To address this challenge, we propose
an approach to plan the dispatchable generation mix of a power system needed to counteract variability
and uncertainty of significant shares of variable renewable generation. The approach exploits the linear
time-invariant feature of variable generation using historical phase planes of capacity (in MW) and ramp
(in MW/min) to bridge the gap between long-term capacity planning and short-term intra-hour
flexibility. This approach is much more computationally tractable than other proposals, while also being
able to capture adequately short-term operational features like ramping and net load variability.
Numerical tests are performed on a realistic datasets to substantiate the effectiveness of the approach.</p>2019-02-01GERADinfo@gerad.ca