Column generation for 1-D cutting stock problem

This is a example of solving one-dimensional cutting stock problem by column generation.

There are two class: MasterProblem and SlaveProblem obtained by Dantzig-Wolfe decomposition.

Master problem

Has a formulation like:

Slave problem:

Has a formulation like:

Instance

In the file instance.csv you can insert your items with structure like

400
280,2
279,4
277,2

where :

• first element on top of file is the max_length of items in stock, which variable in code is called lunghezza_max_asse
• the othere elements are a couple of lenght and demands of i-th item.

Options

debug

• True the solver run a little instance of defaul
• False the solver run a instance in instances.csv file

mostraRisultati

• True show optimum of master problem and new pattern at each iteration
• False show only optimum of cutting stock problem with number of iteration

Benchmarks

nItems	max_width (cm)	time (min)	iteration	optimum
4	110	0.2 s	7	47
23	50	1.4 s	37	23
38	150	2.9 s	61	31
177	400	1 m 7 s	396	236
230	400	1 m 8 s	556	382
313	500	6 m 20 s	1092	330
496	1000	18 m 2 s	2660	504