Modeling Languages in Mathematical Optimization

ISBN-13: 9781461379454 / Angielski / Miękka / 2011 / 408 str.

Josef Kallrath

Opis

This book deals with the aspects of modeling and solving real-world optimiza tion problems in a unique combination. It treats systematically the major mod eling languages and modeling systems used to solve mathematical optimization problems. The book is an offspring ofthe 71 st Meeting of the GOR (Gesellschaft fill Operations Research) Working Group Mathematical Optimization in Real Life which was held under the title Modeling Languages in Mathematical Op timization during April 23-25, 2003 in the German Physics Society Confer ence Building in Bad Honnef, Germany. The modeling language providers AIMMS Johannes Bisschop, Paragon Decision Technology B. V, Haarlem, The Netherlands, AMPL Bob Fourer, Northwestern Univ.; David M. Gay, AMPL Optimization LLC., NJ, GAMS Alexander Meeraus, GAMS Development Corporation, Washington D. C., Mosel Bob Daniel, Dash Optimization, Blisworth, UK, MPL Bjami Krist jansson, Maximal Software, Arlington, VA, NOP-2 Hermann Schichl, Vienna University, Austria, PCOMP Klaus Schittkowski, Bayreuth University, Germany, and OPL Sofiane Oussedik, ILOG Inc., Paris, France gave deep insight into their motivations and conceptual design features of their software, highlighted their advantages but also critically discussed their limits. The participants benefited greatly from this symposium which gave a useful overview and orientation on today's modeling languages in optimization. Roughly speaking, a modeling language serves the need to pass data and a mathematical model description to a solver in the same way that people, es Of course, in pecially mathematicians describe those problems to each other.

Spis treści

I Theoretical and Practical Concepts of Modeling Languages.- 1 Mathematical Optimization and the Role of Modeling Languages.- 1.1 Mathematical Optimization.- 1.2 Classes of Problems in Mathematical Optimization.- 1.2.1 A Deterministic Standard MINLP Problem.- 1.2.2 Constraint Satisfaction Problems.- 1.2.3 Multi-Objective Optimization.- 1.2.4 Multi-Level Optimization.- 1.2.5 Semi-Infinite Programming.- 1.2.6 Optimization Involving Differential Equations.- 1.2.7 Safety Programming.- 1.2.8 Optimization Under Uncertainty.- 1.2.8.1 Approaches to Optimization Under Uncertainty.- 1.2.8.2 Stochastic Optimization.- 1.2.8.3 Beyond Stochastic Programming.- 1.3 The History of Modeling Languages in Optimization.- 1.4 Conventions and Abbreviations.- 2 Models and the History of Modeling.- 2.1 The History of Modeling.- 2.2 Models.- 2.3 Mathematical Models.- 2.4 The Modeling Process.- 2.4.1 The Importance of Good Modeling Practice.- 2.4.2 Making Mathematical Models Accessible for Computers.- 3 Mathematical Model Building.- 3.1 Why Mathematical Modeling?.- 3.2 A List of Applications.- 3.3 Basic numerical tasks.- 3.4 The Modeling Diagram.- 3.5 General Rules.- 3.6 Conflicts.- 3.7 Attitudes.- 4 Theoretical Concepts and Design of Modeling Languages.- 4.1 Modeling Languages.- 4.1.1 Algebraic Modeling Languages.- 4.1.2 Non-algebraic Modeling Languages.- 4.1.3 Integrated Modeling Environments.- 4.1.4 Model-Programming Languages.- 4.1.5 Other Modeling Tools.- 4.2 Global Optimization.- 4.2.1 Problem Description.- 4.2.2 Algebraic Modeling Languages and Global Optimization.- 4.3 A Vision — What the Future Needs to Bring.- 4.3.1 Data Handling.- 4.3.2 Solver Views.- 4.3.3 GUI.- 4.3.4 Object Oriented Modeling — Derived Models.- 4.3.5 Hierarchical Modeling.- 4.3.6 Building Blocks.- 4.3.7 Open Model Exchange Format.- 5 The Importance of Modeling Languages for Solving Real-World Problems.- 5.1 Modeling Languages and Real World Problems.- 5.2 Requirements from Practitioners towards Modeling Languages and Modeling Systems.- II The Modeling Languages in Detail.- 6 The Modeling Language AIMMS.- 6.1 AIMMS Design Philosophy, Features and Benefits.- 6.2 AIMMS Outer Approximation (AOA) Algorithm.- 6.2.1 Problem Statement.- 6.2.2 Basic Algorithm.- 6.2.3 Open Solver Approach.- 6.2.4 Alternative Uses of the Open Approach.- 6.3 Units of Measurement.- 6.3.1 Unit Analysis.- 6.3.2 Unit-Based Scaling.- 6.3.3 Unit Conventions.- 6.4 Time-Based Modeling.- 6.4.1 Calendars.- 6.4.2 Horizons.- 6.4.3 Data Conversion of Time-Dependent Identifiers.- 6.5 The AIMMS Excel Interface.- 6.5.1 Excel as the Main Application.- 6.5.2 AIMMS as the Main Application.- 6.6 Multi-Agent Support.- 6.6.1 Basic Agent Concepts.- 6.6.2 Examples of Motivation.- 6.6.3 Agent-Related Concepts in AIMMS.- 6.6.4 Agent Construction Support.- 6.7 Future Developments.- A AIMMS Features Overview.- A.1 Language Features.- A.2 Mathematical Programming Features.- A.3 End-User Interface Features.- A.4 Connectivity and Deployment Features.- B Application Examples.- 7 Design Principles and New Developments in the AMPL Modeling Language.- 7.1 Background and Early History.- 7.2 The McDonald’s Diet Problem.- 7.3 The Airline Fleet Assignment Problem.- 7.4 Iterative Schemes.- 7.4.1 Flow of Control.- 7.4.2 Named Subproblems.- 7.4.3 Debugging.- 7.5 Other Types of Models.- 7.5.1 Piecewise-Linear Terms.- 7.5.2 Complementarity Problems.- 7.5.3 Combinatorial Optimization.- 7.5.4 Stochastic Programming.- 7.6 Communicating with Other Systems.- 7.6.1 Relational Database Access.- 7.6.2 Internet Optimization Services.- 7.6.3 Communication with Solvers via Suffixes.- 7.7 Updated AMPL Book.- 7.8 Concluding Remarks.- 8 General Algebraic Modeling System (GAMS).- 8.1 Background and Motivation.- 8.2 Design Goals and Changing Focus.- 8.3 A User’s View of Modeling Languages.- 8.3.1 Academic Research Models.- 8.3.2 Domain Expert Models.- 8.3.3 Black Box Models.- 8.4 Summary and Conclusion.- A Selected Language Features.- B GAMS External Functions.- C Secure Work Files.- D GAMS versus FORTRAN Matrix Generators.- E Sample GAMS Problem.- 9 The LINGO Algebraic Modeling Language.- 9.1 History.- 9.2 Design Philosophy.- 9.2.1 Simplified Syntax for Small Models.- 9.2.2 Close Coupled Solvers.- 9.2.3 Interface to Excel.- 9.2.4 Model Class Identification.- 9.2.5 Automatic Linearization and Global Optimization.- 9.2.6 Debugging Models.- 9.2.7 Programming Interface.- 9.3 Future Directions.- 10 The LPL Modeling Language.- 10.1 History.- 10.2 Some Basic Ideas.- 10.3 Highlights.- 10.4 The Cutting Stock Problem.- 10.5 Liquid Container.- 10.6 Model Documentation.- 10.7 Conclusion.- 11 The MINOPT Modeling Language.- 11.1 Introduction.- 11.1.1 Motivation.- 11.1.2 MINOPT Overview.- 11.2 Model Types and Solution Algorithms.- 11.2.1 Mixed-Integer Nonlinear Program (MINLP).- 11.2.1.1 Generalized Benders Decomposition (GBD).- 11.2.1.2 Outer Approximation/Equality Relaxation/Augmented Penalty (OA/ER/AP).- 11.2.2 Nonlinear Program with Differential and Algebraic Constraints (NLP/DAE).- 11.2.3 Mixed-Integer Nonlinear Program with Differential and Algebraic Constraints (MINLP/DAE).- 11.2.4 Optimal Control Problem (OCP) and Mixed Integer Optimal Control.- 11.2.5 External Solvers.- 11.3 Example Problems.- 11.3.1 Language Overview.- 11.3.2 MINLP Problem—Nonconvex Portfolio Optimization Problem.- 11.3.3 Optimal Control Problem—Dow Batch Reactor.- 11.4 Summary.- 12 Mosel: A Modular Environment for Modeling and Solving Optimization Problems.- 12.1 Introduction.- 12.1.1 Solver Modules.- 12.1.2 Other Modules.- 12.1.3 User Modules.- 12.1.4 Contents of this Chapter.- 12.2 The Mosel Language.- 12.2.1 Example Problem.- 12.2.2 Types and Data Structures.- 12.2.3 Initialization of Data/Data File Access.- 12.2.4 Language Constructs.- 12.2.4.1 Selections.- 12.2.4.2 Loops.- 12.2.5 Set Operations.- 12.2.6 Subroutines.- 12.3 Mosel Libraries.- 12.4 Mosel Modules.- 12.4.1 Available Modules.- 12.4.2 QP Example with Graphical Output.- 12.4.3 Example of a Solution Algorithm.- 12.5 Writing User Modules.- 12.5.1 Defining a New Subroutine.- 12.5.2 Creating a New Type.- 12.5.2.1 Module Context.- 12.5.2.2 Type Creation and Deletion.- 12.5.2.3 Type Transformation to and from String.- 12.5.2.4 Overloading of Arithmetic Operators.- 12.6 Summary.- 13 The MPL Modeling System.- 13.1 Maximal Software and Its History.- 13.2 Algebraic Modeling Languages.- 13.2.1 Comparison of Modeling Languages.- 13.2.1.1 Modeling Language.- 13.2.1.2 Multiple Platforms.- 13.2.1.3 Open Design.- 13.2.1.4 Indexing.- 13.2.1.5 Scalability.- 13.2.1.6 Memory Management.- 13.2.1.7 Speed.- 13.2.1.8 Robustness.- 13.2.1.9 Deployment.- 13.2.1.10 Pricing.- 13.3 MPL Modeling System.- 13.3.1 MPL Integrated Model Development Environment.- 13.3.1.1 Solve the Model.- 13.3.1.2 View the Solution Results.- 13.3.1.3 Display Graph of the Matrix.- 13.3.1.4 Change Option Settings.- 13.4 MPL Modeling Language.- 13.4.1 Sparse Index and Data Handling.- 13.4.2 Scalability and Speed.- 13.4.3 Structure of the MPL Model File.- 13.4.3.1 Sample Model in MPL: A Production Planning Model.- 13.4.3.2 Going Through the Model File.- 13.4.4 Connecting to Databases.- 13.4.5 Reading Data from Text Files.- 13.4.6 Connecting to Excel Spreadsheets.- 13.4.7 Optimization Solvers Supported by MPL.- 13.5 Deployment into Applications.- 13.5.1 Deployment Phase: Creating End-User Applications.- 13.5.2 OptiMax 2000 Component Library Application Building Features.- 14 The Optimization Systems MPSX and OSL.- 14.1 Introduction.- 14.2 MPSX from its Origins to the Present.- 14.2.1 Initial Stages Leading to MPSX/370.- 14.2.2 The Role of the IBM Scientific Centers.- 14.2.3 An Important Product: Airline Crew Scheduling.- 14.2.4 MPSX Management in White Plains and Transition to Paris.- 14.2.5 A Major Growth Period in LP and MIP: MPSX/370; 1972-1985.- 14.2.6 MPSX as an Engine in Research and Applications.- 14.2.6.1 CASE A: Algorithmic Tools for Solving Difficult Models.- 14.2.6.2 CASE B: New Solver Programs with ECL.- 14.2.6.3 CASE C: Application Packages – Precursors to Modeling.- 14.2.7 Business Cases for MPSX.- 14.2.8 Changes in Computing, Development and Marketing Groups.- 14.2.9 Transition to OSL.- 15 The NOP-2 Modeling Language.- 15.1 Introduction.- 15.2 Concepts.- 15.3 Specialties of NOP-2.- 15.3.1 Specifying Structure — The Element Concept.- 15.3.2 Data and Numbers.- 15.3.3 Sets and Lists.- 15.3.4 Matrices and Tensors.- 15.3.5 Stochastic and Multistage Programming.- 15.3.6 Recursive Modeling and Other Components.- 15.4 Conclusion.- 16 The OMNI Modeling System.- 16.1 OMNI Features as they Developed Historically.- 16.1.1 Early History.- 16.1.2 Activities Versus Equations.- 16.1.3 Recent and Current Trends.- 16.2 Omni Features to Meet Applications Needs.- 16.3 OMNI Example.- 16.4 Omni Features.- 16.5 Summary.- 17 The OPL Studio Modeling System.- 17.1 Introduction.- 17.2 Overview of OPL.- 17.3 Overview of OPL Studio.- 17.4 Mathematical Programming.- 17.5 Frequency Allocation.- 17.6 Sport Scheduling.- 17.7 Job-Shop Scheduling.- 17.8 Scene Allocation.- 17.9 The Trolley Application.- 17.10 Visualization.- 17.11 Conclusion.- Appendix: Advanced Models.- A A Round-Robin Model for Sport-Scheduling.- B The Complete Trolley Model.- 18 PCOMP: A Modeling Language for Nonlinear Programs with Automatic Differentiation.- 18.1 Introduction.- 18.2 Automatic Differentiation.- 18.3 The PCOMP Language.- 18.4 Program Organization.- 18.5 Case Study: Interactive Data Fitting with EASY-FIT.- 18.6 Summary.- 19 The Tomlab Optimization Environment.- 19.1 Introduction.- 19.2 MATLAB as a Modeling Language.- 19.3 The TOMLAB Development.- 19.4 The Design of TOMLAB.- 19.4.1 Structure Input and Output.- 19.4.2 Description of the Input Problem Structure.- 19.4.3 Defining an Optimization Problem.- 19.4.4 Solving Optimization Problems.- 19.5 A Nonlinear Programming Example.- III The Future of Modeling Systems.- 20 The Future of Modeling Languages and Modeling Systems.- References.

O autorze

Prof. Dr. Josef Kallrath ist in der Praxis und Lehre tätig und löst mit Wissenschaftlichem Rechnen praktische Probleme in der Industrie. Schwerpunkt seiner Tätigkeit ist die Mathematische Optimierung zur Unterstützung von Entscheidungsprozessen und die Modellierung physikalischer Systeme. Lehrtätigkeiten übte er an der Universität Heidelberg und derzeitig an der University of Florida in Gainesville/USA aus. Seit 2002 leitet er die Arbeitsgruppe 'raxis der mathematischen Optimierung' der Gesellschaft für Operations Research (GOR).