cspsol : Cutting stock problem solver, Version 1.0
Copyright (C) 2008, 2009, 2010, Vijay C. Patil Email : vijay.patil@gmail.com
cspsol is a free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License.
See the file COPYING for the GNU General Public License, version 3.
See the file INSTALL for compilation and installation instructions.
This README describes some details of program 'cspsol'. Program 'cspsol' solves cutting stock problems and also bin packing problems.
"Imagine that you work in a paper mill, and you are a manager in the paper cutting division. You have a number of rolls of paper of fixed width waiting to be cut, yet different manufacturers want different numbers of rolls of various-sized widths. How are you going to cut the rolls so that the least amount of left-overs are wasted? This turns out to be an optimization problem, or more specifically, an integer linear programming problem."
Important node: Right now program minimizes number of rolls used. In other words, objective function is to minimize total number of rolls required to satisfy the demand. Other possible objective could be to minimize total amount of left over in each pattern.
Program 'cspsol' uses column generation (CG) technique and branch & bound (BB) algorithm. Best pattern/column is generated by solving sub-problem (which is integer knapsack problem). After solving the node lp using CG, if solution contains fractional variables then simple branching is used to create child nodes while becomes part of BB tree. Program stops when tree is exhausted/empty.
Following section describes usage of the program. Usage: cspsol [options...] --data filename
Where filename contains orders data in following format. max_pattern_width order_width_1 demand_1 order_width_2 demand_2 order_width_n demand_n
All order widths must be <= max_pattern_width. All demands, order widths and max_pattern_width must be INTEGERs.