Search

Metaheuristic algorithms have become one of the preferred approaches for solving optimization problems. Finding the best metaheuristic for a given problem is often difficult due to the large number of available approaches and possible algorithmic designs. Moreover, high-performing metaheuristics often combine general-purpose and problem-specific algorithmic components. We propose here an approach for automatically designing metaheuristics using a flexible framework of algorithmic components, from which algorithms are instantiated and evaluated by an automatic configuration method. The rules for composing algorithmic components are defined implicitly by the properties of each algorithmic component, in contrast to previous proposals, which require a handwritten algorithmic template or grammar. As a result, extending our framework with additional components, even problem-specific or user-defined ones, automatically updates the design space. Furthermore, since the generated algorithms are made up of components, they can be easily interpreted. We provide an implementation of our proposal and demonstrate its benefits by outperforming previous research in three distinct problems from completely different families: a facility layout problem, a vehicle routing problem and a clustering problem., SCOPUS: ar.j, info:eu-repo/semantics/published

In this work we focus on the concept of optimization-by-continuation as a strategy for solving a set of optimization problems in about the time it would take to solve a single instance of them. Each cost function is a different linear combination of two convex terms, one differentiable and the other prox-simple. Such optimization problems occur frequently in the numerical solution of inverse problems (data misfit term plus penalty or constraint term), and the relative weight of both terms is often not known in advance. The algorithm's special feature lies in its ability to approximate, in a single iteration run, the minimizers of the cost function for many different values of the parameters determining the relative weight of the two terms. We also discuss the same problem in the presence of a third term in the cost function which is the combination of a prox-simple function and a linear map. As a special case, one recovers a generalization of the primal-dual algorithm of Chambolle and Pock., info:eu-repo/semantics/nonPublished

info:eu-repo/semantics/inPress

We present a numerical iterative optimization algorithm for the minimization of a cost function consisting of a linear combination of three convex terms, one of which is differentiable, a second one is prox-simple and the third one is the composition of a linear map and a prox-simple function. The algorithm's special feature lies in its ability to approximate, in a single iteration run, the minimizers of the cost function for many different values of the parameters determining the relative weight of the three terms in the cost function. A proof of convergence of the algorithm, based on an inexact variable metric approach, is also provided. As a special case, one recovers a generalization of the primal-dual algorithm of Chambolle and Pock, and also of the proximal-gradient algorithm. Finally, we show how it is related to a primal-dual iterative algorithm based on inexact proximal evaluations of the non-smooth terms of the cost function., Submitted., info:eu-repo/semantics/inPress

info:eu-repo/semantics/published

SCOPUS: no.j, info:eu-repo/semantics/published

info:eu-repo/semantics/published

We discuss several iterative optimization algorithms for the minimization of a cost function consisting of a linear combination of up to three convex terms with at least one differentiable and a second one prox-simple. Such optimization problems frequently occur in the numerical solution of inverse problems (data misfit term plus penalty or constraint term). We present several new results on the convergence of proximal-gradient-like algorithms in the context of a optimization-by-continuation strategy. The algorithms special feature lies in their ability to approximate, in a single iteration run, the minimizers of the cost function for many different values of the parameters determining the relative weight of the three terms in the cost function (penalty parameters). As a special case, one recovers a generalization of the primal-dual algorithm of Chambolle and Pock., info:eu-repo/semantics/nonPublished

Depuis quelques années, plusieurs entreprises ont commencé à exploiter les données qu’ils ont emmagasinées pour pouvoir extraire des connaissances et faire des prévisions. Une bonne utilisation de ces données permet aux entreprises de comprendre leurs clients et pouvoir améliorer leurs services. Les techniques d’intelligence artificielle se présentent comme des moyens pour révolutionner les prises de décisions. Plus d’entreprises embauchent des data scientists pour concevoir des modèles de prédiction. Le but des data scientists est de concevoir des modèles et de les performer. L’un des défis majeurs rencontré par ces data scientists est le prétraitement des données. Le prétraitement des données impact la qualité du modèle mis en place. Ce problème est dû au fait qu’il n’existe pas une seule bonne manière de prétraité les données. Les techniques utilisées dépendent du problème et du type de donnée. Ce mémoire a pour objectif d’évaluer la possibilité de développer une solution qui permet d’automatiser les opérations de prétraitement des données pour les acteurs de données (data scientistes, chercheurs, etc.). Nous utiliserons le terme pipeline afin de nommer la chaîne de pré-traitement et de traitement des données (de la donnée brute jusqu’à la classification de la donnée). En effet, nous proposons un pipeline qui permet de choisir les meilleures techniques de prétraitements en fonction du problème. Plusieurs techniques sont répertoriées et nous utilisons des techniques d’optimisation métaheuristique pour minimiser le temps de recherche du meilleur modèle. Ces techniques sont par la suite comparées avec des techniques d’optimisation standard comme la recherche par grille. Le pipeline est par la suite testé sur des données d’une entreprise d’assurance automobile du Canada. Les résultats nous montrent que les méthodes d’optimisation métaheuristique sont plus efficaces sur des big data. Elles ont permis de diminuer d’environ 30% le temps nécessaire pour retrouver un bon

Feature selection is a fundamental process to avoid overfitting and to reduce the size of databases without significant loss of information that applies to hierarchical clustering. Dendrograms are graphical representations of hierarchical clustering algorithms that for single linkage clustering can be interpreted as minimum spanning trees in the complete network defined by the database. In this work, we introduce the problem that determines jointly a set of features and a dendrogram, according to the single linkage method. We propose different formulations that include the minimum spanning tree problem constraints as well as the feature selection constraints. Different bounds on the objective function are studied. For one of the models, several families of valid inequalities are proposed and the problem of separating them is studied. For another formulation, a decomposition algorithm is designed. In an extensive computational study, the effectiveness of the different models is discussed, the model with valid inequalities is compared with the decomposition algorithm. The computational results also illustrate that the integration of feature selection to the optimization model allows to keep a satisfactory percentage of information., SCOPUS: ar.j, info:eu-repo/semantics/published

L’industrie d’aujourd’hui est constamment en quête de nouvelles méthodes pour améliorer ses processus et ses activités. Elle a recours à la recherche opérationnelle pour répondre à ses besoins. Les problèmes auxquels elle fait face peuvent être définis par l’utilisation de variables de décision entières (problèmes de nature discrète) ou de variables de décision réelles (problèmes de nature continue ou mixte). Les métaheuristiques permettent d’approcher ces problèmes lorsqu’ils sont NP-difficiles. Cette catégorie de méthodes offre un moyen de trouver une solution acceptable dans un délai raisonnable. L’objectif général de cette thèse consiste à améliorer les stratégies métaheuristiques pour la résolution de problèmes de grande taille. Parmi les métaheuristiques bien connues, la famille des algorithmes d’optimisation par essaims particulaires (PSO) offre d’excellentes performances pour la résolution de problèmes de nature continue. Le PSO a beaucoup évolué depuis sa conception. Deux stratégies sont utilisées afin d’améliorer ses performances : l’hybridation et la discrétisation. L’hybridation permet d’améliorer les performances en combinant les forces des méthodes d’optimisation utilisées. La discrétisation permet d’étendre l’applicabilité d’une méthode d’optimisation à une plus grande variété de problèmes. Il est bien connu que plus la dimension d’un problème augmente, plus il s’avère difficile de résoudre ce problème efficacement. Malgré les forces du PSO, cette métaheuristique éprouve de la difficulté à résoudre les problèmes de grande taille. Cette thèse propose tout d’abord la conception de trois algorithmes hybrides construits selon trois variantes de PSO : le Barebones PSO, le Comprehensive Learning PSO et le Cooperative Learning PSO. L’utilisation de fonctions continues bien connues (Rosenbrock, Ackley, etc.) et de fonctions provenant du CEC’15 benchmark set permettent de statuer sur les modèles hybrides les plus prometteurs permettant de pallier les lacunes d

Over the years, operational research (OR) has been used extensively to support the forest products industry and public forestry organizations in their respective planning activities concerning the flow of wood fiber from the forest to the customer. The planning decisions range from long-term strategic planning decisions related to forest management or company development to very short-term operational decisions, such as planning for real-time log/chip transportation or cutting. This chapter presents an overview of the different planning problems and explains how these are solved in the field of forestry using operational research., 0

Collaborative logistics is increasingly emerging as a new opportunity for cost reduction through internal and cross chains coordination. This paper presents different coordination mechanisms to support collaborative logistics. These mechanisms are differentiated by their planning function, their sharing approach and the information, decision and financial flows. Often, the logistics planning is run first, and secondly, the sharing is set on the basis of the plan. However, recently, new approaches have been proposed where both the logistics plan and the sharing are optimized simultaneously. Constraints on the financial flows also introduce specificities to the coordination mechanisms and these are described and discussed. Finally, the proposed coordination mechanisms are used to describe a series of research and applied projects in which collaborative logistics has been implemented., 0

This work describes a framework for the elaboration and evaluation of management policies for production and transportation supply chains in the forest product industry. The approach deals with the issue of coordination between the tactical and operational decision levels. First, we introduce LogiLab, a software system allowing to model the network and to optimize product flows in the supply chain. We than show how one can use this tactical aggregated plan to identify management policies that will guide day to day operations at the operational level. Finally, a discrete event simulation model allows assessing with more details what would be the impact of implementing these policies at the operational/execution level.

The forest-products supply chain gives rise to a variety of interconnected problems. Addressing these problems is challenging, but could be simplified by rigorous data analysis through a machine learning approach. A large amount of data links these problems at various hierarchical levels (e.g., strategic, tactical, operational, online) which complicates the data computation phase required to model and solve industrial problem instances. In this study, we propose to use machine learning to generate models of the sawmills (converting logs into lumber) to simplify the data computation phase for solving optimization problems. Specifically, we show how to use these models to provide a recommendation for the allocation of cutblocks to sawmills for a wood allocation planning problem without needing extensive sawing simulations. Our experimental results on an industrial problem instance demonstrate that the generated models can be used to provide high-quality recommendations (sending the right wood to the right mill). Machine learning models of the sawmill transformation process from logs to lumber allows a better allocation exploiting the strengths of the mills to process the logs in our industrial case.

Over the years, Operational Research (OR) has been used extensively to support the forest products industry and public forestry organizations (e.g., governments, environmental protection groups) in their respective planning activities concerning the flow of wood fiber from the forest to the customer. The applications deal with a wide range of problems, ranging from long-term strategic problems related to forest management or company development to very short-term operational problems, such as planning for real-time log/chip transportation or cutting. This paper presents an overview of the different planning problems and reviews the past contributions in the field of forestry, with a focus on applications and problem descriptions. In the context of the 50th anniversary of the Canadian Operational Research Society, this paper also recognizes the contributions of many Canadian researchers to the field of forestry management.

Forestry has contributed many problems to the Operations Research (OR) community. At the same time, OR has developed many models and solution methods for use in forestry. In this article, we describe the current status of research on the application of OR methods to forestry and a number of research challenges or open questions that we believe will be of interest to both researchers and practitioners. The areas covered include strategic, tactical and operational planning, fire management, conservation and the use of OR to address environmental concerns. The paper also considers more general methodological areas that are important to forestry including uncertainty, multiple objectives and hierarchical planning.

Interest has been raised by the recent identification of potential savings through collaborative planning in logistics operations. Even though substantial savings can be realized, two key questions exist: (i) how should potential savings be divided among a group of collaborating companies and (ii) among potential collaborating companies, how should collaborating group(s) be formed? These two questions are studied in a specific context: among potential collaborating companies; a subset, denoted the leading companies, performs collaborative planning on behalf of the others and together, they initiate formation of a collaborating group. We use the concept of a business model to detail such context. Based on the literature on network formation where potential savings are modelled by a cooperative game, four business models are explored in four different subsets of leading companies. We propose a network model as a method to determine the stable collaborating group in each computation. A case study including eight forest companies is described and analyzed. Results show that very different solution characteristics can be achieved depending on the business model selected.

Multicriteria decision aid consists in helping decision-makers to compare (rank, choose, sort, etc.) different alternatives which are evaluated on conflicting criteria. A well-known family of decision aid methods is the PROMETHEE family. It has been highlighted that these methods may suffer from rank reversal occurrences. However, Mareschal et al. and later Verly and De Smet have pointed out that rank reversal could only occur between alternatives having similar flow scores. In this work, a stricter threshold on the difference of net flow scores is proposed. It is shown using real datasets that the new threshold significantly reduces the pairs of alternatives subject to rank reversal. A comparison of the different thresholds according to the information on which they are based is also given. These new insights suggest carefully reconsidering the definition of the indifference and the incomparability relation in the context of PROMETHEE methods., SCOPUS: ar.j, info:eu-repo/semantics/published

Purpose: This paper aims to explain the impacts of the ongoing digitization reform in Benin. It demonstrates that a well-conducted reform can reduce corruption, improve performance and bring citizens closer to the administration. It also highlights the elements needed to ensure the success of such a reform. Design/methodology/approach: The impacts of the digitization of services and processes on both administrative structures and accountability mechanisms are described and discussed through the analysis of interviews conducted with government officials and key external stakeholders. Findings: Findings indicate that the implementation of new technologies has created difficulties for public servants and that reaching out to the entire population is still proving challenging. However, the reform has helped prevent abuses and corruption in management, and it has raised hopes of improving the state–citizen relationship in the long run. Originality/value: This paper adds to the research on digitization, accountability and state–citizen relationships in developing countries. It fills a gap in the literature by directly analyzing the relationship between digitization and public accountability in Benin., SCOPUS: ar.j, info:eu-repo/semantics/published

Depuis quelques années, le réseau public de la santé du Québec fait face à une pénurie grandissante de main-d’oeuvre. Cette pénurie est reliée à une réforme du système de santé au Québec ayant introduit de nombreux changements administratifs et plusieurs coupes budgétaires. L’analyse des infirmières montre que celles-ci travaillent dans des conditions difficiles, ce qui cause une détérioration de leur santé mentale et physique. Entre autres, le taux d’absentéisme des infirmières a atteint un sommet historique et continue d’augmenter chaque année. De plus, un grand nombre de cas d’épuisements professionnels ont été recensés dans les dernières années, causant des arrêts de travail pour des périodes prolongées. Les conséquences sont ressenties par une augmentation de la charge de travail des infirmières, qui doivent effectuer des quarts de travail en temps supplémentaire afin de compenser le manque de personnel soignant. Pour toutes ces raisons, les infirmières ont besoin d’horaires de travail convenables et adaptés à leur situation. Ce mémoire propose une solution à la problématique de gestion des horaires des infirmières afin de réduire les risques d’absentéisme à l’aide d’une valeur permettant de quantifier le bien-être des infirmières. Un modèle d’optimisation en nombres entiers est utilisé afin de construire des horaires pour les infirmières d’une unité de soins. Un algorithme Branchand-bound est utilisé afin de résoudre le modèle. Ce modèle d’optimisation est supporté par un autre modèle issu de l’apprentissage machine, où l’un des paramètres d’optimisation est calculé par un algorithme Random Forest Regression (RFR). Ce dernier permet de prédire le paramètre de bien-être des infirmières en utilisant l’historique des horaires antérieurs. À partir de ces données, la sommation du nombre de quarts travaillés (ex. à temps régulier, à temps supplémentaire, etc.), des congés et des absences est utilisée pour la construction d’une variable de prédiction de l’état de cha

Since the introduction of Simulated Annealing (SA), researchers have considered variants that keep the same temperature value throughout the whole search and tried to determine whether this strategy can be more effective than the original cooling scheme. Several studied have tried to answer this question without a conclusive answer and without providing indications that could be useful for a practical implementation. In this work, we address this question following an experimental approach, relating the characteristics of the algorithms with the characteristics of the landscapes they encounter. We use problem-independent landscape features to study the algorithmic behaviour across different problems. We consider three different objective functions and various instance classes and determine the conditions under which the fixed-temperature variant of SA can outperform its original counterpart and when SA is instead a better choice., SCOPUS: ar.j, info:eu-repo/semantics/published

Dimensionality reduction and manifold learning techniques are used in numerous disciplines to find low-dimensional manifolds in complex systems with many degrees of freedom. This approach allows for a substantial reduction in the number of parameters needed to visualize, describe and predict complex systems, but some topological properties of low-dimensional manifolds can hinder their practical application. Here, we present a quantitative metric for characterizing the quality of low-dimensional manifolds. The metric collects information about variance in dependent variable values happening across multiple spatial scales on a manifold. It can characterize two topological aspects in particular: non-uniqueness and feature sizes in low-dimensional parameterizations. Our metric is scalable with manifold dimensionality and can work across different linear and nonlinear dimensionality reduction techniques. Moreover, dependent variables that are most relevant in modeling can be selected a priori and the manifold topology can be assessed for those variables specifically. Using the metric as a cost function in optimization algorithms, we show that optimized low-dimensional manifolds can be found. The metric can be also used to tune the hyper-parameters of reduction techniques and to select appropriate data preprocessing strategies to obtain improved manifolds. Our approach provides a way to quantify and automate decisions that need to be made prior to applying a reduction technique., info:eu-repo/semantics/published

info:eu-repo/semantics/published

We study the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints. One class is characterized by having hop-indexed arc variables. Although such models have proved to have a very strong linear programming bound, they are not easy to use because of the huge number of variables. This has motivated some studies with models involving fewer variables that use, instead of the hop-indexed arc variables, hop-indexed node variables. In this article, we contextualize the linear programming relaxation of these node-based models in terms of the linear programming relaxation of known arc-based models. We show that the linear programming relaxation of a general node-based model is implied by the linear programming relaxation of a straightforward arc-based model., SCOPUS: ar.j, info:eu-repo/semantics/published

Grammar-based automatic algorithm design has been shown to generate stochastic local search algorithms that compete with or outperform state-of-the-art methods. In such systems, algorithms are divided in components and a grammar is used to describe how to properly combine the components to create a working algorithm. In our approach, the grammar is converted into parameters and an automatic parameter configuration tool is used to find the best configuration. This approach allows us to consider and hybridize different metaheuristic templates producing combinations never tested before, but this flexibility leads to a very large configuration space to explore. Is such complexity really needed to achieve state-of-the-art performance? In this paper, we investigate this question by creating grammars that allow the hybridization of stochastic local search algorithms at most two, one, or zero times. We use these grammars to generate algorithms for the three most studied objectives of the permutation flowshop problem: makespan, total completion time, and total tardiness. The generated algorithms are compared using benchmark sets from the literature as well as a quantitative measure of algorithm complexity using a metric based on concept directed acyclic graphs. The experiments show that our system tends to generate hybridized algorithms only when they can provide a substantial performance improvement. On the contrary, when such algorithms do not improve performance, the system generates simpler algorithms regardless of the grammar used., SCOPUS: ar.j, info:eu-repo/semantics/published