E-mail this page
Our Webinars
Description
This project illustrates AIMMS' capabilities to implement an algorithmic approach to find an optimal solution to a problem by repeatedly solving two optimization programs until no further improvement is possible anymore.
The problem tackled in this demo is a cutting stock problem: how to cut long rolls of material (referred to as raws) into smaller rolls of a prescribed size (referred to as finals), given a demand for each of the finals.
The straightforward way to tackle the problem would be to generate all possible patterns of cutting finals from raws, and generate a MIP model to find the optimal pattern choices. The problem here, however, is that the number of possible patterns grows explosively, making it virtually impossible to solve the MIP for larger numbers of finals.
However, parts of the branch-and-bound tree can be cut off when using the AIMMS heuristic callback in the GMP library. In this example the LILE heuristic is used to provide CPLEX with integer solutions, after which large parts of the branch-and-bound tree can be cut off. The possible cutting patterns are generated recursively in an external procedure using the AIMMS API.
The LILE heuristic approach can be of advantage when the model needs to be solved over and over again using the same set of finals, but with different demand scenarios. When the set of finals is large or different for each solve, the below described alternative approach might work better, because not all patterns need to be generated.
An alternative way to tackle the problem is to start with a small number of patterns, and generate new patterns on the basis of shadow prices returned by the solver. In this way, only a subset of useful patterns will be generated for the final MIP model. In practice, this will lead to very good solutions, although optimality is not necessarily guaranteed. The solution is optimal, however, if the gap between the integer and linear objective function value is less than one.
The pattern generation approach is implemented using conventional math programs that require regeneration every time and using generated math programs (GMPs) that allow for direct updates on the generated problem.
The demo page illustrates the solution both in tabular and graphical (not when all patterns are generated) form given the raw size, as well as the prescribed finals and their demands.
Keywords
Composite table, Scalar object, shadow price, External procedure, GMP, AIMMS callback, Gantt chart
Industries
Model Types
(Mixed) Integer Programming, Advanced Algorithms
References
Chapter 20 - A Cutting Stock Problem in the Optimization Modeling Guide
Download AIMMS Example
You can download an AIMMS example dealing with this problem via the link below, and run it after installing the AIMMS software. If you don't have an AIMMS license yet, you can download a free license of AIMMS.
ftp://ftp.aimms.com/pub/Download/Examples/Cutting Stock.aimmspack
Please make sure to save this file including the .aimmspack extension so that it can be opened by AIMMS.
This example application is a simplification of reality. Please do not hesitate to contact us to discuss how AIMMS enables you to build a complete optimization application that captures the full complexity of your problem.
Screenshot AIMMS Example
