ABSTRACT Title of Document: SOLVING TWO-LEVEL OPTIMIZATION PROBLEMS WITH APPLICATIONS TO ROBUST DESIGN AND ENERGY MARKETS Sauleh Ahmad Siddiqui Doctor of Philosophy, 2011 Directed By: Steven A. Gabriel, Associate Professor Department of Civil and Environmental Engineering Shapour Azarm, Professor Department of Mechanical Engineering This dissertation provides efficient techniques to solve two-level optimization problems. Three specific types of problems are considered. The first problem is robust optimization, which has direct applications to engineering design.
Traditionally robust optimization problems have been solved using an inner-outer structure, which can be computationally expensive. This dissertation provides a method to decompose and solve this two-level structure using a modified Benders decomposition. This gradient-based technique is applicable to robust optimization problems with quasiconvex constraints and provides approximate solutions to problems with nonlinear constraints. The second types of two-level problems considered are mathematical and equilibrium programs with equilibrium constraints.
Their two-level structure is simplified using Schur‟s decomposition and reformulation schemes for absolute value functions. The resulting formulations are applicable to game theory problems in operations research and economics. The third type of two- level problem studied is discretely-constrained mixed linear complementarity problems. These are first formulated into a two-level mathematical program with equilibrium constraints and then solved using the aforementioned technique for mathematical and equilibrium programs with equilibrium constraints.
The techniques for all three problems help simplify the two-level structure into one level, which helps gain numerical and application insights. The computational effort for solving these problems is greatly reduced using the techniques in this dissertation. Finally, a host of numerical examples are presented to verify the approaches. Diverse applications to economics, operations research, and engineering design motivate the relevance of the novel methods developed in this dissertation.
SOLVING TWO-LEVEL OPTIMIZATION PROBLEMS WITH APPLICATIONS TO ROBUST DESIGN AND ENERGY MARKETS By Sauleh Ahmad Siddiqui Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park, in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2011 Advisory Committee: Associate Professor Steven A. Gabriel, Co-Advisor/Chair Professor Shapour Azarm, Co-Advisor Associate Professor Radu V. Balan Professor Dianne P. O‟Leary Professor Lars J.
Olson, Dean‟s Representative © Copyright by Sauleh Ahmad Siddiqui 2011 Acknowledgements First and foremost, I would like to thank my advisers Dr. Gabriel and Dr. Shapour Azarm for all their help and support. Their perpetual encouragement, abundant patience, and careful guidance made this work possible.
My time at this university was made memorable because of them, and I am proud to look back and realize how much I have learned from them. I would also like to thank my committee members for agreeing to advise me on this work: Dr. Balan, for overlooking the mathematical aspects in both my preliminary oral exam and dissertation; Dr. O‟Leary, whose survival manual for graduate study in the computer and mathematical sciences provided valuable advice; and Dr.
Olson for graciously agreeing to serve as the Dean‟s representative. I am grateful that they have taken time out from their busy schedules to provide insight. I also want to acknowledge funding received from the Office of Naval Research and the Norwegian Research Council. The work presented in this dissertation was supported in part by the Office of Naval Research Contract N000140810384.
The LinkS project funded by Norwegian Research Council via the Norwegian University of Science and Technology and SINTEF (UMD Award number 013768-001) also supported part of the work in this dissertation. Such support does not constitute an endorsement by the funding agency of the opinions expressed in this dissertation. ii Table of Contents ACKNOWLEDGEMENTS. ii TABLE OF CONTENTS.
iii LIST OF TABLES. vi LIST OF FIGURES. vii NOMENCLATURE AND ABBREVIATIONS. viii CHAPTER 1: INTRODUCTION.
MOTIVATION AND OBJECTIVE. Solving Robust Optimization Problems. Solving Mathematical Programs and Equilibrium Problems with Equilibrium Constraints. Solving Discretely-Constrained Mixed-Integer Linear Complementarity Problems.
ORGANIZATION OF DISSERTATION. 5 CHAPTER 2: DEFINITIONS AND LITERATURE REVIEW. DEFINITIONS AND TERMINOLOGIES. Mathematical and Equilibrium Programs with Equilibrium Constraints .3 Discretely-Constrained Mixed Linear Complementarity Problems.
OVERVIEW OF PREVIOUS WORK .3 Mathematical and Equilibrium Programs with Equilibrium Constraints. Discretely-Constrained Mixed Linear Complementarity Problems. Approximating Nonlinear Functions using SOS Type 1 and Type 2 Variables. 31 CHAPTER 3: SOLVING ROBUST OPTIMIZATION PROBLEMS USING A MODIFIED BENDERS METHOD .3 MODIFIED BENDERS DECOMPOSITION.
Formulation of Approach: Solving Robust Linear Programs. Formulation of Approach: Solving Robust Optimization Problems with Quasiconvex Constraints. Formulation of Approach: Solving Robust Optimization Problems with Nonlinear Constraints. Numerical Example (Example 1) to Show Methodology Step-by-Step.
ENGINEERING DESIGN AND OTHER APPLICATIONS. Fleury‟s Weight Minimization. Design of a Welded Beam. Heat Exchanger Design.
Building Energy Intensive Infrastructure. 90 CHAPTER 4: SOLVING MATHEMATICAL PROGRAMS AND EQUILIBRIUM PROGRAMS WITH EQUILIBRIUM CONSTRAINTS. SOLVING MATHEMATICAL PROGRAMS WITH EQUILIBRIUM CONSTRAINTS. Changing the Formulation of the Lower-Level Problem.
Approximating The Absolute Value Function Using Special Ordered Sets of Type 1 Variables. Approximating Absolute Value Function Using a Penalty Method. Algorithm 1 to Solve Mathematical Programs with Equilibrium Constraints. SOLVING EQUILIBRIUM PROGRAMS WITH EQUILIBRIUM CONSTRAINTS .1 to Equilibrium Programs with Equilibrium Constraints .2 to Solve Equilibrium Problems with Equilibrium Constraints (Heuristic).
Numerical Results for Equilibrium Programs with Equilibrium Constraints. THE NORTH AMERICAN GAS MODEL. Shale Gas in the United States. 134 CHAPTER 5: SOLVING DISCRETELY-CONSTRAINED MIXED LINEAR COMPLEMENTARITY PROBLEMS.
DISCRETELY-CONSTRAINED MIXED LINEAR COMPLEMENTARITY PROBLEMS. Complementarity, Integrality Trade-off. Formulation to Solve Discretely-Constrained Mixed Linear Complementary problems. DISCRETELY-CONSTRAINED NASH-COURNOT GAMES.
Formulation of a DC-Nash game by Gabriel et al. First Numerical Example. Results for First Numerical Example. Numerical Example Relevant to Production Systems.
DISCRETELY-CONSTRAINED NETWORK PROBLEMS. First Network Example. Second Network Example. MPECs and EPECs.
Discretely-Constrained Mixed Linear Complementarity Problems. Multiobjective Mixed-Integer Robust Optimization. Solving Nonlinear MPECs and EPECs. Solving Large-Scale Mixed-Integer Complementary Problems.
190 APPENDIX A: ROBUST OPTIMIZATION TEST PROBLEMS. 190 APPENDIX B: DISCUSSION ON FUNCTION CALLS. 201 v List of Tables Table 2.1: Definition of Terms for Robust Optimization Table 2.2: Definition of Terms for Benders Decomposition Table 3.1: Analysis of function calls for one iteration Table 3.2: Solution Steps for Modified Benders Approach Table 3.3: Detailed Solution for Simple Problem Table 3.4: Description of Test Problems Table 3.5: Results for Fleury‟s Weight Minimization Like Problem Table 3.6: Results of Welded Beam Example Table 3.7: Design Variables and Parameters with Uncertainty Table 3.8: Results for Heat Exchanger Design Table 3.9: Number of Iterations and CPU Time to Solve Problems Table 3.10: Results for Increasing Uncertainty in t2 Table 4.1: Definition of terms for simple example Table 4.2: Different Datasets to Compare (4.3: Different Cases to Compare Solutions to (25) Table 4.4: Results for Dataset 1 Table 4.5: Results for Dataset 2 Table 4.6: Results for Dataset 3 Table 4.7: Results for Dataset 1 Table 4.8: Results for Dataset 2 Table 4.9: Results for Dataset 3 Table 4.10: World Gas Model Nodes: Coverage of States and Shale Basins Table 4.11: Prices in $/MMBTU in 2025 Table 5.1: Bimatrix Nash-Cournot Game, Profits(q1/q2) Table 5.2: Nash-Cournot Game, Profits(q1/q2), (Only Adjustments a=9, ρ₂ = 3) Table 5.3: Description of Formulation Variations Table 5.4: Summary of Results (a = 9, b = 1, β₁= β₂ = 1,ρ₁ = 1, ρ₂ = 3) Table 5.5: Summary of Results (a = 9, b = 1, β₁= β₂ = 1,ρ₁ = 1, ρ₂ = 3) Table 5.6: Summary of Results (Example Relevant to Production Systems) Table 5.7: Summary of Results (Example Relevant to Production Systems) Table 5.8: Parameter Values Used in First Network Example Table 5.9: Description of Formulation Variations Table 5.10: Solution to Power Market Example Table 5.11: Dataset Used in Second Network Example Table 5.12: Description of Formulation Variations for Second Network Example Table 5.13: Results for Second Network Problem (Integer Variables) Table 5.14: Results for Second Network Problem (Other Variables) vi List of Figures Figure 1.1: Organization of Dissertation Figure 2.1: The Structure of a Two-Level Problem Figure 2.2: Representation of a Robust Optimization Problem Figure 2.3: Representation of an MPEC Figure 2.4: Representation of an EPEC Figure 2.5: Representation of a DC-MLCP Figure 2.6: Approximating a Nonlinear Function Using SOS Type 1 Variable Figure 2.7: Approximation of Nonlinear Functions using SOS Type 2 Variables Figure 3.1: Comparison of the Feasible Region with the Robust Feasible Region Figure 3.2: The Robust Benders Cuts to Estimate the Maximum Endpoint of αu Figure 3.3: Checking Feasibility by Interval-Optimal Points for Constraints Figure 3.4: Adding a modified (Robust) Benders Cut Figure 3.5: Design of a Welded Beam (Gunawan & Azarm, 2004) Figure 3.6: Heat Exchanger Schematic Figure 4.1: Computational Time for Solving Problem Figure 4.2: A Marginal Cost Structure for Shale Gas (Skagen, 2010) Figure 4.3: A Marginal Cost Structure for Shale Gas Figure 4.4: Overall Production in 2025 as Predicted by the Model Figure 4.5: Producer Profit in 2025 as Predicted by the Model Figure 4.6: Shale Producers in 2025 as Predicted by the Model Figure 4.7: Consumption in 2025 as Predicted by the Model Figure 5.1: The Tradeoff Between Complementary and Integrality Figure 5.2: Computational Time for First Numerical Example Figure 5.3: Computational Time for Example Relevant to Production Systems Figure 5.4: Diagram of First Network Example Figure 5.5: Representation of Second Network Example vii Nomenclature and Abbreviations BCM Billion Cubic Meters DC-MLCP Discretely-Constrained Mixed Linear Complementary Problems DC-Nash Discretely-Constrained Nash Game EPEC Equilibrium Program with Equilibrium Constraints f Objective Function (Unless stated otherwise) g Inequality Constraint Function (Unless stated otherwise) KKT Karush-Kuhn-Tucker Conditions LBF Pound Force LP Linear Program MCF Million Cubic Feet MIP Mixed Integer Program MILP Mixed Integer Linear Program MMBTU One million British Thermal Units; measurement of heat energy MPEC Mathematical Programs with Equilibrium Constraints NCP Nonlinear Complementary Problem The real numbers SOS Special Ordered Set x Decision Variable WGM World Gas Model Z The Integers viii Chapter 1: Introduction 1. Motivation and Objective Mathematical modeling of problems arising in engineering and economics often requires formulations where optimal decisions need to be made at two different levels.
These levels can be distinguished by time, space, decision choices, or even sets of players. An optimal decision at each level, we assume, can be obtained using an optimization problem. Consider some of many types of decisions made by the computer processor manufacturer Intel. First while making the processor, manufacturing errors and uncertainty can lead to their “best” design being infeasible.
If not infeasible, the design might not be the best choice under uncertainty. This decision needs to be made accounting for the uncertainty or errors that can develop after manufacturing the product. Second, while deciding the price (or quantity) of the processor, Intel would have to take into account what its competitors are doing and if the government has made any regulations regarding taxation or distribution. Setting a price, thus, not only depends on Intel‟s own costs but the strategy of other actors at a different level than Intel.
Finally, Intel needs to decide the number of processors to ship to specific locations. Even considering a simplified version of the market makes this a complex problem as network dynamics, transportation costs, and local demand all weigh into the decision. But, more importantly, the processors can only be transported in positive integer number quantities, as opposed to fractional quantities. 1 All the problems classified above fall under the umbrella of two-level problems.
The first decision, regarding uncertainty, requires the initial proposed design of the chip to be such that the presence of uncertainty does not cause the design to be infeasible and/or suboptimal. The decision is thus made to ensure feasibility of design constraints as well as minimum variation in a design‟s performance under uncertainty. Such a problem will be described in this dissertation as a Robust Optimization problem.