MIT Press
Modeler++
Modeler++ is a C++ modeling layer that reduces that gap between modeling languages and implementation languages. It demonstrates that many orthogonal functionalities of mathematical modeling tools and constraint programming tools can be seamlessly integrated in libraries without defining language extensions or sacrificing any of the performance achieved by the respective tools.
Modeler++ offers a number of significant benefits. First, it makes available, within traditional object oriented languages the advanced features found in mathematical modeling languages such as sets and algebraic expressions. It also support the development of advanced search strategies commonly found in modeling languages such as OPL. Overall it greatly enhances the modeling capabilities of libraries. Consequently, it leads to higher-level programs that are easier to implement and maintain. Second, it simplifies the implementation of modeling languages as the distance between the library and the modeling tool is substantially smaller. Third, it greatly simplifies the integration of models within an application as the control and data structures are natively implemented with the host language. Finally, it is important to notice that the modeling facilities of modeler++ are not limited to mathematical or constraint programming but extend to local search as well.
Localizer++
Localizer++ is a C++ library for local search founded on Modeler++ that extends the work initiated with localizer in several respects.
First, it extends the concept of invariants by supporting a larger class called global invariants. Global invariants are akin to global constraints as they introduce the idea that semantics relevant to the structure being maintained can be exploited to yield better incremental algorithms (in terms of competitive ratio). For instance, a recent addition to this class of invariants include shortest and longest path computation in directed acyclic graphs, a worthwhile tool for, among others, scheduling problems.
Second, it introduces traditional constraints as a higher level abstraction for problem modeling. Constraints are declarative, and highly compositional. Local models can effectively use constraints. Indeed, local constraints specify properties of the solutions and introduce the notion of constraint violation, a measure of how unsatisfied a constraint is. This central idea forms the basis of a protocol to automatically aggregate constraint violations and provide a sensible optimization function. Hence, local constraints contribute to a higher degree of compositionality. The Localizer++ library now offers traditional constraints such as cardinality or sequence constraints to name a few. Interestingly enough, these constraints can, themselves, be expressed and implemented in terms of invariants.
These efforts are fruitful as localizer++ is used to concisely and easily state and solve state of the art local search models for a variety of hard problems such as magic squares, graph coloring, car sequencing, packing, sport scheduling and jobshop or openshop scheduling problems to name a few. This endeavor can and will be pursued even further, hopefully bringing an increasingly broader class of constraints into the local realm.