2LP(ID:8038/)

Linear Programming Language 

Linear programming language

Ken McAloon and Carol Tretkoff
Logic Based Systems Lab, CUNY Graduate Center and Brooklyn College
References:
  • McAloon, K. and C. Tretkoff, 2LP: Linear programming and logic programming, in: Principles and Practice of Constraint Programming, V. Saraswat and P. van Hentenryck, eds., MIT Press, pp.101 ? 116. 1995 view details
  • McAloon, K. and C. Tretkoff, Optimization and Computational Logic, Wiley, 1996 view details
  • McAloon, Ken and Tretkoff, Carol "Logic, modeling, and programming" Annals of Operations Research 71: 335-372, 1997 view details Abstract: In this paper we discuss the integration of logic, modeling, and programming in order to solve problems in operations research, artificial intelligence, and decision support programming in general. Our goals are to integrate modeling into the larger programming scheme of things and, conversely, to inject programming into modeling. To accomplish these ends, we use the language 2LP, which is based on ideas from constraint logic programming. This leads to a technologically open way to handle problems, one which supports flexible treatment of goal programming, hybrid MIP/local search algorithms, libraries for distributed processing, disjunctive programming, etc. An additional advantage of the programming language approach is that problem solving and model management can be abetted by software engineering techniques. In this paper, by means of variations on a single example, we will illustrate how the logical connectives and linear constraints interact in the solution of a linear program, a goal program, a disjunctive program, a branch and bound search, a randomized shuffle algorithm, and a parallel solution to a model with stochastic data. Extract: The 2LP programming language
    The 2LP programming language
    The 2LP language is a constraint logic programming language with C like syntax. The data type continuous is introduced in order to capture the modeling methods of linear programming. Constraints on continuous variables define a polyhedral set called the feasible region. The representation of this convex body (by means of the simplex method) includes a distinguished vertex, called the witness point. Typically, at the end of a program, this vertex will be the solution to an optimization problem.
    Other structural information and communication routines are also connected with the polyhedral set. This collection forms an ?object? to use object-oriented programming (OOP) terminology. 2LP supports these constructs and has its own interpreter. On the other hand, object-oriented programming as in C++ enables one to extend a language with new data types without writing an interpreter for the expanded language. However, in order to support full algebraic modeling and to support the logical connectives in a structured way, the language approach is the most natural one. For the other approach to linear programming and constraint programming, see [31] and [32].
    2LP is different from algebraic modeling languages such as GAMS [11] and AMPL [17] in several ways. First, it is a logical control language as well as a modeling language and so supports search methods not usually available to the MIP modeler. Second, it can directly code disjunctive programs and avoid recoding as a MIP model.
    Third, 2LP supports parameter passing, procedure based modularity and other structured programming constructs. Fourth, the data types int and double in 2LP are the same as in CyC++ and so the 2LP model can be passed pointers to data directly from CyC++ avoiding a detour through a data file.
    As a programming language, 2LP is designed to be embedded in the larger programming scheme of things. The architecture provides for a very modular linkage between the logical control and the mathematical constraint solver. As a result, 2LP supports use of optimization libraries such as Cplex. This means that 2LP can be used for applications that require state-of-the-art optimization software and the system can move with changes in the mathematical programming world.

    Resources