102 research outputs found
Stronger path‐based extended formulation for the Steiner tree problem
No full textThe Steiner tree problem (STP) is a classical NP-hard combinatorial optimization problem with applications in computational biology and network wiring. The objective of this problem is to find a minimum cost subgraph of a given undirected graph G with edge costs, that spans a subset of vertices called terminals. We present currently used linear programming formulations of the problem based on two different approaches—the bidirected cut relaxation (BCR) and the hypergraphic formulations (HYP), the former offering better computational performance, and the latter better bounds on the integrality gap. As our contribution, we propose a new hierarchy of path-based extended formulations for STP.We show that this hierarchy provides better integrality gaps on graph instances used to define the worst-case lower bounds on the integrality gap for both BCR and HYP. We prove that each consecutive level of our hierarchy is at least as strong as the previous one. Additionally, we also present numerical results showing that several difficult STP instances can be solved to integer optimality by using this hierarchy. Our approach can be adapted to variants of STP or applied to hypergraphic formulations for further potential improvement on the integrality gap bounds, in exchange for additional computational effort
Analysis of the European electricity grid scenarios : application to the Belgian renewable energies
No full textlia analysed the renewable energy (RE) capacity required in each scenario (and for other variables such as other countries’ production, etc) and then agreed on a transmission capacity for each border and each scenario. Based on these forecasts, I examined the influence of this new REs capacity (based on new transmission line capacity) on exports and on the price. The literature review highlighted the congestion problem due to the intermittent nature of REs. Therefore, in the Belgian case I focused on the situation where RE production was elevated.
After conducting the necessary transformations to ensure relevant results and analysing the relations between these variables when REs production was high, I forecasted the following:
• Exports based on a change in REs capacity installed
• Prices based on a change in REs capacity installed
Finally, I ran an autoregressive integrated moving average (ARIMA) model with the forecasted prices as the dependent variable and exports as the independent variable. The purpose was both to determine how the price is influenced by an augmentation of exports due to an increase in REs capacity installed and to identify the differences among scenarios.
The results revealed that in 2040, exports will influence prices negatively three times more than at present. Quantitatively, this development will result in the current decrease in price of 0.0039 €/MWh for each additional MWh of electricity exported becoming a decrease of 0.012 €/MWh by 2040.
Considering the best scenario for Belgium and knowing that its CO2 emission targets are the same as the EU’s, the global climate action (GCA) scenario outcome appears better than the two others. This projection allows for a substantial part of Belgium’s electricity to be produced by renewable energies and limits the seasonality in the production presented in the distributed generation (DG) scenario. This result is due to a better mix in REs installed.nhhma
Auktionen in Börsenhandelssystemen: Modellierungstechniken und Algorithmen
No full textModern exchange trading systems facilitate the market participants to electronically submit detailed information about their buy and sell preferences. With the help of so-called combinatorial orders, they can buy or sell several different items at once.
Tradable items are, for instance, company shares, futures contracts, electricity, or natural gas. The most basic combinatorial order is the fill-or-kill order in stock exchanges. This order is either executed entirely or not executed at all. That is, the participant either buys or sells all requested or offered items at once or none of them. Combinatorial orders are also available in electricity exchanges (e.g., block orders) and in futures exchanges (e.g., futures combination order).
An exchange usually determines a single price for each class of tradable items. For example, one price is determined for futures contracts of type A and a further price is determined for futures contracts of type B. In the absence of combinatorial orders, these prices can be determined separately. However, if participants submit combinatorial orders that comprise futures contracts of type A and B, then the prices must be determined simultaneously. This is necessary in order to make the prices for combinatorial orders consistent with the ones of the underlying futures contracts.
The first part of this work presents general modeling techniques and algorithms. For instance, we present a framework model for auctions in which the prices for several classes of items are determined simultaneously. Roughly speaking, we perform several auctions in parallel and integrate the combinatorial orders in such a way that they couple the parallel auctions among each other. For a certain class of combinatorial auctions this work provides model formulations that are solvable in polynomial time (e.g., the futures opening auction). For the general case, where the problem is NP-hard, we provide model formulations and algorithms which are fast enough such that they can be used in practice (e.g., in the European day-ahead electricity auction).
In the second part of this work, we present specific auction models for futures opening auctions, European day-ahead electricity auctions, and European natural gas auctions. Thereby we apply our general models and algorithms, go into problem specific details, and perform numerical tests on real-world instances.Moderne Börsenhandelssysteme ermöglichen es den Marktteilnehmern, ihre Kauf- und Verkaufspräferenzen in detaillierter Form elektronisch zu übermitteln. Mit Hilfe von sogenannten kombinatorischen Geboten können beispielsweise mehrere verschiedene Güter simultan gekauft oder verkauft werden.
Handelbare Güter sind zum Beispiel Aktien, Futures-Kontrakte, Strom oder Erdgas. Das einfachste kombinatorische Gebot ist die sogenannte Fill-or-kill-Order an der Wertpapierbörse. Dieses Gebot wird entweder vollständig oder gar nicht ausgeführt. Das bedeutet, dass ein Teilnehmer entweder alle nachgefragten oder angebotenen Wertpapiere am Stück kauft oder verkauft, oder kein einziges. Kombinatorische Gebote werden auch an Strombörsen (z.B. das Blockgebot) und Terminbörsen (z.B. die Futures-Kombinationsorder) angeboten.
Normalerweise bestimmt eine Börse einen Preis für jede Klasse von handelbaren Gütern. Zum Beispiel wird ein Preis für Futures-Kontrakte vom Typ A und ein Preis für Futures-Kontrakte vom Typ B ermittelt. Falls keine kombinatorischen Gebote abgegeben wurden, dann sind die Preise voneinander unabhängig und können separat bestimmt werden. Falls jedoch kombinatorische Gebote abgegeben wurden, die sowohl Futures-Kontrakte vom Typ A als auch vom Typ B beinhalten, dann müssen die Preise simultan berechnet werden. Dies ist notwendig, damit die Preise für die kombinatorischen Gebote konsistent zu den Preisen der zugrundeliegenden Futures-Kontrakte sind.
Im ersten Teil dieser Arbeit stellen wir allgemeine Modellierungstechniken und Algorithmen vor. Unter anderem präsentieren wir allgemeine Rahmenmodelle für Auktionen, bei denen die Preise für mehrere Klassen von handelbaren Gütern simultan berechnet werden. Grob gesagt werden mehrere Auktionen parallel durchgeführt und dabei die kombinatorischen Gebote so eingebunden, so dass die Auktionen untereinander gekoppelt werden. Für bestimmte Klassen von kombinatorischen Auktionen präsentieren wir Modellformulierungen, die in polynomieller Zeit gelöst werden können (z.B. die Futures-Eröffnungsauktionen). Für den allgemeinen Fall, in dem das Auktionsproblem NP-schwer ist, stellen wir Modellformulierungen und Algorithmen vor, die schnell genug sind, um in der Praxis verwendet werden zu können (z.B. in europäischen day-ahead Strommarktauktionen).
Im zweiten Teil dieser Arbeit werden spezielle Auktionsmodelle für Futures-Eröffnungsauktionen, europäische day-ahead Stromauktionen und europäische Erdgasauktionen vorgestellt. Dabei wenden wir unsere allgemeinen Modelle und Algorithmen an, gehen auf problemspezifische Details ein und führen numerische Tests mit Probleminstanzen aus der Praxis durch
What drives the Rebound Effect in transportation? An evaluation based on a Traveling Purchaser Problem
No full textLimiting climate change is one of the most important challenges of the 21st century.
Focusing on the transport sector, encouraging the use of more energy-efficient transport
modes, and improving the performance of vehicles are the main targets in the fight for
GHG reductions. However, due to Rebound Effect (RE), it is proven that improvements
in engine fuel efficiency result in lower cost per kilometer driven and can induce individuals
to use vehicles more often or to drive longer distances. As a result, the potential energy
savings from improved energy efficiency could be partially or totally offset. Therefore, we
decided to examine "What drives the Rebound Effect in transportation".
To answer this research question, a Traveling Purchaser Problem was evaluated. This
simple real-life business application models a situation in which a company owns one or
several vehicles and has to buy specific products. The goal is to select and visit a subset
of suppliers to satisfy a given demand for each product while minimizing both purchasing
and travel costs. In total, 510 instances of this problem with various characteristics
and parameters were generated and solved using the optimization software AIMMS. The
impact of five main experimentations was deeply investigated. In addition, the trends
obtained from these experiments were confirmed by fitting a logistic regression and a
decision tree.
The results of the various experiments showed that four variables can influence the occurrence
of RE in a transportation network. On the one hand, RE tended to increase
with the number of potential suppliers from which the firm can choose and the number
of vehicles that the company owns to procure the products. On the other hand, the exclusivity
of the products to source, as well as the introduction of a distance-traveled tax,
reduced the occurrence of RE. To sum up, significant conclusions could be drawn from
the experiments and the results can be easily transferred to real-life business applications.
Recommendations for possible future studies were also discussed.nhhma
A solution approach of production planning problems based on compact formulations for single-item lot-sizing models
No full textWe survey the main results presented in the author’s PhD Thesis presented in June 2003 at the Université catholique de Louvain and supervised by Y. Pochet and L.A. Wolsey. The dissertation is written in English and is available from
the author. In the first part of the thesis, we investigate the complexity and the polyhedral structure of various extensions of the uncapacitated single-item lot-sizing problem (Barany et al. 1984). In particular, we study models involving fixed charges on stocks, constant capacity and backlogging, and lower bounds on production. We describe algorithms, extended formulations, (facet-defining) valid inequalities and separation algorithms. Emphasis is placed on compact (i.e. of polynomial size) exact extended formulations. In a second part, we show how such extended reformulations for single-item problems can help to improve the solution of much more general production planning problems
Linear prices for non-convex electricity markets: models and algorithms
No full textStrict Linear Pricing in non-convex markets is a mathematical impossibility. In the context of electricity markets, two different classes of solutions have been proposed to this conundrum on both sides of the Atlantic. We formally describe these two approaches in a common framework, review and analyze their main properties, and discuss their shortcomings.
In US, some orders are not settled at the market price, but at their bidding price, deviating from uniform pricing (all orders are financially settled at the same prices). This creates a disincentive to bid one’s own true cost, and creates a missing money problem for the clearing house of the market. In Europe, all accepted orders are in-the-money are settled at the uniform market price. This implies that the welfare-maximizing solution is considered infeasible and also that the optimization problem is much less convex and more difficult to solve. This also creates fairness issues for orders of small volume, and the solution obtained does not implement a Walrasian equilibrium.
Based on this analysis we propose a new model that draws on both approaches and retains their best theoretical properties. We also show how the different approaches compare on classical toy problem
Algorithms for single item constant capacity lotsizing problems
No full textThe main result of this paper is to provide an O(n3) algorithm for the single item constant capacity lotsizing problem with backlogging and a general number of installable batches, i.e in each time period t we may install up to mt multiples of the batch capacity, where the mt are given and are time-dependent. This generalizes earlier results [12, 16] as we consider backlogging and a general number of installable batches. We also give faster algorithms for three special cases of this general problem. When backlogging is not allowed and the costs satisfy the Wagner-Whitin property the problem is solvable in O(n2logn) time. In the discrete case it is possible to solve the problem with and without backlogging in O(n2) and O(n2logn) time respectively
Is it possible to be successful in mass customization in imperfect conditions ? If yes : how do companies manage these ? A case study of Bivolino and my M&M’S
No full textThis thesis aimed at finding out whether it is possible to be successful in mass customization when not all success factors are met, and, if so, how to manage this lack. In order to do so, extensive literature review - to have a thorough understanding of the concept of mass customization and to find out the list of all success factors - and case study research - to uncover which factors are not necessary and how this lack was managed - has been done. The case study research revealed to be the best method for this thesis according to Yin (2014), which was about two successful mass customizers, namely Bivolino who produces shirts, and My M&M's who produces chocolate candies. There are three key takeaways of this study. First of all, it can be concluded that it is indeed possible to be successful in imperfect conditions. Secondly, solutions to tackle the absence of seven success factors were revealed. But most surprising was the absence of a need for the product, which can be created by the company, and the high prices compared to similar standard goods, two factors that seemed indispensable for successful mass customization. Time will tell if these findings will lead to an increased number of mass customizers, who previously were deterred of adopting such a strategy, and to new types of mass customization.Master [120] en Ingénieur de gestion, Université catholique de Louvain, 201
L'utilisation des outils électroniques traditionnels au sein du parcours décisionnel du consommateur
No full textDans la première partie de ce mémoire, j’ai rappelé la définition des outils électroniques traditionnels utilisés par les consommateurs dans le paysage digital belge en l'occurrence, de l’ordinateur, de la tablette et du smartphone. C’est dans l’environnement digital que j’ai développé le parcours décisionnel du consommateur. Celui-ci est composé de quatre étapes à savoir : la considération initiale, l’évaluation active, l’achat et l’expérience après achat. Lors de la première étape du parcours décisionnel du consommateur, celui-ci a un nombre restreint de marques à l’esprit pouvant répondre à son besoin d’achat. L’évaluation active correspond à l’étape de recherche, c’est la seconde étape du parcours décisionnel du consommateur. Celui-ci recherche les biens correspondants à ses besoins. La troisième étape est celle de l’achat. Dans ce mémoire, je me suis concentré sur l’achat en ligne. Celui-ci prend un peu plus d’importance chaque année en Belgique. Enfin, la dernière étape est celle de l’expérience après achat. Cette étape englobe la loyauté envers la marque et la défense de celle-ci par le consommateur. Ensuite, j’ai exposé les résultats obtenus grâce à la distribution de mon questionnaire. Ces résultats ont été recueillis en utilisant le logiciel SPSS et m’ont permis de répondre à la question de recherche. Celle-ci est la suivante : « Quel est l’utilisation des différents outils électroniques traditionnels au sein du parcours décisionnel du consommateur ? ». L’ordinateur est l’outil électronique incontournable. En effet, celui-ci est l’outil préféré des consommateurs, quel que soit l’étape du parcours décisionnel dans laquelle ils se trouvent. Cependant, les consommateurs effectuant des recherches en magasin utilisent leur smartphone. Cette recherche en magasin est l’unique instant où le consommateur utilise un autre outil que son ordinateur. Il s’agit là d’une opportunité pour les entreprises car les consommateurs n’ont pas de bloqueur de publicité sur leur smartphone, contrairement à leur ordinateur.Master [120] en sciences de gestion, Université catholique de Louvain, 201
Flight efficiency : relaxed profiles generation performance and “Traffic Draggers” RAD in Switzerland
No full textThis thesis contains the resolution of two different projects accomplished at Eurocontrol, the European agency for Air Traffic Flow Capacity Management. -Project 1: enhancement of relaxed trajectories generation -Project 2: identification of RAD Traffic draggers methodology This thesis is confidentialMaster [120] en Ingénieur de gestion, Université catholique de Louvain, 201
- …
