On Sun, Mar 30, 2008 at 11:36 PM, vijay patil <[EMAIL PROTECTED]> wrote: > > On Sat, Mar 29, 2008 at 3:29 PM, vijay patil <[EMAIL PROTECTED]> wrote: > > Hi, > > > > I wrote a program to solve cutting stock problem. Program is written > > in C++ and uses GLPK C API. Customized branch & bound (BB) algorithm > > is used. Each node of BB tree is a LP. Each node LP is solved using > > column generation (CG). Very simple branching on fractional variable > > is used to obtain integer solution. BB tree is traversed using breadth > > first search (BFS) strategy. > > > > Hopefully program will be useful to anyone interested in learning GLPK > > C API and understand column generation technique. In case you want to > > have a look at the source code, following web-page has more details, > > including source code: > > > > http://code.google.com/p/cspsol/ > > > > I have not tested the program extensively. It is likely that program > > has some flaw or incorrect use of GLPK C API. Your feedback/comments > > are welcome. > > > > Thanks > > -- > > Vijay Patil > > > > Just released version 0.2. > > http://code.google.com/p/cspsol/downloads/list > > Added some command line options. Added support for two search > strategies (DFS and BFS). > > [EMAIL PROTECTED]:~/projects/cspsol/src$ cspsol --help > > Usage: cspsol [options...] --data filename > > Where filename contains orders data in following format. > maximum_pattern_width > order_width_1 demand_1 > order_width_2 demand_2 > order_width_n demand_n > > All demand quantities are <= maximum_pattern_width. > > Options: > --dfs Process branch and bound tree in depth first manner. > --bfs Process branch and bound tree in breadth first manner. > -h, --help Display this help information and exit. > > > -- > Vijay Patil >
Released version 0.3. http://code.google.com/p/cspsol/downloads/list 1. Now CG is done only at the root node of BB tree. CG at all nodes of BB tree requires some more thought. 2. Removed slack variables, instead added trivial patterns to the master problem. (as Andrew suggested.) 3. Now order width can be integer/float. 4. Improved formatting etc. 5. Moved files INSTALL and README from /src to parent dir. 6. Updated homepage http://code.google.com/p/cspsol/ Thanks -- Vijay Patil _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
