OptimJ

Last updated
OptimJ
Paradigm object-oriented
Designed by Ateji
First appeared2006 (2006)
Website www.Ateji.com
Influenced by
Java

OptimJ is an extension for Java with language support for writing optimization models and abstractions for bulk data processing. The extensions and the proprietary product implementing the extensions were developed by Ateji which went out of business in September 2011. [1] OptimJ aims at providing a clear and concise algebraic notation for optimization modeling, removing compatibility barriers between optimization modeling and application programming tools, and bringing software engineering techniques such as object-orientation and modern IDE support to optimization experts.

Contents

OptimJ models are directly compatible with Java source code, existing Java libraries such as database access, Excel connection or graphical interfaces. OptimJ is compatible with development tools such as Eclipse, CVS, JUnit or JavaDoc. OptimJ is available free with the following solvers: lp_solve, glpk, LP or MPS file formats and also supports the following commercial solvers: MOSEK, IBM ILOG CPLEX Optimization Studio.

Language concepts

OptimJ combines concepts from object-oriented imperative languages with concepts from algebraic modeling languages for optimization problems. Here we will review the optimization concepts added to Java, starting with a concrete example.

The example of map coloring

The goal of a map coloring problem is to color a map so that regions sharing a common border have different colors. It can be expressed in OptimJ as follows.

packageexamples;// a simple model for the map-coloring problempublicmodelSimpleColoringsolverlpsolve{// maximum number of colorsintnbColors=4;// decision variables hold the color of each countryvarintbelgiumin1..nbColors;varintdenmarkin1..nbColors;varintgermanyin1..nbColors;// neighbouring countries must have a different colorconstraints{belgium!=germany;germany!=denmark;}// a main entry point to test our modelpublicstaticvoidmain(String[]args){// instantiate the modelSimpleColoringm=newSimpleColoring();// solve itm.extract();m.solve();// print solutionsSystem.out.println("Belgium: "+m.value(m.belgium));System.out.println("Denmark: "+m.value(m.denmark));System.out.println("Germany: "+m.value(m.germany));}}

Readers familiar with Java will notice a strong similarity with this language. Indeed, OptimJ is a conservative extension of Java: every valid Java program is also a valid OptimJ program and has the same behavior.

This map coloring example also shows features specific to optimization that have no direct equivalent in Java, introduced by the keywords model, var, constraints.

OR-specific concepts

Models

A model is an extension of a Java class that can contain not only fields and methods but also constraints and an objective function. It is introduced by the model keyword and follows the same rules as class declarations. A non-abstract model must be linked to a solver, introduced by the keyword solver. The capabilities of the solver will determine what kind of constraints can be expressed in the model, for instance a linear solver such as lp solve will only allow linear constraints.

publicmodelSimpleColoringsolverlpsolve

Decision variables

Imperative languages such as Java provide a notion of imperative variables, which basically represent memory locations that can be written to and read from.

OptimJ also introduces the notion of a decision variable, which basically represents an unknown quantity whose value one is searching. A solution to an optimization problem is a set of values for all its decision variables that respects the constraints of the problem—without decision variables, it would not possible to express optimization problems. The term "decision variable" comes from the optimization community, but decision variables in OptimJ are the same concept as logical variables in logical languages such as Prolog.

Decision variables have special types introduced by the keyword var. There is a var type for each possible Java type.

// a var type for a Java primitive typevarintx;// a var type for a user-defined classvarMyClassy;

In the map coloring example, decision variables were introduced together with the range of values they may take.

varintgermanyin1..nbColors;

This is just a shorthand equivalent to putting a constraint on the variable.

Constraints

Constraints express conditions that must be true in any solution of the problem. A constraint can be any Java boolean expression involving decision variables.

In the map coloring example, this set of constraints states that in any solution to the map coloring problem, the color of Belgium must be different from the color of Germany, and the color of Germany must be different from the color of Denmark.

constraints{belgium!=germany;germany!=denmark;}

The operator != is the standard Java not-equal operator.

Constraints typically come in batches and can be quantified with the forall operator. For instance, instead of listing all countries and their neighbors explicitly in the source code, one may have an array of countries, an array of decision variables representing the color of each country, and an array boolean[][] neighboring or a predicate (a boolean function) boolean isNeighbor(). 

constraints{forall(Countryc1:countries,Countryc2:countries,:isNeighbor(c1,c2)){color[c1]!=color[c2];}}

Country c1 : countries is a generator: it iterates c1 over all the values in the collection countries.

:isNeighbor(c1,c2) is a filter: it keeps only the generated values for which the predicate is true (the symbol : may be read as "if").

Assuming that the array countries contains belgium, germany and denmark, and that the predicate isNeighbor returns true for the couples (Belgium , Germany) and (Germany, Denmark), then this code is equivalent to the constraints block of the original map coloring example.

Objectives

Optionally, when a model describes an optimization problem, an objective function to be minimized or maximized can be stated in the model.

Generalist concepts

Generalist concepts are programming concepts that are not specific to OR problems and would make sense for any kind of application development. The generalist concepts added to Java by OptimJ make the expression of OR models easier or more concise. They are often present in older modeling languages and thus provide OR experts with a familiar way of expressing their models.

Associative arrays

While Java arrays can only be indexed by 0-based integers, OptimJ arrays can be indexed by values of any type. Such arrays are typically called associative arrays or maps. In this example, the array age contains the age of persons, identified by their name:

int[String]age;

The type int[String] denoting an array of int indexed by String. Accessing OptimJ arrays using the standard Java syntax:

age["Stephan"]=37;x=age["Lynda"];

Traditionally, associative arrays are heavily used in the expression of optimization problems. OptimJ associative arrays are very handy when associated to their specific initialization syntax. Initial values can be given in intensional definition, as in:

int[String]age={"Stephan"->37,"Lynda"->29};

or can be given in extensional definition, as in:

int[String]length[Stringname:names]=name.length();

Here each of the entries length[i] is initialized with names[i].length().

Extended initialization

Tuples

Tuples are ubiquitous in computing, but absent from most mainstream languages including Java. OptimJ provides a notion of tuple at the language level that can be very useful as indexes in combination with associative arrays.

(:int,String:)myTuple=new(:3,"Three":);Strings=myTuple#1;

Tuple types and tuple values are both written between (: and :).

Ranges

Comprehensions

Comprehensions, also called aggregates operations or reductions, are OptimJ expressions that extend a given binary operation over a collection of values. A common example is the sum:

// the sum of all integers from 1 to 10intk=sum{i|intiin1..10};

This construction is very similar to the big-sigma summation notation used in mathematics, with a syntax compatible with the Java language.

Comprehensions can also be used to build collections, such as lists, sets, multisets or maps:

// the set of all integers from 1 to 10HashSet<Integer>s=`hashSet(){i|intiin1..10};

Comprehension expressions can have an arbitrary expression as target, as in:

// the sum of all squares of integers from 1 to 10intk=sum{i*i|intiin1..10};

They can also have an arbitrary number of generators and filters:

// the sum of all f(i,j), for 0<=i<10, 1<=j<=10 and i!=j intk=sum{f(i,j)|inti:10,intj:1..10,:i!=j}

Comprehension need not apply only to numeric values. Set or multiset-building comprehensions, especially in combination with tuples of strings, make it possible to express queries very similar to SQL database queries:

// select name from persons where age > 18`multiSet(){p.name|Personp:persons,:p.age>18}

In the context of optimization models, comprehension expressions provide a concise and expressive way to pre-process and clean the input data, and format the output data.

Development environment

OptimJ is available as an Eclipse plug-in. The compiler implements a source-to-source translation from OptimJ to standard Java, thus providing immediate compatibility with most development tools of the Java ecosystem.

OptimJ GUI and Rapid Prototyping

Since the OptimJ compiler knows about the structure of all data used in models, it is able to generate a structured graphical view of this data at compile-time. This is especially relevant in the case of associative arrays where the compiler knows the collections used for indexing the various dimensions.

The basic graphical view generated by the compiler is reminiscent of an OLAP cube. It can then be customized in many different ways, from simple coloring up to providing new widgets for displaying data elements.

The compiler-generated OptimJ GUI saves the OR expert from writing all the glue code required when mapping graphical libraries to data. It enables rapid prototyping, by providing immediate visual hints about the structure of data.

Another part of the OptimJ GUI reports in real time performance statistics from the solver. This information can be used for understanding performance problems and improving solving time. At this time, it is available only for lp_solve.

Supported solvers

OptimJ is available for free with the following solvers lp_solve, glpk, LP or MPS file formats and also supports the following commercial solvers: Mosek, IBM ILOG CPLEX Optimization Studio.

Related Research Articles

In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function with the value or reference to which the name was bound when the closure was created. Unlike a plain function, a closure allows the function to access those captured variables through the closure's copies of their values or references, even when the function is invoked outside their scope.

In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container's elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled.

In computer programming, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a language. The basic idea is to have a class for each symbol in a specialized computer language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate (interpret) the sentence for a client. See also Composite pattern.

Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state the constraints on the feasible solutions for a set of decision variables. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological backtracking and constraint propagation, but may use customized code like a problem specific branching heuristic.

In object-oriented and functional programming, an immutable object is an object whose state cannot be modified after it is created. This is in contrast to a mutable object, which can be modified after it is created. In some cases, an object is considered immutable even if some internally used attributes change, but the object's state appears unchanging from an external point of view. For example, an object that uses memoization to cache the results of expensive computations could still be considered an immutable object.

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, Boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.

Foreach loop Control flow statement

Foreach loop is a control flow statement for traversing items in a collection. Foreach is usually used in place of a standard for loop statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set", rather than "do this x times". This avoids potential off-by-one errors and makes code simpler to read. In object-oriented languages an iterator, even if implicit, is often used as the means of traversal.

In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region.

Java syntax

The syntax of Java refers to the set of rules defining how a Java program is written and interpreted.

In computer science, the min-conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems.

SystemVerilog hardware description and hardware verification language

SystemVerilog, standardized as IEEE 1800, is a hardware description and hardware verification language used to model, design, simulate, test and implement electronic systems. SystemVerilog is based on Verilog and some extensions, and since 2008 Verilog is now part of the same IEEE standard. It is commonly used in the semiconductor and electronic design industry as an evolution of Verilog.

Scala (programming language) General-purpose programming language

Scala is a strong statically typed general-purpose programming language which supports both object-oriented programming and functional programming. Designed to be concise, many of Scala's design decisions are aimed to address criticisms of Java.

Distributed constraint optimization is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is minimized.

In computer programming, an enumerated type is a data type consisting of a set of named values called elements, members, enumeral, or enumerators of the type. The enumerator names are usually identifiers that behave as constants in the language. An enumerated type can be seen as a degenerate tagged union of unit type. A variable that has been declared as having an enumerated type can be assigned any of the enumerators as a value. In other words, an enumerated type has values that are different from each other, and that can be compared and assigned, but are not specified by the programmer as having any particular concrete representation in the computer's memory; compilers and interpreters can represent them arbitrarily.

Haxe is an open source high-level cross-platform programming language and compiler that can produce applications and source code, for many different computing platforms from one code-base. It is free and open-source software, released under the MIT License. The compiler, written in OCaml, is released under the GNU General Public License (GPL) version 2.

C++11 is a version of the ISO/IEC 14882 standard for the C++ programming language. C++11 replaced the prior version of the C++ standard, called C++03, and was later replaced by C++14. The name follows the tradition of naming language versions by the publication year of the specification, though it was formerly named C++0x because it was expected to be published before 2010.

B-Prolog was a high-performance implementation of the standard Prolog language with several extended features including matching clauses, action rules for event handling, finite-domain constraint solving, arrays and hash tables, declarative loops, and tabling. First released in 1994, B-Prolog is now a widely used CLP system. The constraint solver of B-Prolog was ranked top in two categories in the Second International Solvers Competition, and it also took the second place in P class in the second ASP solver competition and the second place overall in the third ASP solver competition. B-Prolog underpins the PRISM system, a logic-based probabilistic reasoning and learning system. B-Prolog is a commercial product, but it can be used for learning and non-profit research purposes free of charge. B-Prolog is not anymore actively developed, but it forms the basis for the Picat programming language.

In computer science, an array type is a data type that represents a collection of elements, each selected by one or more indices that can be computed at run time during program execution. Such a collection is usually called an array variable, array value, or simply array. By analogy with the mathematical concepts vector and matrix, array types with one and two indices are often called vector type and matrix type, respectively. More generally, a multidimensional array type can be called a tensor type.

In computer science, an interchangeability algorithm is a technique used to more efficiently solve constraint satisfaction problems (CSP). A CSP is a mathematical problem in which objects, represented by variables, are subject to constraints on the values of those variables; the goal in a CSP is to assign values to the variables that are consistent with the constraints. If two variables A and B in a CSP may be swapped for each other without changing the nature of the problem or its solutions, then A and B are interchangeable variables. Interchangeable variables represent a symmetry of the CSP and by exploiting that symmetry, the search space for solutions to a CSP problem may be reduced. For example, if solutions with A=1 and B=2 have been tried, then by interchange symmetry, solutions with B=1 and A=2 need not be investigated.

References

  1. ↑ "Ateji is closed" . Retrieved 2012-01-11.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.