Modeling Languages in Mathematical Optimization

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.