| Ateji Newsletter - November 2008 |
|
Welcome to Ateji's bimonthly newsletter.
OptimJ™ is becoming the language of choice for decomposing complex problems. In the TECHNICAL CORNER, you will learn how sparse data can be modeled with associative arrays and tuples. The next OptimJ release will include a compiler-generated graphical user interface. It will help you to create prototypes in no time or to debug your model. We look forward to meeting you in our new forums. -- The Ateji Team Close the gap between optimization engines & Java™ applications
"It's been a positive experience for Siemens Corporate Research
dealing with Ateji and using OptimJ." said Andrey Torzhkov, Research Scientist.
"We've succesfully applied OptimJ to improve an existing software application developed in one of our past numerical optimization projects. Now, we're going to deploy OptimJ capabilities for our ongoing Java-based projects to close a gap between optimization engines & modeling applications".
|
Join the OptimJ community
Ateji is pleased to announce the launch of its forums. This is the place to ask technical questions, share tips, meet the OptimJ team, and discuss new features. ROADEF'09 Meet us in Nancy at the annual meeting of the French OR Society. Academic licenses OptimJ academic licenses are free for teaching at degree-granting institutions. Contact us. Internships Ateji is always welcoming interns (master level). Topics include language technology, Java development and marketing. International candidates welcome. Contact us. |
| News and Events |
Graphical Interface
The OptimJ GUI (Graphical User Interface) is now available as a beta version for technology preview. Main features are- visual prototyping
- visual debugging
- interactive parameter settings
- requires exactly one line of code
Contact us at info@ateji.com to try it hands-on.
Just one line
This single line of code creates a default GUI and binds it to an OptimJ model :
LpSolve.bind(myModel);
In constrast, using a visualization API may require 100's of lines of code for the same result. Here, the bulk of the work is done instead by the OptimJ compiler at compile time.
Overview
The top part of the GUI window is a "control panel" that presents an overview of the model and the solver state:- 'Control' buttons allow one to pause or step the solver
- 'Solver activity' displays the current objective value, the number of simplex and B&B iterations, and the running time of the solver
- 'Model size' summarizes the number of variables and constraints before and after presolve
In the bottom part of the window, the first three tabs relate to the solver state (in this example, lp_solve):
- Run
- Parameters
- Matrix Data
The last tab displays the model data as defined in the OptimJ code:
- Model Data
Debugging and tuning a model
The 'Run' tab displays in real-time:- the current objective value and its evolution
- solver events
- the log messages of the solver
Visualizing the evolution of the objective function is helpful in understanding where solving time is spent. As an example, on a specific model, if the branch-and-bound algorithm does not show any progress after a first solution, this may be a hint that this first solution is a good candidate and that there is no need waiting for a provably optimal solution.
The 'Parameters' tab provides an interactive way to experiment with various settings, such as:
- presolve mode
- scaling options
- branch and bound strategy
For a given model, a good choice of settings can have a tremendous impact on performance.
- the coefficients of the matrix
- the current values and duals of the constraints
- the current values and duals of the variables
Rapid prototypingThe 'Model Data' tab displays the model structure in terms of the data structures defined in the OptimJ source. It can display both decision variables (the unknown of the model) and programming variables (the parameters of the model).This proves very useful for rapid prototyping. Write a first OptimJ model, bind it to the GUI, and you immediately have a visual prototype that you can present to all the project's stakeholders. A default visualization is generated by the OptimJ compiler. It can easily be parameterized in arbitrary ways, such as coloring cells or using different graphical components. In the first screenshot on the right, coloring the cells where an employee is assigned to a shift required exactly three additionally lines of code. The default display presents data in a two-dimensional array. Other graphical components such as pie or bar charts are available and the default display can be overridden with few lines of code. The single lineThe default OptimJ GUI is created with this single line in your program :
LpSolve.bind(myModel);
Your model does not change, and this single line gives you access to the OptimJ GUI. Additional code can be written in a simple manner to improve the default rendering, such as adding colors or using different graphical components. Beta-test the InterfaceThe first version of the OptimJ GUI will only be available with LpSolve, but versions for other solvers will soon be added.While waiting for this new release, you can beta-test the interface : just contact us at info@ateji.com . |
|
| Technical Corner |
Sparse Data
In this technical corner, we will see how you can model sparse data with OptimJ.Often, when working with large models, the data for the model tends not to be dense. Sparse data typically involves multiple dimensions, but does not necessarily contain values for every combination of the indices.
Many storage formats (or data structures) have been proposed to represent sparse matrices. Most of them have a Java API and can be used with OptimJ.
We will focus on solutions using associative arrays and tuples. This allows to easily skip certain combinations of indices, that are not valid, by omitting them in the array.
Associative arrays
Associative arrays allow to store data indexed by an arbitrary collection. They behave exactly like Java arrays, but indices range over any given collection rather than over integers from 0 to n. The indices must be given at array creation time and can never change.Associative arrays are convenient for expressing optimization models in a concise mathematical-like fashion.
Problem description
Consider the declaration:
Set<Warehouse> warehouses;
Set<Customer> customers;
int[Customer][Warehouse] transp[warehouses][customers];
Set<Customer> customers;
int[Customer][Warehouse] transp[warehouses][customers];
transp is a two-dimensional associative array. It may represent the units shipped from a wharehouse to a customer. But a wharehouse delivers only to a subset of customers. Array transp may be sparse.
We will present two ways to exploit the sparsity: tuples and non rectangular associative arrays.
Formulation in OptimJ with a set of tuples
OptimJ provides a notion of tuples similar to the one used in mathematics. A tuple type is written by enumerating the types of its components between two tuple markers.
Set<(:Warehouse, Customer:)> routes = ...;
int[(:Warehouse, Customer:)] transp[routes]
int[(:Warehouse, Customer:)] transp[routes]
routes is a set of tuples and contains only the revelant pairs (warehouse, customer). It is used to defined the indices of associative array transp.
The sum of all units shipped is calculated as follow:
sum{ transp[route] | (:Warehouse,Customer:) route : routes };
Instead of a tuple type, you can use your own class Route.
public class Route {
private final Warehouse w;
private final Customer c;
public Route(Warehouse w, Customer c) {this.c=c; this.w=w;}
...
}
private final Warehouse w;
private final Customer c;
public Route(Warehouse w, Customer c) {this.c=c; this.w=w;}
...
}
The previous example becomes:
Set<Route> routes = ...;
int[Route] transp[routes]
sum{ transp[route] | Route route : routes };
int[Route] transp[routes]
sum{ transp[route] | Route route : routes };
Formulation in OptimJ with non rectangular associative arrays
Another solution is to use a two-dimensional non-rectangular arrays:
Set<Warehouse> warehouses;
Set<Customer> customers(Warehouse w) { return ...;}
int[Customer][Warehouse]
transp[Warehouse w : warehouses][customers(w)];
Set<Customer> customers(Warehouse w) { return ...;}
int[Customer][Warehouse]
transp[Warehouse w : warehouses][customers(w)];
This declaration specifies an associative array transp. For a given Warehouse w, indices of transp[w] (computed by method customers) are a subset of set of all customers. transp is said to be non rectangular since two different warehouses may be associated to different sets of customers.
The sum of units shipped from a given wharehouse w is calculated as follow:
sum{ transp[w][c] | Customer c : transp[w] };