Die Erreichung der ehrgeizigen Dekarbonisierungsziele Deutschlands erfordert eine massive Ausweitung der Onshore-Windenergie. In den letzten Jahren sahen sich Onshore-Wind Projektentwickler zunehmend mit sozialen und Umweltbedenken aufgrund von Landnutzungskonflikten konfrontiert. Aus regulatorischer Sicht stellen die weitere Integration von Onshore-Windkapazitäten in das deutsche Energiesystem besondere Herausforderungen in Bezug auf geografische und zeitliche Aspekte der Stromerzeugung dar. Die hohen Windgeschwindigkeiten und die vergleichsweise geringe Bevölkerungsdichte haben dazu geführt, dass Investoren in der Vergangenheit überproportional in den nördlichen Bundesländern Windparks entwickelten. Eine starke gleichzeitige Einspeisung von Strom an nahegelegenen Windstandorten führt jedoch zu einem Druck auf die Großhandelsstrompreise, was die Markterträge der Entwickler reduziert. Diese Arbeit zielt daher darauf ab, einen Beitrag zum zukünftigen Design des deutschen Energiesystems zu leisten und insbesondere den weiteren Ausbau der Onshore-Windenergie in Deutschland unter Berücksichtigung sozialer, Umwelt- und wirtschaftlicher Einschränkungen zu untersuchen. Dabei werden GIS-Software und ein neues inverses Zeitreihenmodellierungsverfahren genutzt, um das Windpotenzial und Landnutzungskonflikte zu analysieren. Zukünftige Marktszenarien werden mit Hilfe eines dekomposierten Kraftwerkseinsatz und -investitionsmodells hinsichtlich ihrer Wirkungen auf die ökonomische Effizienz der Marktintegration von Onshore-Windenergie bewertet, wobei Preisentwicklungen für CO2-Emissionszertifikate eine entscheidende Rolle spielen. Die Ergebnisse deuten auf eine abnehmende Rentabilität der Onshore-Windenergie in Deutschland hin, während der Süden Deutschlands aus ganzheitlicher Perspektive einen größeren Beitrag zur Windenergie leisten könnte.:I Analysis framework 1 1 Introduction 3 1.1 Research motivation . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Research objective, aims and questions . . . . . . . . . . . . . 5 1.3 Scientific contribution . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 Research focus specification . . . . . . . . . . . . . . . 7 1.3.2 Contribution regarding renewable energy potentials and levelised generation cost . . . . . . . . . . . . . . . 10 1.3.3 Contribution regarding generic wind time series modelling 12 1.3.4 Contribution regarding electricity market modelling and model decomposition . . . . . . . . . . . . . . . . . 14 1.3.5 Contribution regarding evaluating the market integration of wind energy . . . . . . . . . . . . . . . . . . 17 1.4 Organisation of thesis and software tools applied . . . . . . . 20 2 Basics of electricity economics 23 2.1 Pricing and investments in electricity markets . . . . . . . . . 23 2.1.1 Long-term market equilibrium . . . . . . . . . . . . . . 23 2.1.2 Short-term market equilibrium . . . . . . . . . . . . . . 25 2.2 Interplay of price formation and renewable support . . . . . . 27 2.2.1 Definitions and concepts . . . . . . . . . . . . . . . . . 27 2.2.2 Quantity and price effect of environmental policies and implications for geographic deployment pathways 29 II Regionalisation of data inputs 33 3 GIS-based windenergy potential analysis 35 3.1 Framing the approach . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.1 Taxonomy of renewable potentials . . . . . . . . . . . 35 3.1.2 GIS-based analysis procedure . . . . . . . . . . . . . . 36 3.1.3 Three-stage sensitivity analysis . . . . . . . . . . . . . 37 3.2 Land assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Land characteristics . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Results on the land availability . . . . . . . . . . . . . . 41 3.3 Technical potential . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3.1 Technical wind turbine configuration . . . . . . . . . . 44 3.3.2 Electrical energy conversion . . . . . . . . . . . . . . . 45 3.3.3 Wind-farm design . . . . . . . . . . . . . . . . . . . . . 46 3.3.4 Results on the technical potential . . . . . . . . . . . . 47 3.4 Economic potential . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.1 Cost-potential curves at a country level . . . . . . . . 49 3.4.2 Cost-potential curves at a regional level . . . . . . . . 52 4 Generic wind energy feed-in time series 55 4.1 Generic wind speed data in energy systems analysis . . . . . . 55 4.1.1 Motivation of generic time series . . . . . . . . . . . . 55 4.1.2 Incorporation of time series generation into modelling setup . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 Dynamic adjustment of model size via clustering . . . . . . . 56 4.2.1 Introduction to hierarchical and partitional cluster methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2.2 Euclidean distance as proximity measure . . . . . . . . 57 4.2.3 Linkage of observations and cluster verification . . . 58 4.2.4 Specification of input data and data organisation . . . 59 4.2.5 Results on cluster algorithm selection and representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Vector autoregressive stochastic process with Normal-to- Weibull transformation . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.1 Wind characteristics . . . . . . . . . . . . . . . . . . . . 61 4.3.2 Data description and handling . . . . . . . . . . . . . . 62 4.3.3 Additive modelling procedure . . . . . . . . . . . . . . 63 4.3.4 Standard Normal-to-Weibull transformation . . . . . . 64 4.3.5 Time series decomposition . . . . . . . . . . . . . . . . 67 4.3.6 (V)AR-Parameter estimation . . . . . . . . . . . . . . . 70 4.3.7 Statistical dependence between different locations . . 73 4.3.8 Time series simulation . . . . . . . . . . . . . . . . . . . 75 4.3.9 Results on time series simulation . . . . . . . . . . . . 77 III Market model-based investigation 81 5 Modelling investment decisions in power markets 83 5.1 Motivation for illustration of model decomposition . . . . . . 83 5.2 Simplified market model formulation . . . . . . . . . . . . . . . 83 5.2.1 Power plant dispatch problem . . . . . . . . . . . . . . 83 5.2.2 Capacity expansion extension . . . . . . . . . . . . . . 84 5.2.3 Constraint matrix structure . . . . . . . . . . . . . . . . 85 5.3 Complexity reduction via Benders decomposition . . . . . . . 87 5.3.1 Benders strategies . . . . . . . . . . . . . . . . . . . . . 87 5.3.2 Single-cut procedure . . . . . . . . . . . . . . . . . . . . 88 5.3.3 Multi-cut procedure . . . . . . . . . . . . . . . . . . . . 93 5.4 Acceleration strategies for decomposed market models . . . . 98 5.4.1 Scenario solver . . . . . . . . . . . . . . . . . . . . . . . 98 5.4.2 Distributed computing . . . . . . . . . . . . . . . . . . . 98 5.4.3 Regularisation . . . . . . . . . . . . . . . . . . . . . . . 98 5.5 Numerical testing of model formulation and solving strategy 99 5.5.1 Preliminary remarks . . . . . . . . . . . . . . . . . . . . 99 5.5.2 Effects of multiple cuts . . . . . . . . . . . . . . . . . . 100 5.5.3 Effects of scenario solver and parallelisation . . . . . . 101 5.5.4 Effects of regularisation . . . . . . . . . . . . . . . . . . 103 5.6 Implications for a large-scale application . . . . . . . . . . . . 105 6 ELTRAMOD-dec: A market model tailored for investigating the European electricity markets 107 6.1 Understanding the model design . . . . . . . . . . . . . . . . . 107 6.1.1 Market modelling fundamentals . . . . . . . . . . . . . 107 6.1.2 ELTRAMOD-dec’s model structure and solving conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.1.3 Central capacity planning assumptions . . . . . . . . . 109 6.1.4 Central market clearing assumptions . . . . . . . . . . 110 6.2 Mathematical formulation of ELTRAMOD-dec . . . . . . . . . 111 6.2.1 Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2.2 Master problem equations . . . . . . . . . . . . . . . . 114 6.2.3 Subproblem equations . . . . . . . . . . . . . . . . . . . 117 6.2.4 Program termination . . . . . . . . . . . . . . . . . . . 123 6.2.5 Research-specific extensions . . . . . . . . . . . . . . . 124 6.3 Data description and model calibration . . . . . . . . . . . . . 126 6.3.1 Base year modelling data . . . . . . . . . . . . . . . . . 126 6.3.2 Model performance validation . . . . . . . . . . . . . . 131 6.3.3 Target year modelling data . . . . . . . . . . . . . . . . 133 6.4 Determination of ELTRAMOD-dec’s solving conventions and tuning parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.4.1 Framing some modelling experiments . . . . . . . . . 137 6.4.2 Effects of regularisation on convergence behaviour . 138 6.4.3 Effects of time slicing on solution accuracy . . . . . . 142 6.4.4 Effects of decomposition on solving speed . . . . . . . 145 7 Model-based investigation of onshore wind deployment pathways in Germany 149 7.1 Scenario framework and key assumptions . . . . . . . . . . . . 149 7.1.1 Scenario creation . . . . . . . . . . . . . . . . . . . . . . 149 7.1.2 Definition of market configuration . . . . . . . . . . . 152 7.1.3 Summary on scenario key assumptions . . . . . . . . . 154 7.2 Results on market integration at a market zone level . . . . . 155 7.2.1 Introducing market integration indicators . . . . . . . 155 7.2.2 Market integration indicators for baseline calculation 156 7.2.3 Market integration indicators for increased renewable uptake calculation . . . . . . . . . . . . . . . . . . 157 7.2.4 Market integration indicators for ultimate renewable uptake calculation . . . . . . . . . . . . . . . . . . . . . 159 7.3 Results on market integration at a detailed regional level . . . 160 7.3.1 Introducing regional market integration indicators . . 160 7.3.2 Regional market integration indicators for baseline calculation . . . . . . . . . . . . . . . . . . . . . . . . . . 161 7.3.3 Regional market integration indicators for increased renewable uptake calculation . . . . . . . . . . . . . . . 163 7.3.4 Regional market integration indicators for ultimate renewable uptake calculation . . . . . . . . . . . . . . . 164 8 Summary and conclusions 169 8.1 Findings regarding the market integration . . . . . . . . . . . . 169 8.1.1 Onshore wind resources constitute a limiting factor for achieving Germany’s energy transition . . . . . . 169 8.1.2 Distribution of wind farm fleet has a strong impact on market premia in the centre and south of Germany 170 8.2 Findings regarding the technical underpinning . . . . . . . . . 173 8.2.1 Generic wind speed velocities can be a powerful tool for power system modellers . . . . . . . . . . . . . . . 173 8.2.2 Decomposition enables efficient solving of large-scale power system investment and dispatch models . . . . 174 8.3 Implications for policymakers . . . . . . . . . . . . . . . . . . . 176 IV Appendix 179 A Additional tables and figures 181 B Code listings 187 Bibliography 199 / Achieving Germany's ambitious decarbonisation goals requires a massive expansion of onshore wind energy. In recent years, onshore wind project developers have increasingly faced social and environmental concerns due to land use conflicts. From a regulatory perspective, further integrating onshore wind capacity into the German energy system poses particular challenges regarding geographical and temporal aspects of electricity generation. High wind speeds and comparatively low population density have led investors to disproportionately develop wind farms in the northern states in the past. However, a strong simultaneous electricity feed-in at nearby wind sites suppresses wholesale electricity prices, reducing developers' market returns. This study aims to contribute to the future design of the German energy system and, in particular, to examine the further expansion of onshore wind energy in Germany, considering social, environmental, and economic constraints. GIS software and a new inverse time series modelling approach are utilised to investigate wind potential and land use conflicts. Future market scenarios are evaluated using a decomposed power plant dispatch and investment model regarding their effects on the economic efficiency of onshore wind energy market integration, with price developments for carbon emission certificates playing a crucial role. The results indicate a decreasing profitability of onshore wind energy in Germany, while from a holistic perspective, southern Germany could make a more significant contribution to wind energy at reasonable increases in support requirements.:I Analysis framework 1 1 Introduction 3 1.1 Research motivation . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Research objective, aims and questions . . . . . . . . . . . . . 5 1.3 Scientific contribution . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 Research focus specification . . . . . . . . . . . . . . . 7 1.3.2 Contribution regarding renewable energy potentials and levelised generation cost . . . . . . . . . . . . . . . 10 1.3.3 Contribution regarding generic wind time series modelling 12 1.3.4 Contribution regarding electricity market modelling and model decomposition . . . . . . . . . . . . . . . . . 14 1.3.5 Contribution regarding evaluating the market integration of wind energy . . . . . . . . . . . . . . . . . . 17 1.4 Organisation of thesis and software tools applied . . . . . . . 20 2 Basics of electricity economics 23 2.1 Pricing and investments in electricity markets . . . . . . . . . 23 2.1.1 Long-term market equilibrium . . . . . . . . . . . . . . 23 2.1.2 Short-term market equilibrium . . . . . . . . . . . . . . 25 2.2 Interplay of price formation and renewable support . . . . . . 27 2.2.1 Definitions and concepts . . . . . . . . . . . . . . . . . 27 2.2.2 Quantity and price effect of environmental policies and implications for geographic deployment pathways 29 II Regionalisation of data inputs 33 3 GIS-based windenergy potential analysis 35 3.1 Framing the approach . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.1 Taxonomy of renewable potentials . . . . . . . . . . . 35 3.1.2 GIS-based analysis procedure . . . . . . . . . . . . . . 36 3.1.3 Three-stage sensitivity analysis . . . . . . . . . . . . . 37 3.2 Land assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.1 Land characteristics . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Results on the land availability . . . . . . . . . . . . . . 41 3.3 Technical potential . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3.1 Technical wind turbine configuration . . . . . . . . . . 44 3.3.2 Electrical energy conversion . . . . . . . . . . . . . . . 45 3.3.3 Wind-farm design . . . . . . . . . . . . . . . . . . . . . 46 3.3.4 Results on the technical potential . . . . . . . . . . . . 47 3.4 Economic potential . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.1 Cost-potential curves at a country level . . . . . . . . 49 3.4.2 Cost-potential curves at a regional level . . . . . . . . 52 4 Generic wind energy feed-in time series 55 4.1 Generic wind speed data in energy systems analysis . . . . . . 55 4.1.1 Motivation of generic time series . . . . . . . . . . . . 55 4.1.2 Incorporation of time series generation into modelling setup . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 Dynamic adjustment of model size via clustering . . . . . . . 56 4.2.1 Introduction to hierarchical and partitional cluster methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2.2 Euclidean distance as proximity measure . . . . . . . . 57 4.2.3 Linkage of observations and cluster verification . . . 58 4.2.4 Specification of input data and data organisation . . . 59 4.2.5 Results on cluster algorithm selection and representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Vector autoregressive stochastic process with Normal-to- Weibull transformation . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.1 Wind characteristics . . . . . . . . . . . . . . . . . . . . 61 4.3.2 Data description and handling . . . . . . . . . . . . . . 62 4.3.3 Additive modelling procedure . . . . . . . . . . . . . . 63 4.3.4 Standard Normal-to-Weibull transformation . . . . . . 64 4.3.5 Time series decomposition . . . . . . . . . . . . . . . . 67 4.3.6 (V)AR-Parameter estimation . . . . . . . . . . . . . . . 70 4.3.7 Statistical dependence between different locations . . 73 4.3.8 Time series simulation . . . . . . . . . . . . . . . . . . . 75 4.3.9 Results on time series simulation . . . . . . . . . . . . 77 III Market model-based investigation 81 5 Modelling investment decisions in power markets 83 5.1 Motivation for illustration of model decomposition . . . . . . 83 5.2 Simplified market model formulation . . . . . . . . . . . . . . . 83 5.2.1 Power plant dispatch problem . . . . . . . . . . . . . . 83 5.2.2 Capacity expansion extension . . . . . . . . . . . . . . 84 5.2.3 Constraint matrix structure . . . . . . . . . . . . . . . . 85 5.3 Complexity reduction via Benders decomposition . . . . . . . 87 5.3.1 Benders strategies . . . . . . . . . . . . . . . . . . . . . 87 5.3.2 Single-cut procedure . . . . . . . . . . . . . . . . . . . . 88 5.3.3 Multi-cut procedure . . . . . . . . . . . . . . . . . . . . 93 5.4 Acceleration strategies for decomposed market models . . . . 98 5.4.1 Scenario solver . . . . . . . . . . . . . . . . . . . . . . . 98 5.4.2 Distributed computing . . . . . . . . . . . . . . . . . . . 98 5.4.3 Regularisation . . . . . . . . . . . . . . . . . . . . . . . 98 5.5 Numerical testing of model formulation and solving strategy 99 5.5.1 Preliminary remarks . . . . . . . . . . . . . . . . . . . . 99 5.5.2 Effects of multiple cuts . . . . . . . . . . . . . . . . . . 100 5.5.3 Effects of scenario solver and parallelisation . . . . . . 101 5.5.4 Effects of regularisation . . . . . . . . . . . . . . . . . . 103 5.6 Implications for a large-scale application . . . . . . . . . . . . 105 6 ELTRAMOD-dec: A market model tailored for investigating the European electricity markets 107 6.1 Understanding the model design . . . . . . . . . . . . . . . . . 107 6.1.1 Market modelling fundamentals . . . . . . . . . . . . . 107 6.1.2 ELTRAMOD-dec’s model structure and solving conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.1.3 Central capacity planning assumptions . . . . . . . . . 109 6.1.4 Central market clearing assumptions . . . . . . . . . . 110 6.2 Mathematical formulation of ELTRAMOD-dec . . . . . . . . . 111 6.2.1 Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2.2 Master problem equations . . . . . . . . . . . . . . . . 114 6.2.3 Subproblem equations . . . . . . . . . . . . . . . . . . . 117 6.2.4 Program termination . . . . . . . . . . . . . . . . . . . 123 6.2.5 Research-specific extensions . . . . . . . . . . . . . . . 124 6.3 Data description and model calibration . . . . . . . . . . . . . 126 6.3.1 Base year modelling data . . . . . . . . . . . . . . . . . 126 6.3.2 Model performance validation . . . . . . . . . . . . . . 131 6.3.3 Target year modelling data . . . . . . . . . . . . . . . . 133 6.4 Determination of ELTRAMOD-dec’s solving conventions and tuning parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.4.1 Framing some modelling experiments . . . . . . . . . 137 6.4.2 Effects of regularisation on convergence behaviour . 138 6.4.3 Effects of time slicing on solution accuracy . . . . . . 142 6.4.4 Effects of decomposition on solving speed . . . . . . . 145 7 Model-based investigation of onshore wind deployment pathways in Germany 149 7.1 Scenario framework and key assumptions . . . . . . . . . . . . 149 7.1.1 Scenario creation . . . . . . . . . . . . . . . . . . . . . . 149 7.1.2 Definition of market configuration . . . . . . . . . . . 152 7.1.3 Summary on scenario key assumptions . . . . . . . . . 154 7.2 Results on market integration at a market zone level . . . . . 155 7.2.1 Introducing market integration indicators . . . . . . . 155 7.2.2 Market integration indicators for baseline calculation 156 7.2.3 Market integration indicators for increased renewable uptake calculation . . . . . . . . . . . . . . . . . . 157 7.2.4 Market integration indicators for ultimate renewable uptake calculation . . . . . . . . . . . . . . . . . . . . . 159 7.3 Results on market integration at a detailed regional level . . . 160 7.3.1 Introducing regional market integration indicators . . 160 7.3.2 Regional market integration indicators for baseline calculation . . . . . . . . . . . . . . . . . . . . . . . . . . 161 7.3.3 Regional market integration indicators for increased renewable uptake calculation . . . . . . . . . . . . . . . 163 7.3.4 Regional market integration indicators for ultimate renewable uptake calculation . . . . . . . . . . . . . . . 164 8 Summary and conclusions 169 8.1 Findings regarding the market integration . . . . . . . . . . . . 169 8.1.1 Onshore wind resources constitute a limiting factor for achieving Germany’s energy transition . . . . . . 169 8.1.2 Distribution of wind farm fleet has a strong impact on market premia in the centre and south of Germany 170 8.2 Findings regarding the technical underpinning . . . . . . . . . 173 8.2.1 Generic wind speed velocities can be a powerful tool for power system modellers . . . . . . . . . . . . . . . 173 8.2.2 Decomposition enables efficient solving of large-scale power system investment and dispatch models . . . . 174 8.3 Implications for policymakers . . . . . . . . . . . . . . . . . . . 176 IV Appendix 179 A Additional tables and figures 181 B Code listings 187 Bibliography 199

This dissertation focuses on selected issues in regard to the mathematical modeling of electricity markets. In a first step the interrelations of electric power market modeling are highlighted a crossroad between operations research, applied economics, and engineering. In a second step the development of a large-scale continental European economic engineering model named ELMOD is described and the model is applied to the issue of wind integration. It is concluded that enabling the integration of low-carbon technologies appears feasible for wind energy. In a third step algorithmic work is carried out regarding a game theoretic model. Two approaches in order to solve a discretely-constrained mathematical program with equilibrium constraints using disjunctive constraints are presented. The first one reformulates the problem as a mixed-integer linear program and the second one applies the Benders decomposition technique. Selected numerical results are reported.

[pt] Portfólios de fontes renováveis de energia elétrica são mecanismos de gerenciamento de risco interessantes para comercialização de energia em mercados de negociação bilateral. Quando formados por agentes que pertencem a diferentes companhias sua estabilidade depende da maneira com que os benefícios de mitigação de risco gerados pelo portfólio são alocados individualmente entre os participantes. O problema de se encontrar uma solução estável pode ser matematicamente formulado através da busca de um vetor de alocação de quotas que pertença ao núcleo do jogo cooperativo, que por sua vez pode ser formulado como um conjunto de restrições lineares que aumenta exponencialmente com o número de participantes. Adicionalmente, o lado direito de cada restrição que define o núcleo do jogo cooperativo define o valor de uma determinada coalisão que, no presente trabalho, é obtido através de um modelo de otimização estocástica de dois estágios. Este trabalho compara diferentes metodologias computacionalmente eficientes baseadas em programação linear inteira mista e na técnica de decomposição de Benders para encontrar vetores de alocação de quotas que pertençam ao núcleo de portfólios de larga escala de geradores de energia renovável. São apresentados estudos de casos que utilizam dados reais do sistema elétrico brasileiro. / [en] Portfolios of renewable electricity sources are interesting risk-management mechanisms for trading in electricity contract markets. When they are formed by players belonging to different companies, their stability relies on the way the riskmitigation benefit generated by the optimal portfolio is allocated through individual participants. The problem of reaching a stable allocation can be mathematically formulated in terms of finding a quota-sharing vector belonging to the Core of a cooperative game, which can be formulated as a set of linear constraints that exponentially grows with the number of participants. Moreover, the right-hand-side of each constraint defining the Core relies on a given coalition value which, in the present work, is obtained by a two-stage stochastic optimization model. This work presents and compares efficient methodologies mainly based on mixed integer linear programming and Benders decomposition to find quota allocation vectors that belongs to the Core of large-scale renewable energy portfolios. Case studies are presented with realistic data from the Brazilian power system.

[pt] Recentes apagões em todo o mundo fazem da confiabilidade de sistemas de potência, no tocante a contingências múltiplas, um tema de pesquisa mundial. Dentro desse contexo, se faz importante investigar métodos eficientes de proteger o sistema contra falhas de alguns de seus componentes, sejam elas dependentes e/ou independentes de outras falhas. Nesse sentido, se tornou crucial a incorporação de critérios de segurança mais rigorosos na operação e planejamento de sistemas de potência. Contingências múltiplas são mais comuns e desastrosas do que falhas naturais e independentes. A principal razão para isso reside na complexidade da estabilidade dinâmica de sistemas de potência. Além disso, o sistema de proteção que opera em paralelo ao sistema de distribuição não é livre de falhas. Portanto, interrupções naturais podem causar contingências em cascata em decorrência do mau funcionamento de mecanismos de proteção ou da instabilidade do sistema elétrico como um todo. Nesse contexto, se dá a motivação pela busca de critérios de segurança mais severos como, por exemplo, o n - K, onde K pode ser maior do que 2. Nesse trabalho, o principal objetivo é incorporar o crtitério de segurança geral n-K para geração e transmissão em modelos de operação e planejamento de sistemas de potência. Além de interrupções em geradores, restrições de rede, bem como falhas em linhas de transmiss˜ao também são modeladas. Esse avanço leva a novos desafios computacionais, para os quais formulamos metodologias de solução eficientes baseadas em decomposição de Benders. Considerando operação, duas abordagens são apresentadas. A primeira propõe um modelo de otimização trinível para decidir o despacho ótimo de energia e reservas sob um critério de segurançaa n - K. Nessa abordagem, a alta dimensionalidade do problema, por contemplar restrições de rede, bem como falhas de geradores e de linhas de transmissão, é contornada por meio da implícita consideração do conjunto de possíveis contingências. No mesmo contexto, a segunda abordagem leva em conta a incerteza da carga a ser suprida e a correlação entre demandas de diferentes barras. Considerando planejamento de expansão da transmissão, outro modelo de otimização trinível é apresentado no intuito de decidir quais linhas de transmissão, dentro de um conjunto de candidatas, devem ser construídas para atender a um critério de segurança n - K e, consequentemente, aumentar a confiabilidade do sistema como um todo. Portanto, as principais contribuições do presente trabalho são as seguintes: 1) modelos de otimização trinível para considerar o critério de segurança n - K em operação e planejamento de sistemas de potência, 2) consideração implícita de todo o conjunto de contingências por meio de uma abordagem de otimização robusta ajustável, 3) otimização conjunta de energia e reserva para operação de sistemas de potência, considerando restrições de rede e garantindo a entregabilidade das reservas em todos os estados pós-contingência considerados, 4) metodologias de solução eficientes baseadas em decomposição de Benders que convergem em passos finitos para o ótimo global e 5) desenvolvimento de restrições válidas que alavancam a eficiência computacional. Estudos de caso ressaltam a eficácia das metodologias propostas em capturar os efeitos econômicos de demanda nodal correlacionada sob um critério de segurançaa n - 1, em reduzir o esfor¸co computacional para considerar os critérios de seguran¸ca convencionais n-1 e n-2 e em considerar critérios de segurança mais rigorosos do que o n - 2, um problema intratável até então. / [en] Recent major blackouts all over the world have been a driving force to make power system reliability, regarding multiple contingencies, a subject of worldwide research. Within this context, it is important to investigate efficient methods of protecting the system against dependent and/or independent failures. In this sense, the incorporation of tighter security criteria in power systems operation and planning became crucial. Multiple contingencies are more common and dangerous than natural independent faults. The main reason for this lies in the complexity of the dynamic stability of power systems. In addition, the protection system, that operates in parallel to the supply system, is not free of failures. Thus, natural faults can cause subsequent contingencies (dependent on earlier contingencies) due to the malfunction of the protection mechanisms or the instability of the overall system. These facts drive the search for more stringent safety criteria, for example, n - K, where K can be greater than 2. In the present work, the main objective is to incorporate the joint generation and transmission general security criteria in power systems operation and planning models. Here, in addition to generators outages, network constraints and transmission lines failures are also accounted for. Such improvement leads to new computational challenges, for which we design efficient solution methodologies based on Benders decomposition. Regarding operation, two approaches are presented. The first one proposes a trilevel optimization model to decide the optimal scheduling of energy and reserve under an n - K security criterion. In such approach, the high dimensionality curse of considering network constraints as well as outages of generators and transmission assets is withstood by implicitly taking into account the set of possible contingencies. The second approach includes correlated nodal demand uncertainty in the same framework. Regarding transmission expansion planning, another trilevel optimization model is proposed to decide which transmission assets should be built within a set of candidates in order to meet an n - K security criterion, and, consequently, boost the power system reliability. Therefore, the main contributions of this work are the following: 1) trilevel models to consider general n - K security criteria in power systems operation and planning, 2) implicit consideration of the whole contingency set by means of an adjustable robust optimization approach, 3) co-optimization of energy and reserves for power systems operation, regarding network constraints and ensuring the deliverability of reserves in all considered post-contingency states, 4) efficient solution methodologies based on Benders decomposition that finitely converges to the global optimal solution, and 5) development of valid constraints to boost computational efficiency. Case studies highlight the effectiveness of the proposed methodologies in capturing the economic effect of nodal demand correlation on power system operation under an n - 1 security criterion, in reducing the computational effort to consider conventional n-1 and n-2 security criteria, and in considering security criteria tighter than n - 2, an intractable problem heretofore.

Dans cette thèse, nous étudions le problème d’optimisation des effectifs dans les centres d’appels, dans lequel nous visons à minimiser les coûts d’exploitation tout en offrant aux clients une qualité de service (QoS) élevée. Nous introduisons également l'utilisation de contraintes probabilistes qui exigent que la qualité de service soit satisfaite avec une probabilité donnée. Ces contraintes sont adéquates dans le cas où la performance est mesurée sur un court intervalle de temps, car les mesures de QoS sont des variables aléatoires sur une période donnée. Les problèmes de personnel proposés sont difficiles en raison de l'absence de forme analytique pour les contraintes probabilistes et doivent être approximées par simulation. En outre, les fonctions QoS sont généralement non linéaires et non convexes. Nous considérons les problèmes d’affectation personnel dans différents contextes et étudions les modèles proposés tant du point de vue théorique que pratique. Les méthodologies développées sont générales, en ce sens qu'elles peuvent être adaptées et appliquées à d'autres problèmes de décision dans les systèmes de files d'attente. La thèse comprend trois articles traitant de différents défis en matière de modélisation et de résolution de problèmes d'optimisation d’affectation personnel dans les centres d'appels à compétences multiples. Les premier et deuxième article concernent un problème d'optimisation d'affectation de personnel en deux étapes sous l'incertitude. Alors que dans le second, nous étudions un modèle général de programmation stochastique discrète en deux étapes pour fournir une garantie théorique de la consistance de l'approximation par moyenne échantillonnale (SAA) lorsque la taille des échantillons tend vers l'infini, le troisième applique l'approche du SAA pour résoudre le problème d’optimisation d'affectation de personnel en deux étapes avec les taux d’arrivée incertain. Les deux articles indiquent la viabilité de l'approche SAA dans notre contexte, tant du point de vue théorique que pratique. Pour être plus précis, dans le premier article, nous considérons un problème stochastique discret général en deux étapes avec des contraintes en espérance. Nous formulons un problème SAA avec échantillonnage imbriqué et nous montrons que, sous certaines hypothèses satisfaites dans les exemples de centres d'appels, il est possible d'obtenir les solutions optimales du problème initial en résolvant son SAA avec des échantillons suffisamment grands. De plus, nous montrons que la probabilité que la solution optimale du problème de l’échantillon soit une solution optimale du problème initial tend vers un de manière exponentielle au fur et à mesure que nous augmentons la taille des échantillons. Ces résultats théoriques sont importants, non seulement pour les applications de centre d'appels, mais également pour d'autres problèmes de prise de décision avec des variables de décision discrètes. Le deuxième article concerne les méthodes de résolution d'un problème d'affectation en personnel en deux étapes sous incertitude du taux d'arrivée. Le problème SAA étant coûteux à résoudre lorsque le nombre de scénarios est important. En effet, pour chaque scénario, il est nécessaire d'effectuer une simulation pour estimer les contraintes de QoS. Nous développons un algorithme combinant simulation, génération de coupes, renforcement de coupes et décomposition de Benders pour résoudre le problème SAA. Nous montrons l'efficacité de l'approche, en particulier lorsque le nombre de scénarios est grand. Dans le dernier article, nous examinons les problèmes de contraintes en probabilité sur les mesures de niveau de service. Notre méthodologie proposée dans cet article est motivée par le fait que les fonctions de QoS affichent généralement des courbes en S et peuvent être bien approximées par des fonctions sigmoïdes appropriées. Sur la base de cette idée, nous avons développé une nouvelle approche combinant la régression non linéaire, la simulation et la recherche locale par région de confiance pour résoudre efficacement les problèmes de personnel à grande échelle de manière viable. L’avantage principal de cette approche est que la procédure d’optimisation peut être formulée comme une séquence de simulations et de résolutions de problèmes de programmation linéaire. Les résultats numériques basés sur des exemples réels de centres d'appels montrent l'efficacité pratique de notre approche. Les méthodologies développées dans cette thèse peuvent être appliquées dans de nombreux autres contextes, par exemple les problèmes de personnel et de planification dans d'autres systèmes basés sur des files d'attente avec d'autres types de contraintes de QoS. Celles-ci soulèvent également plusieurs axes de recherche qu'il pourrait être intéressant d'étudier. Par exemple, une approche de regroupement de scénarios pour atténuer le coût des modèles d'affectation en deux étapes, ou une version d'optimisation robuste en distribution pour mieux gérer l'incertitude des données. / In this thesis, we study the staffing optimization problem in multiskill call centers, in which we aim at minimizing the operating cost while delivering a high quality of service (QoS) to customers. We also introduce the use of chance constraints which require that the QoSs are met with a given probability. These constraints are adequate in the case when the performance is measured over a short time interval as QoS measures are random variables in a given time period. The proposed staffing problems are challenging in the sense that the stochastic constraints have no-closed forms and need to be approximated by simulation. In addition, the QoS functions are typically non-linear and non-convex. We consider staffing optimization problems in different settings and study the proposed models in both theoretical and practical aspects. The methodologies developed are general, in the sense that they can be adapted and applied to other staffing/scheduling problems in queuing-based systems. The thesis consists of three articles dealing with different challenges in modeling and solving staffing optimization problems in multiskill call centers. The first and second articles concern a two-stage staffing optimization problem under uncertainty. While in the first one, we study a general two-stage discrete stochastic programming model to provide a theoretical guarantee for the consistency of the sample average approximation (SAA) when the sample sizes go to infinity, the second one applies the SAA approach to solve the two-stage staffing optimization problem under arrival rate uncertainty. Both papers indicate the viability of the SAA approach in our context, in both theoretical and practical aspects. To be more precise, in the first article, we consider a general two-stage discrete stochastic problem with expected value constraints. We formulate its SAA with nested sampling. We show that under some assumptions that hold in call center examples, one can obtain the optimal solutions of the original problem by solving its SAA with large enough sample sizes. Moreover, we show that the probability that the optimal solution of the sample problem is an optimal solution of the original problem, approaches one exponentially fast as we increase the sample sizes. These theoretical findings are important, not only for call center applications, but also for other decision-making problems with discrete decision variables. The second article concerns solution methods to solve a two-stage staffing problem under arrival rate uncertainty. It is motivated by the fact that the SAA version of the two-stage staffing problem becomes expensive to solve with a large number of scenarios, as for each scenario, one needs to use simulation to approximate the QoS constraints. We develop an algorithm that combines simulation, cut generation, cut strengthening and Benders decomposition to solve the SAA problem. We show the efficiency of the approach, especially when the number of scenarios is large. In the last article, we consider problems with chance constraints on the service level measures. Our methodology proposed in this article is motivated by the fact that the QoS functions generally display ``S-shape'' curves and might be well approximated by appropriate sigmoid functions. Based on this idea, we develop a novel approach that combines non-linear regression, simulation and trust region local search to efficiently solve large-scale staffing problems in a viable way. The main advantage of the approach is that the optimization procedure can be formulated as a sequence of steps of performing simulation and solving linear programming models. Numerical results based on real-life call center examples show the practical viability of our approach. The methodologies developed in this thesis can be applied in many other settings, e.g., staffing and scheduling problems in other queuing-based systems with other types of QoS constraints. These also raise several research directions that might be interesting to investigate. For examples, a clustering approach to mitigate the expensiveness of the two-stage staffing models, or a distributionally robust optimization version to better deal with data uncertainty.

Cette thèse porte sur la modélisation du trafic dans les réseaux routiers et comment celle-ci est intégrée dans des modèles d'optimisation. Ces deux sujets ont évolué de manière plutôt disjointe: le trafic est prédit par des modèles mathématiques de plus en plus complexes, mais ce progrès n'a pas été incorporé dans les modèles de design de réseau dans lesquels les usagers de la route jouent un rôle crucial. Le but de cet ouvrage est d'intégrer des modèles d'utilités aléatoires calibrés avec de vraies données dans certains modèles biniveaux d'optimisation et ce, par une décomposition de Benders efficace. Cette décomposition particulière s'avère être généralisable par rapport à une grande classe de problèmes communs dans la litérature et permet d'en résoudre des exemples de grande taille. Le premier article présente une méthodologie générale pour utiliser des données GPS d'une flotte de véhicules afin d'estimer les paramètres d'un modèle de demande dit recursive logit. Les traces GPS sont d'abord associées aux liens d'un réseau à l'aide d'un algorithme tenant compte de plusieurs facteurs. Les chemins formés par ces suites de liens et leurs caractéristiques sont utilisés afin d'estimer les paramètres d'un modèle de choix. Ces paramètres représentent la perception qu'ont les usagers de chacune de ces caractéristiques par rapport au choix de leur chemin. Les données utilisées dans cet article proviennent des véhicules appartenant à plusieurs compagnies de transport opérant principalement dans la région de Montréal. Le deuxième article aborde l'intégration d'un modèle de choix de chemin avec utilités aléatoires dans une nouvelle formulation biniveau pour le problème de capture de flot de trafic. Le modèle proposé permet de représenter différents comportements des usagers par rapport à leur choix de chemin en définissant les utilités d'arcs appropriées. Ces utilités sont stochastiques ce qui contribue d'autant plus à capturer un comportement réaliste des usagers. Le modèle biniveau est rendu linéaire à travers l'ajout d'un terme lagrangien basé sur la dualité forte et ceci mène à une décomposition de Benders particulièrement efficace. Les expériences numériques sont principalement menés sur un réseau représentant la ville de Winnipeg ce qui démontre la possibilité de résoudre des problèmes de taille relativement grande. Le troisième article démontre que l'approche du second article peut s'appliquer à une forme particulière de modèles biniveaux qui comprennent plusieurs problèmes différents. La décomposition est d'abord présentée dans un cadre général, puis dans un contexte où le second niveau du modèle biniveau est un problème de plus courts chemins. Afin d'établir que ce contexte inclut plusieurs applications, deux applications distinctes sont adaptées à la forme requise: le transport de matières dangeureuses et la capture de flot de trafic déterministe. Une troisième application, la conception et l'établissement de prix de réseau simultanés, est aussi présentée de manière similaire à l'Annexe B de cette thèse. / The subject of this thesis is the modeling of traffic in road networks and its integration in optimization models. In the literature, these two topics have to a large extent evolved independently: traffic is predicted more accurately by increasingly complex mathematical models, but this progress has not been incorporated in network design models where road users play a crucial role. The goal of this work is to integrate random utility models calibrated with real data into bilevel optimization models through an efficient Benders decomposition. This particular decomposition generalizes to a wide class of problems commonly found in the literature and can be used to solved large-scale instances. The first article presents a general methodology to use GPS data gathered from a fleet of vehicles to estimate the parameters of a recursive logit demand model. The GPS traces are first matched to the arcs of a network through an algorithm taking into account various factors. The paths resulting from these sequences of arcs, along with their characteristics, are used to estimate parameters of a choice model. The parameters represent users' perception of each of these characteristics in regards to their path choice behaviour. The data used in this article comes from trucks used by a number of transportation companies operating mainly in the Montreal region. The second article addresses the integration of a random utility maximization model in a new bilevel formulation for the general flow capture problem. The proposed model allows for a representation of different user behaviors in regards to their path choice by defining appropriate arc utilities. These arc utilities are stochastic which further contributes in capturing real user behavior. This bilevel model is linearized through the inclusion of a Lagrangian term based on strong duality which paves the way for a particularly efficient Benders decomposition. The numerical experiments are mostly conducted on a network representing the city of Winnipeg which demonstrates the ability to solve problems of a relatively large size. The third article illustrates how the approach used in the second article can be generalized to a particular form of bilevel models which encompasses many different problems. The decomposition is first presented in a general setting and subsequently in a context where the lower level of the bilevel model is a shortest path problem. In order to demonstrate that this form is general, two distinct applications are adapted to fit the required form: hazmat transportation network design and general flow capture. A third application, joint network design and pricing, is also similarly explored in Appendix B of this thesis.

This dissertation focuses on selected issues in regard to the mathematical modeling of electricity markets. In a first step the interrelations of electric power market modeling are highlighted a crossroad between operations research, applied economics, and engineering. In a second step the development of a large-scale continental European economic engineering model named ELMOD is described and the model is applied to the issue of wind integration. It is concluded that enabling the integration of low-carbon technologies appears feasible for wind energy. In a third step algorithmic work is carried out regarding a game theoretic model. Two approaches in order to solve a discretely-constrained mathematical program with equilibrium constraints using disjunctive constraints are presented. The first one reformulates the problem as a mixed-integer linear program and the second one applies the Benders decomposition technique. Selected numerical results are reported.

In today's competitive environment, the importance of continuous production, quality improvement, and fast delivery has forced production and delivery processes to become highly reliable. Keeping equipment in good condition through maintenance activities can ensure a more reliable system. However, maintenance leads to temporary reduction in capacity that could otherwise be utilized for production. Therefore, the coordination of maintenance and production is important to guarantee good system performance. The central thesis of this dissertation is that integrating maintenance and production decisions increases efficiency by ensuring high quality production, effective resource utilization, and on-time deliveries. Firstly, we study the problem of integrated maintenance and production planning where machines are preventively maintained in the context of a periodic review production system with uncertain yield. Our goal is to provide insight into the optimal maintenance policy, increasing the number of finished products. Specifically, we prove the conditions that guarantee the optimal maintenance policy has a threshold type. Secondly, we address the problem of integrated maintenance planning and production scheduling where machines are correctively maintained in the context of a dynamic aircraft repair shop. To solve the problem, we view the dynamic repair shop as successive static repair scheduling sub-problems over shorter periods. Our results show that the approach that uses logic-based Benders decomposition to solve the static sub-problems, schedules over longer horizon, and quickly adjusts the schedule increases the utilization of aircraft in the long term. Finally, we tackle the problem of integrated maintenance planning and production scheduling where machines are preventively maintained in the context of a multi-machine production system. Depending on the deterioration process of machines, we design decomposed techniques that deal with the stochastic and combinatorial challenges in different, coupled stages. Our results demonstrate that the integrated approaches decrease the total maintenance and lost production cost, maximizing the on-time deliveries. We also prove sufficient conditions that guarantee the monotonicity of the optimal maintenance policy in both machine state and the number of customer orders. Within these three contexts, this dissertation demonstrates that the integrated maintenance and production decision-making increases the process efficiency to produce high quality products in a timely manner.

Le problème d’ordre linéaire (LOP) a reçu beaucoup d’attention dans différents domaines d’application, allant de l’archéologie à l’ordonnancement en passant par l’économie et même de la psychologie mathématique. Ce problème est aussi connu pour être parmi les problèmes NP-difficiles. Nous considérons dans cette thèse une variante de (LOP) sous contrainte de cardinalité. Nous cherchons donc un ordre linéaire d’un sous-ensemble de sommets du graphe de préférences de cardinalité fixée et de poids maximum. Ce problème, appelé (FCLOP) pour ’fixed-cardinality linear ordering problem’, n’a pas été étudié en tant que tel dans la littérature scientifique même si plusieurs applications dans les domaines de macro-économie, de classification dominante ou de transport maritime existent concrètement. On retrouve en fait ses caractéristiques dans les modèles étendus de sous-graphes acycliques. Le problème d’ordre linéaire est déjà connu comme un problème NP-difficile et il a donné lieu à de nombreuses études, tant théoriques sur la structure polyédrale de l’ensemble des solutions réalisables en variables 0-1 que numériques grâce à des techniques de relaxation et de séparation progressive. Cependant on voit qu’il existe de nombreux cas dans la littérature, dans lesquelles des solveurs de Programmation Linéaire en nombres entiers comme CPLEX peuvent en résoudre certaines instances en moins de 10 secondes, mais une fois que la cardinalité est limitée, ces mêmes instances deviennent très difficiles à résoudre. Sur les aspects polyédraux, nous avons étudié le polytope de FCLOP, défini plusieurs classes d’inégalités valides et identifié la dimension ainsi que certaines inégalités qui définissent des facettes pour le polytope de FCLOP. Nous avons introduit un algorithme Relax-and-Cut basé sur ces résultats pour résoudre les instances du problème. Dans cette étude, nous nous sommes également concentrés sur la relaxation Lagrangienne pour résoudre ces cas difficiles. Nous avons étudié différentes stratégies de relaxation et nous avons comparé les bornes duales par rapport à la consolidation obtenue à partir de chaque stratégie de relâcher les contraintes afin de détecter le sous-ensemble des contraintes le plus approprié. Les résultats numériques montrent que nous pouvons trouver des bornes duales de très haute qualité. Nous avons également mis en place une méthode de décomposition Lagrangienne. Dans ce but, nous avons décomposé le modèle de FCLOP en trois sous-problèmes (au lieu de seulement deux) associés aux contraintes de ’tournoi’, de ’graphes sans circuits’ et de ’cardinalité’. Les résultats numériques montrent une amélioration significative de la qualité des bornes duales pour plusieurs cas. Nous avons aussi mis en oeuvre une méthode de plans sécants (cutting plane algorithm) basée sur la relaxation pure des contraintes de circuits. Dans cette méthode, on a relâché une partie des contraintes et on les a ajoutées au modèle au cas où il y a des de/des violations. Les résultats numériques montrent des performances prometteuses quant à la réduction du temps de calcul et à la résolution d’instances difficiles hors d’atteinte des solveurs classiques en PLNE. / Linear Ordering Problem (LOP) has receive significant attention in different areas of application, ranging from transportation and scheduling to economics and even archeology and mathematical psychology. It is classified as a NP-hard problem. Assume a complete weighted directed graph on V n , |V n |= n. A permutation of the elements of this finite set of vertices is a linear order. Now let p be a given fixed integer number, 0 ≤ p ≤ n. The p-Fixed Cardinality Linear Ordering Problem (FCLOP) is looking for a subset of vertices containing p nodes and a linear order on the nodes in S. Graphically, there exists exactly one directed arc between every pair of vertices in an LOP feasible solution, which is also a complete cycle-free digraph and the objective is to maximize the sum of the weights of all the arcs in a feasible solution. In the FCLOP, we are looking for a subset S ⊆ V n such that |S|= p and an LOP on these S nodes. Hence the objective is to find the best subset of the nodes and an LOP over these p nodes that maximize the sum of the weights of all the arcs in the solution. Graphically, a feasible solution of the FCLOP is a complete cycle-free digraph on S plus a set of n − p vertices that are not connected to any of the other vertices. There are several studies available in the literature focused on polyhedral aspects of the linear ordering problem as well as various exact and heuristic solution methods. The fixed cardinality linear ordering problem is presented for the first time in this PhD study, so as far as we know, there is no other study in the literature that has studied this problem. The linear ordering problem is already known as a NP-hard problem. However one sees that there exist many instances in the literature that can be solved by CPLEX in less than 10 seconds (when p = n), but once the cardinality number is limited to p (p < n), the instance is not anymore solvable due to the memory issue. We have studied the polytope corresponding to the FCLOP for different cardinality values. We have identified dimension of the polytope, proposed several classes of valid inequalities and showed that among these sets of valid inequalities, some of them are defining facets for the FCLOP polytope for different cardinality values. We have then introduced a Relax-and-Cut algorithm based on these results to solve instances of the FCLOP. To solve the instances of the problem, in the beginning, we have applied the Lagrangian relaxation algorithm. We have studied different relaxation strategies and compared the dual bound obtained from each case to detect the most suitable subproblem. Numerical results show that some of the relaxation strategies result better dual bound and some other contribute more in reducing the computational time and provide a relatively good dual bound in a shorter time. We have also implemented a Lagrangian decomposition algorithm, decom-6 posing the FCLOP model to three subproblems (instead of only two subproblems). The interest of decomposing the FCLOP model to three subproblems comes mostly from the nature of the three subproblems, which are relatively quite easier to solve compared to the initial FCLOP model. Numerical results show a significant improvement in the quality of dual bounds for several instances. We could also obtain relatively quite better dual bounds in a shorter time comparing to the other relaxation strategies. We have proposed a cutting plane algorithm based on the pure relaxation strategy. In this algorithm, we firstly relax a subset of constraints that due to the problem structure, a very few number of them are active. Then in the course of the branch-and-bound tree we verify if there exist any violated constraint among the relaxed constraints or. Then the characterized violated constraints will be globally added to the model. (...)