A constraint logic programming language for combinatorial optimization and linear programming

The authors report on the language definition and a prototype implementation of the constrained logic programming shell (Mathematica), or CLPS(M), an instance of the constraint logic programming (CLP) scheme specialized for solving combinatorial optimization and linear programming problems. The work extends the capabilities of current CLAP systems by allowing extremum search for mixed integer and linear programming problems, as well as the easy specification of search heuristics. Arrays have been included as an atomic data-type since they occur frequently in the specification of this class of problems. The three issues addressed by CLPS(M) are finding optimal and approximate solutions to combinatorial problems including mixed integer linear programs, creating compact, intuitive problem representations and using the declarative logical framework to form rule-based heuristics to guide the underlying solver in the combinatorial search space