Of course, I mean the formulation like this:
https://en.wikipedia.org/wiki/Cutting_stock_problem#Formulation_and_solution_approaches
When teaching OR, I use this kind of the ILP problem as a simple example where LP must be "supplemented" with integer variables. However, my students expect practical applications to the models I teach them, not only their formal mathematical correctness. And what can I say to them? Well, you must know all the cutting patterns before you optimize. It's easy to find those patterns at least in the 1D-CSP case. Even if we are restricted to 1D-CSP only, it is still an important application. But there may be hundreds or thousands of cutting patterns and, what follows, integer variables even in a possibly small and simply problem. So, the whole thing often becomes useless.
My question is really the following:
Is there any case in which the considered ILP form of CSP (restrict it to 1D-CSP) is better in some sense (time of optimization, but also e.g. availability of free software) to compare with other 1D-CSP models (those with "guaranteed" optimal solutions, not like First Fit Decreasing for example)? Or, more practically, does anybody know any real-world case of a company in which the ILP form of CSP is actually used in production planning?
I don't want to teach something which is nothing but a practically useless mathematical concept, that's all.
At first, I teach many MP-models by Linus textbook and demo-version of WB! and LINGO. Recently, I write a textbook with free version of WB! and LINGO.
This "academic" problem is perfect for educational purposes, as you can use it as an example of the column generation principle (extending Dantzig-Wolfe to integer programs). It's an age-old story - Dirickx-Jennergren's book from - I think - 1979 is full of things like this. Very good!
Michael, I agree with your answer but but my teaching targets are somewhat different. I teach management students and I focus on creating possibly realistic mathematical models, not details of algorithms. For solving specific problems, I use some "general-purpose" software like Excel+Solver or lp_solve. I want my student to teach them doing something like this - a diet/blending problem: https://www.researchgate.net/publication/238370821_UNEForm_a_powerful_feed_formulation_spreadsheet_suitable_for_teaching_or_on-farm_formulation (full text: http://www.sciencedirect.com/science/article/pii/S0377840101002103).
I'd like to make similar models for 1D-CSP as ILP which might also be of practical use. More precisely, I'd like to show that creating and solving such a model by using "general-purpose" optimization software may be in some REALISTIC cases (preferably - FROM a REAL COMPANY) better then using a dedicated 1D-CSP software. By "better" I mean "entering the input data and obtaining an optimal solution in reasonable time" . Moreover, the convenience of using the software which solve 1D-CSP as ILP may be worse than that of the dedicated software, but still worth considering because it's possible to avoid paying for the licence for the dedicated software.
Article UNEForm: a powerful feed formulation spreadsheet suitable fo...
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling