Ateji Newsletter - April 2009

Welcome to Ateji's newsletter. In this issue:

Gurobi solver link
Column generation
OptimJ graphical interface

OptimJ™ can now be used with the new Gurobi™ solver, to be announced prior to the INFORMS Practice meeting.

In the TECHNICAL CORNER, you will learn how OptimJ enables a concise, fast and reusable formulation of column generation algorithms.

The latest OptimJ release includes OptimJ GUI , a compiler-generated graphical user interface. The compiler does all the boring work for you, making it possible to develop gorgeous rapid prototypes in a matter of minutes. It also proves very useful for debugging and tuning complex models.

-- The Ateji Team

Gurobi

While modern solvers improve solving time, modern modeling languages improve time-to-market and lower development costs. OptimJ for Gurobi is the combination of choice when implementing optimization techniques in a Java environment.

Gurobi is a MIP solver designed from the ground up to exploit the power of modern multi-core processors. Version 1.0 of the Gurobi suite of optimization products will be released in April 2009, and an OptimJ solver link for Gurobi is available here.

PRODUCT NEWS

Graphical Interface

Debug and tune models in an intuitive and easy-to-use graphical interface.

Impress your clients with gorgeous rapid prototypes.

OptimJ GUI lets the compiler do all the boring work for you. Read the tutorial.

TECHNICAL CORNER

Column Generation

Being based on Java, OptimJ doesn't require an external scripting language.

Being object-oriented, OptimJ makes it possible to reuse algorithms.

See how to formulate a column-generation algorithm in OptimJ.

Learn more

Understand how language integration boosts productivity and quality (Pdf, 269Kb)
Learn about Object-Oriented Modeling (Pdf, 294Kb)
Try OptimJ hands-on with a free evaluation license
Browse the newsletter archive.

"I use OptimJ for teaching a master and an engineer course. Students become quickly proficient in the language and its IDE, and appreciate the ease of implementation and integration"
said Lucas Letocart, Associate professor at University Paris 13.

Academic licenses
OptimJ academic licenses are free for teaching at degree-granting institutions. Contact us for details.

GLPK
The latest OptimJ release includes a solver link for GLPK. The GNU Linear Programming Kit is an open-source package intended for solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems.

Roadef Challenge
At the award ceremony, Patrick Viry offered OptimJ licenses to the winners.
Watch the photos.

Blog
Learn everything about Ateji's ongoing and future projects.
Read the blog

Technical Corner

Column Generation

Column generation (Wikipedia entry) is an efficient algorithm for solving large linear programs. The main idea is that many linear programs are too large to consider all the variables explicitly. The column generation algorithm generates only the variables (the columns) that have the potential to improve the objective function.

The initial problem is split into two problems: the master problem and the sub-problem. The master problem is the original problem with only a subset of variables. The sub-problem is a new problem that generates new variables (new columns) considering the dual values (prices) of constraints in the master problem.

Highlights

Column generation in OptimJ is

efficient: while most modeling languages reset the solver after each iteration, OptimJ preserves the current solver state
concise: OptimJ handles the creation of new columns automatically
reusable: object-oriented modeling makes it possible to abstract away the notion of pattern, thus enabling the reuse of algorithms on various different problems

Formulation in OptimJ

The code below is a generic example of a column generation algorithm. It is based on a notion of pattern, specific to each problem.

// initialize the master model and perform an initial solve
MasterProblem master = new MasterProblem(masterParameters);
master.extract();
master.solve();

// loop while progress is being made
while(master.isProgressMade()){

// subProblem generates a new pattern
SubProblem subProblem = new SubProblem(master.getDuals());
Pattern newPattern = subProblem.getNewPattern();
// add the new pattern to the master problem
master.addPattern(newPattern);
// incrementally re-solve the master problem
master.extract();
master.solve();

}

Given this generic formulation, the responsability of the problem expert is to specify the problem decomposition, namely to define the notion of pattern to be used. Concretely, this amounts to implementing the type Pattern and the methods isProgressMade(), getDuals(), getNewPattern() and addPattern().

Running example: the cutting stock problem

The cutting stock problem (Wikipedia entry) is the archetypal application of column generation algorithms. Given a set of orders from customers, the goal is to cut paper rolls so that the waste (amount of left-overs) is minimized.

Here, a pattern specifies one possible way of cutting rolls (how many cuts of a given size). The cost of a pattern is related to the amount of leftover material.

class Pattern
{
int[Order] fill; // order o appears fill[o] times in the pattern
int cost;
}

In the master model, patterns is the current set of patterns to be considered, and use is a collection of decision variables representing how many instances of each pattern should be used.

Set<Pattern> patterns;
Map<Pattern, var double> use; // 'use.get(p)' is the number of times p is used.

The master model states that the total cost of patterns should be minimized, constrained to the fact that all orders are satisfied.

minimize sum{Pattern p : patterns}{p.cost*use.get(p)};

constraints {

forall (Order o : orders) {

ctFill[o]: sum{Pattern p : patterns}{p.fill[o]*use.get(p)} >= o.quantity;

}

Dynamically adding new patterns and decision variables

The fields patterns and use defined above are dynamic data structures that can be expanded at run time. Adding a new pattern consists in adding a new entry to the set patterns, and mapping a new decision variable to the new pattern.

public void addPattern(Pattern p) {

patterns.add(p);
use.put(p, new var double(lowerBound, upperBound));

}

Note the use of the new keyword to create a new decision variable of the given type.

When the extract() method is called for the first time, it creates in the solver enough decision variables for all var fields defined in the model. Then, each time extract() is called again, it incrementally adds only the new decision variables that have been created in the model since its last call, without resetting the solver .

Technical note:

extract() is incremental only for linear solvers
modifying existing coefficients between subsequent calls to extract() is not taken into account
similarly, new constraints and SOS sets are not taken into account

Going back to the generic column generation algorithm given above, notice how extract() is called repeatedly in the main loop, taking into account the new patterns and variables introduced by addPattern().

The full code for this cutting stock example is available in the OptimJ samples library, that you can obtain by requesting an evaluation license.

The sub-problem

The role the sub-problem is to generate new patterns. There are many possible design options, such as:

Model the sub-problem with OptimJ as a linear programming problem.
Use constraint programming techniques, either with OptimJ for ILOG CPLEX™ or using a specific Java package.
Generate patterns using dynamic programming techniques.
Use hybrid techniques such as tabu search.
Or develop your own algorithm in Java or OptimJ, in order to take into account your intimate knowledge of the problem at hand.

Please refer to the literature for details.

Forums

Share your comments about this newsletter in the forums.