Skip to content

paolosantarsiero/ColumnGeneration

Repository files navigation

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

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published