OPL(ID:2901/opl001)Optimization Programming Language Pascal van Hentenryck MIT 1998 People: Related languages
References: in New Trends in Constraints , Lecture Notes in Artificial Intelligence (LNAI 1865), Springer Verlag, 2000 view details Introduction Combinatorial optimization problems are ubiquitous in many practical applications, including scheduling, resource allocation, planning, and configuration problems. These problems are computationally difficult (i.e., they are NP-hard) and require considerable expertise in optimization, software engineering, and the application domain. The last two decades have witnessed substantial development in tools to simplify the design and implementation of combinatorial optimization problems. Their goal is to decrease development time substantially while preserving most of the efficiency of specialized programs. Most tools can be classified in two categories: mathematical modeling languages and constraint programming languages. Modeling languages such as AMPL [Fourer et al. 1993] and GAMS [Bisschop and Meeraus 1982] provide high-level algebraic and set notations to express, in concise ways, mathematical problems that can then be solved using state-of-the-art solvers. These modeling languages do not require specific programming skills and can be used by a wide audience. Constraint programming languages such as CHIP [Dincbas et al. 1988], Prolog III [Colmerauer 1990], Prolog IV [Colmerauer 1996], Oz [Schulte 1997; Smolka 1995], and Ilog Solver [Ilog Solver 4.4 1998] have orthogonal strengths. Their constraint vocabulary and their underlying solvers go beyond traditional linear and nonlinear constraints and support logical, higher-order, and global constraints. They also make it possible to program search procedures to specify how to explore the search space. However, these languages are mostly aimed at computer scientists and often have weaker abstractions for algebraic and set manipulation. The optimization programming language OPL [Van Hentenryck 1999] is a recent addition in this area, and it originated as an attempt to unify modeling and constraint programming languages, both at the language and at the solver technology level. OPL shares with modeling languages their high-level algebraic and set notations. It also contains some novel functionalities to exploit sparsity in large-scale applications, such as the ability to index arrays with arbitrary data structures. OPL shares with constraint programming languages their rich constraint vocabulary, their support for scheduling and resource allocation problems, and the ability to specify search procedures and strategies. OPL also makes it easy to combine di erent solver technologies for the same application. As mentioned, one of the original features of constraint programming is the ability to program search procedures. This ability was present in constraint logic programming since its inception and was directly inherited from logic programming (e.g., [Colmerauer 1990; Ja ar et al. 1992; Van Hentenryck 1989]). It was supported in constraint programming libraries such as Ilog Solver [Ilog Solver 4.4 1998]. It has been the subject of much recent research in constraint programming (e.g., [Apt et al. 1998; Laburthe and Caseau 1998; Schulte 1997; Van Hentenryck 1999]), and it is generally considered as one of the most important aspects of constraint programming. In contrast, search procedures are generally absent from modeling languages where only limited support is available to tailor predefined search procedures (e.g., by specifying a static variable ordering). One of the main contributions of OPL is to show how search procedures can be specified, in concise and elegant ways, in modeling languages by building on the strengths of both technologies. The purpose of this paper is to give an overview of the search abstractions of OPL and to illustrate how they can be used to implement typical search procedures. A search procedure typically consists of two parts: a search component defining the search tree to explore and a strategy component specifying how to explore this tree. OPL provides high-level abstractions for both components. Its search constructs have many commonalities with recent proposals such as Alma-0 [Apt et al. 1998] and Salsa [Laburthe and Caseau 1998] that were developed independently, and its strategy constructs, based on the model proposed in [Perron 1999], o er a high-level alternative to the computation states of Oz [Schulte 1997]. in ACM Transactions on Computational Logic, 1(2), October 2000 view details Introduction Combinatorial optimization problems are ubiquitous in many practical applications, including scheduling, resource allocation, planning, and configuration problems. These problems are computationally difficult (i.e., they are NP-hard) and require considerable expertise in optimization, software engineering, and the application domain. The last two decades have witnessed substantial development in tools to simplify the design and implementation of combinatorial optimization problems. Their goal is to decrease development time substantially while preserving most of the efficiency of specialized programs. Most tools can be classified in two categories: mathematical modeling languages and constraint programming languages. Mathematical modeling languages such as AMPL [4] and GAMS [1] provides very high-level algebraic and set notations to express concisely mathematical problems that can then be solved using state-of-the-art solvers. These modeling languages do not require specific programming skills and can be used by a wide audience. Constraint programming languages such as CHIP [3], PROLOG III and its successors [2], OZ [12], and ILOG SOLVER [11] have orthogonal strenghts. Their constraint languages, and their underlying solvers, go beyond traditional linear and nonlinear constraints and support logical, high-order, and global constraints. They also make it possible to program search procedures to specify how to explore the search space. However, these languages are mostly aimed at computer scientists and often have weaker abstractions for algebraic and set manipulation. The work described in this paper originated as an attempt to unify modeling and constraint programming languages and their underlying implementation technologies. It led to the development of the optimization programming language OPL [13], its associated script language OPLSCRIPT [15], and its development environment OPL STUDIO. OPL is a modeling language sharing high-level algebraic and set notations with traditional modeling languages. It also contains some novel functionalities to exploit sparsity in large-scale applications, such as the ability to index arrays with arbitrary data structures. OPL shares with constraint programming languages their rich constraint languages, their support for scheduling and resource allocation problems, and the ability to specify search procedures and strategies. OPL also makes it easy to combine different solver technologies for the same application. OPLSCRIPT is a script language for composing and controlling OPL models. Its motivation comes from the many applications that require solving several instances of the same problem (e.g., sensibility analysis), sequences of models, or a combination of both as in column-generation applications. OPLSCRIPT supports a variety of abstractions to simplify these applications, such as OPL models as firstclass objects, extensible data structures, and linear programming bases to name only a few. OPL STUDIO is the development environment of OPL and OPLSCRIPT. Beyond support for the traditional ''edit, execute, and debug'' cycle, it provides automatic visualizations of the results (e.g., Gantt charts for scheduling applications), visual tools for debugging and monitoring OPL models (e.g., visualizations of the search space), and C++ code generation, or C++ or COM components, to integrate an OPL model in a larger application. The code generation produces a class for each model object and makes it possible to add/remove constraints dynamically and to overwrite the search procedure. The purpose of this paper is to illustrate some of the functionalities of OPL and OPLSCRIPT through a number of applications, including a transportation problem, sport and job-shop scheduling applications, and a configuration problems. Extract: Conclusion Conclusion The purpose of this paper was to review, through four applications, a number of features of OPL to give a preliminary understanding of the expressiveness of the language. These features include very high-level algebraic notations and data structures, a rich constraint programming language supporting logical, higher-level, and global constraints, support for scheduling and resource allocation problems, and search procedures and strategies. The paper also introduced briefly OPLSCRIPT, a script language to control and compose OPL models. The four applications presented in this paper should give a preliminary, although very incomplete, understanding of how OPL can decrease development time significantly. in ACM Transactions on Computational Logic, 1(2), October 2000 view details in ACM Transactions on Computational Logic, 1(2), October 2000 view details Resources
|