| 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
|
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.
MasterProblem master = new MasterProblem(masterParameters);
master.extract();
master.solve();
while(master.isProgressMade()){
SubProblem subProblem = new SubProblem(master.getDuals());
Pattern newPattern = subProblem.getNewPattern();
master.addPattern(newPattern);
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;
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 patterns; Map var double> use; 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.
|
