Multi-area decentralized optimal VAr planning using the Dantzig-Wolfe decomposition principle

This paper presents a new methodology for solving the optimal VAr planning problem in multi-area electric power systems, using the Dantzig-Wolfe decomposition. The original multi-area problem is decomposed into subproblems (one for each area) and a master problem (coordinator). The solution of the VAr planning problem in each area is based on the application of successive linear programming, and the coordination scheme is based on the reactive power marginal costs in the border bus. The aim of the model is to provide coordinated mechanisms to carry out the VAr planning studies maximizing autonomy and confidentiality for each area, assuring global economy to the whole system. Using the mathematical model and computational implementation of the proposed methodology, numerical results are presented for two interconnected systems, each of them composed of three equal subsystems formed by IEEE30 and IEEE118 test systems. © 2011 IEEE.

Decomposição de Dantzig-Wolfe aplicada ao problema de planejamento de reativos em sistemas de potência multi-áreas

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Hierarchical Demand Response for Peak Minimization Using Dantzig-Wolfe Decomposition

Demand response (DR) algorithms manipulate the energy consumption schedules of controllable loads so as to satisfy grid objectives. Implementation of DR algorithms using a centralized agent can be problematic for scalability reasons, and there are issues related to the privacy of data and robustness to communication failures. Thus, it is desirable to use a scalable decentralized algorithm for the implementation of DR. In this paper, a hierarchical DR scheme is proposed for peak minimization based on Dantzig-Wolfe decomposition (DWD). In addition, a time weighted maximization option is included in the cost function, which improves the quality of service for devices seeking to receive their desired energy sooner rather than later. This paper also demonstrates how the DWD algorithm can be implemented more efficiently through the calculation of the upper and lower cost bounds after each DWD iteration.

Kuljetustensuunnittelu- ja reitinoptimointiohjelmiston kaupallistamiseen vaikuttavat keskeiset ominaisuudet

Ajoneuvojen reititystä on tutkittu 1950-luvulta asti, alunperin etsiessä polttoainekuljetuksille optimaalisinta reittiä varastolta useille palveluasemille. Siitä lähtien ajoneuvon reititystehtäviä on tutkittu akateemisesti ja niistä on muodostettu kymmeniä erilaisia variaatioita. Tehtävien ratkaisumenetelmät jaetaan tyypillisesti tarkkoihin menetelmiin sekä heuristiikkoihin ja metaheuristiikkoihin. Konetehon ja heuristiikoissa käytettävien algoritmien kehittymisen myötä reitinoptimointia on alettu tarjota kaupallisesti. CO-SKY-projektin tavoitteena on kaupallistaa web-pohjainen tai toiminnanohjausjärjestelmään integroitava ajoneuvon reititys. Diplomityössä tutkitaan kuljetustensuunnittelu- ja reitinoptimointiohjelmistojen kaupallistamiseen vaikuttavia keskeisiä ominaisuuksia. Ominaisuuksia on tarkasteltu: 1) erityisesti pk-kuljetusyritysten tarpeiden ja vaatimusten pohjalta, ja 2) markkinoilla olevien ohjelmistojen tarjontaa arvioiden. Näiden pohjalta on myös pyritty arvioimaan kysynnän ja tarjonnan kohtaamista. Pilottiasiakkaita haastattelemalla ohjelmistolle on kyetty asettamaan vaatimuksia, mutta samalla on kuultu käyttäjien mielipiteitä optimoinnista. Lukuisia logistiikkaohjelmistojen tarjoajia on haastateltu logistiikkamessuilla sekä Suomessa että Saksassa. Haastattelujen perusteella on saatu käsitys kyseisistä ohjelmista sekä optimoinnin tarjonnasta että kysynnästä. Akateeminen tutkimus aiheesta on laajaa, koskien niin teknistä toteutusta kuin myös (kysely-)tutkimuksia tarjolla olevien ohjelmistojen ominaisuuksista ja laadusta. Kuljetusyritysten tarpeissa on vaihtelua yritys- ja alakohtaisesti. Perusongelmat ovat samoja, joita reitinoptimoinnin akateemisessa tutkimuksessa käsitellään ja joita kaupalliset ohjelmistot pystyvät ratkaisemaan. Vaikka reitinoptimoinnilla saatavat hyödyt ovat mitattavissa, suunnittelu etenkin pk-yrityksissä tehdään pääosin yhä käsin. Messuhaastattelujen ja loppukäyttäjien mielipiteiden perusteella voidaan todeta kaupallisten ratkaisujen olevan suunniteltu isommille kuljetusyrityksille: tyypillisen it-projektin hinta, käyttöönottoaika ja asennus sekä ratkaisun takaisinmaksuaika vaikuttavat pk-yritysten hankintapäätökseen. Kaupallistamiseen liittyen haasteet liittyvät erityisesti segmentointiin ja markkinointiin asiakasarvon todentamisen ja sen välittämisen kautta.

Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

Le problème de tournées de véhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problèmes les plus étudiés en recherche opérationnelle, et ce, en raison de son intérêt méthodologique et de ses retombées pratiques dans de nombreux domaines tels que le transport, la logistique, les télécommunications et la production. L'objectif général du VRP est d'optimiser l'utilisation des ressources de transport afin de répondre aux besoins des clients tout en respectant les contraintes découlant des exigences du contexte d’application. Les applications réelles du VRP doivent tenir compte d’une grande variété de contraintes et plus ces contraintes sont nombreuse, plus le problème est difficile à résoudre. Les VRPs qui tiennent compte de l’ensemble de ces contraintes rencontrées en pratique et qui se rapprochent des applications réelles forment la classe des problèmes ‘riches’ de tournées de véhicules. Résoudre ces problèmes de manière efficiente pose des défis considérables pour la communauté de chercheurs qui se penchent sur les VRPs. Cette thèse, composée de deux parties, explore certaines extensions du VRP vers ces problèmes. La première partie de cette thèse porte sur le VRP périodique avec des contraintes de fenêtres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fenêtres de temps (VRPTW) puisqu’il considère un horizon de planification de plusieurs jours pendant lesquels les clients n'ont généralement pas besoin d’être desservi à tous les jours, mais plutôt peuvent être visités selon un certain nombre de combinaisons possibles de jours de livraison. Cette généralisation étend l'éventail d'applications de ce problème à diverses activités de distributions commerciales, telle la collecte des déchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la première partie de cette thèse est le développement d'une méta-heuristique hybride dans la quelle un ensemble de procédures de recherche locales et de méta-heuristiques basées sur les principes de voisinages coopèrent avec un algorithme génétique afin d’améliorer la qualité des solutions et de promouvoir la diversité de la population. Les résultats obtenus montrent que la méthode proposée est très performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problème. La deuxième partie de cette étude a pour but de présenter, modéliser et résoudre deux problèmes riches de tournées de véhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dépendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problèmes sont connus respectivement sous le nom de Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW) et de Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS). Ces deux problèmes proviennent de la planification des opérations de systèmes logistiques urbains à deux niveaux. La difficulté de ces problèmes réside dans la manipulation de deux ensembles entrelacés de décisions: la composante des tournées de véhicules qui vise à déterminer les séquences de clients visités par chaque véhicule, et la composante de planification qui vise à faciliter l'arrivée des véhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont été abordées séparément. La combinaison de ces types de décisions dans une seule formulation mathématique et dans une même méthode de résolution devrait donc donner de meilleurs résultats que de considérer ces décisions séparément. Dans cette étude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de décisions simultanément, et ce, d'une manière complète et efficace. Les résultats de tests expérimentaux confirment la performance de la méthode proposée lorsqu’on la compare aux autres méthodes présentées dans la littérature. En effet, la méthode développée propose des solutions nécessitant moins de véhicules et engendrant de moindres frais de déplacement pour effectuer efficacement la même quantité de travail. Dans le contexte des systèmes logistiques urbains, nos résultats impliquent une réduction de la présence de véhicules dans les rues de la ville et, par conséquent, de leur impact négatif sur la congestion et sur l’environnement.

Administración estratégica de la producción: Modelo con base en la matriz de tecnología Una herramienta de planeación y control de la productividad.

El desarrollo de modelos económicos lineales fue uno de los logros más signifi cativos en teoría económica en la Norteamérica de la posguerra. La programación lineal, desarrollada por George B. Dantzig (1947), los modelos de insumo producto de Wassily Leontief (1946) y la teoría de juegos de John. Von Neumann (1944) se constituyeron en tres ramas diferentes de la teoría económica lineal. Sus aplicaciones en variados campos del conocimiento, como la Economía y la Ciencia Política, y en actividades de gestión en la industria y en el gobierno son cada vez más signifi cativas. El objetivo principal de este trabajo es el de presentar un modelo práctico de los procesos de producción típicos de una fábrica o empresa que transforma insumos en productos. El modelo se desarrolla en el contexto y con los conceptos propios de la teoría de modelos económicos lineales, y el enfoque de la investigación de operaciones, también conocido como el de las ciencias de la administración.

Perspectivas históricas da pesquisa operacional

Pós-graduação em Educação Matemática - IGCE

Modelos Matemáticos e Métodos de Solução para Problemas de Dimensionamento de Lotes

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

Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Metodi euristici per il problema dei trasporti con costi fissi

In questa tesi viene considerato il problema dei trasporti con costi fissi (FCTP) che, assieme al Traveling Salesman Problem (TSP), è uno dei problemi nobili dell’ottimizzazione combinatoria. Esso generalizza il ben noto problema dei trasporti (TP) imponendo che il costo per spedire prodotti da un’origine ad una destinazione sia composto da un costo fisso ed un costo proporzionale alla quantità spedita. Il FCTP è stato formulato per la prima volta in un articolo di Hirsch e Dantzig (1968) ed è stato da allora oggetto di studio per la ricerca di nuovi e sempre migliori algoritmi di risoluzione. Nessuno dei metodi esatti fin ora pubblicati è in grado di risolvere istanze con più di 15 origini e 15 destinazioni. Solo recentemente, Roberti et al. (2013), in un paper in corso di pubblicazione, hanno presentato un metodo esatto basato su una nuova formulazione matematica del problema, il quale è in grado di risolvere istanze di FCTP con 70 origini e 70 destinazioni. La crescita esponenziale dello sforzo computazionale richiesto dai metodi esatti ne ha confinato l’applicazione a problemi di dimensioni ridotte. Tali limitazioni hanno portato allo studio e alla ricerca di approcci approssimativi, euristici e metaeuristici i quali sfruttano varie strategie di local search. Fra i molteplici metodi euristici presentati in letteratura, meritano particolare attenzione quelli di Sun et al. (1998) e Glover et al. (2005). Recentemente, Buson et al. (2013) hanno presentato un nuovo euristico che domina tutti i precedenti sui problemi test proposti in letteratura. In questa tesi viene presentato un approccio Tabu Search che migliora il metodo originalmente proposto da Sun et al. (1998). I risultati computazionali ottenuti con un codice prototipale indicano che l’algoritmo sviluppato è migliore del metodo originario di Sun et al. (1998) e competitivo con il più recente metodo proposto da Buson et al. (2013).

Cut-first branch-and-price-second for the capacitated arc-routing problem

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model.rnSuch a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.