An iterated sample construction with path relinking method: Application to switch allocation in electrical distribution networks

We present a metaheuristic approach which combines constructive heuristics and local searches based on sampling with path relinking. Its effectiveness is demonstrated by an application to the problem of allocating switches in electrical distribution networks to improve their reliability. Our approach also treats the service restoration problem, which has to be solved as a subproblem, to evaluate the reliability benefit of a given switch allocation proposal. Comparisons with other metaheuristics and with a branch-and-bound procedure evaluate its performance. © 2012 Published by Elsevier Ltd.

Métodos híbridos de pontos interiores e de programação inteira 0-1 para problemas de custo de colheita da cana-de-açúcar e de custo de coleta e geração de energia relacionados à sua biomassa

Pós-graduação em Engenharia Elétrica - FEB

Heurística Surrogate para problema de carregamento de paletes dio produtor

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Análise de novos modelos matemáticos para o problema de planejamento da expansão de sistemas de transmissão

Pós-graduação em Engenharia Elétrica - FEIS

La programmazione lineare intera e i suoi sviluppi

La tesi si occupa della programmazione lineare in particolare nel caso in cui le variabili coinvolte o alcune di esse sono obbligate ad assumere valori interi.

A Column-Generation Approach for a Short-Term Production Planning Problem in Closed-Loop Supply Chains

We present a new model formulation for a multi-product lot-sizing problem with product returns and remanufacturing subject to a capacity constraint. The given external demand of the products has to be satisfied by remanufactured or newly produced goods. The objective is to determine a feasible production plan, which minimizes production, holding, and setup costs. As the LP relaxation of a model formulation based on the well-known CLSP leads to very poor lower bounds, we propose a column-generation approach to determine tighter bounds. The lower bound obtained by column generation can be easily transferred into a feasible solution by a truncated branch-and-bound approach using CPLEX. The results of an extensive numerical study show the high solution quality of the proposed solution approach.

Supporting pruning in tabled LP

This paper analyzes issues which appear when supporting pruning operators in tabled LP. A version of the once/1 control predicate tailored for tabled predicates is presented, and an implementation analyzed and evaluated. Using once/1 with answer-on-demand strategies makes it possible to avoid computing unneeded solutions for problems which can benefit from tabled LP but in which only a single solution is needed, such as model checking and planning. The proposed version of once/1 is also directly applicable to the efficient implementation of other optimizations, such as early completion, cut-fail loops (to, e.g., prune at the top level), if-then-else, and constraint-based branch-and-bound optimization. Although once/1 still presents open issues such as dependencies of tabled solutions on program history, our experimental evaluation confirms that it provides an arbitrarily large efficiency improvement in several application areas.

On the solution of a class of capital investment problems

In this work the solution of a class of capital investment problems is considered within the framework of mathematical programming. Upon the basis of the net present value criterion, the problems in question are mainly characterized by the fact that the cost of capital is defined as a non-decreasing function of the investment requirements. Capital rationing and some cases of technological dependence are also included, this approach leading to zero-one non-linear programming problems, for which specifically designed solution procedures supported by a general branch and bound development are presented. In the context of both this development and the relevant mathematical properties of the previously mentioned zero-one programs, a generalized zero-one model is also discussed. Finally,a variant of the scheme, connected with the search sequencing of optimal solutions, is presented as an alternative in which reduced storage limitations are encountered.

Jeux de policiers et voleurs, Modèles et applications

Les jeux de policiers et voleurs sont étudiés depuis une trentaine d’années en informatique et en mathématiques. Comme dans les jeux de poursuite en général, des poursuivants (les policiers) cherchent à capturer des évadés (les voleurs), cependant ici les joueurs agissent tour à tour et sont contraints de se déplacer sur une structure discrète. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se déroule à information parfaite. La première définition d’un jeu de policiers-voleurs remonte à celle de Nowakowski et Winkler [39] et, indépendamment, Quilliot [46]. Cette première définition présente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de déplacement. Des extensions furent graduellement proposées telles que l’ajout de policiers et l’augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] proposèrent une généralisation des jeux de policiers-voleurs pour permettre l’étude de ceux-ci dans leur globalité. Cependant, leur modèle ne couvre aucunement les jeux possédant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de manière aléatoire. Dans ce mémoire est donc présenté un nouveau modèle incluant des aspects stochastiques. En second lieu, on présente dans ce mémoire une application concrète de l’utilisation de ces jeux sous la forme d’une méthode de résolution d’un problème provenant de la théorie de la recherche. Alors que les jeux de policiers et voleurs utilisent l’hypothèse de l’information parfaite, les problèmes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut être analysé comme une relaxation de contraintes d’un problème de recherche. Ce nouvel angle de vue est exploité pour la conception d’une borne supérieure sur la fonction objectif d’un problème de recherche pouvant être mise à contribution dans une méthode dite de branch and bound.

Interrupted searches in the BBMCSFilter context for MINLP problems

The BBMCSFilter method was developed to solve mixed integer nonlinear programming problems. This kind of problems have integer and continuous variables and they appear very frequently in process engineering problems. The objective of this work is to analyze the performance of the method when the coordinate searches are interrupted in the context of the multistart strategy. From the numerical experiments, we observed a reduction on the number of function evaluations and on the CPU time.

Exact Combinatorial Optimization with Graph Convolutional Neural Networks

Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose to learn a variable selection policy for branch-and-bound in mixed-integer linear programming, by imitation learning on a diversified variant of the strong branching expert rule. We encode states as bipartite graphs and parameterize the policy as a graph convolutional neural network. Experiments on a series of synthetic problems demonstrate that our approach produces policies that can improve upon expert-designed branching rules on large problems, and generalize to instances significantly larger than seen during training.

Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

Scalable and Efficient Configuration of TimeDivision Multiplexed Resources

Consumer-electronics systems are becoming increasingly complex as the number of integrated applications is growing. Some of these applications have real-time requirements, while other non-real-time applications only require good average performance. For cost-efficient design, contemporary platforms feature an increasing number of cores that share resources, such as memories and interconnects. However, resource sharing causes contention that must be resolved by a resource arbiter, such as Time-Division Multiplexing. A key challenge is to configure this arbiter to satisfy the bandwidth and latency requirements of the real-time applications, while maximizing the slack capacity to improve performance of their non-real-time counterparts. As this configuration problem is NP-hard, a sophisticated automated configuration method is required to avoid negatively impacting design time. The main contributions of this article are: 1) An optimal approach that takes an existing integer linear programming (ILP) model addressing the problem and wraps it in a branch-and-price framework to improve scalability. 2) A faster heuristic algorithm that typically provides near-optimal solutions. 3) An experimental evaluation that quantitatively compares the branch-and-price approach to the previously formulated ILP model and the proposed heuristic. 4) A case study of an HD video and graphics processing system that demonstrates the practical applicability of the approach.

Remodeling of DNA replication structures by the branch point translocase FANCM

Fanconi anemia (FA) is a genetically heterogeneous chromosome instability syndrome associated with congenital abnormalities, bone marrow failure, and cancer predisposition. Eight FA proteins form a nuclear core complex, which promotes tolerance of DNA lesions in S phase, but the underlying mechanisms are still elusive. We reported recently that the FA core complex protein FANCM can translocate Holliday junctions. Here we show that FANCM promotes reversal of model replication forks via concerted displacement and annealing of the nascent and parental DNA strands. Fork reversal by FANCM also occurs when the lagging strand template is partially single-stranded and bound by RPA. The combined fork reversal and branch migration activities of FANCM lead to extensive regression of model replication forks. These observations provide evidence that FANCM can remodel replication fork structures and suggest a mechanism by which FANCM could promote DNA damage tolerance in S phase

Shout and Act: an Algorithm for Digital Objects Preservation Inspired from Rescue Robots

We adapt the Shout and Act algorithm to Digital Objects Preservation where agents explore file systems looking for digital objects to be preserved (victims). When they find something they “shout” so that agent mates can hear it. The louder the shout, the urgent or most important the finding is. Louder shouts can also refer to closeness. We perform several experiments to show that this system works very scalably, showing that heterogeneous teams of agents outperform homogeneous ones over a wide range of tasks complexity. The target at-risk documents are MS Office documents (including an RTF file) with Excel content or in Excel format. Thus, an interesting conclusion from the experiments is that fewer heterogeneous (varying skills) agents can equal the performance of many homogeneous (combined super-skilled) agents, implying significant performance increases with lower overall cost growth. Our results impact the design of Digital Objects Preservation teams: a properly designed combination of heterogeneous teams is cheaper and more scalable when confronted with uncertain maps of digital objects that need to be preserved. A cost pyramid is proposed for engineers to use for modeling the most effective agent combinations