Setiap variabel dalam suatu masalah program linear bersesuaian dengan kolom dalam matriks kendalanya sehingga masalah program linear yang melibatkan variabel yang sangat banyak identik dengan melibatkan jumlah kolom yang sangat besar dalam matriks kendalanya. Salah satu metode yang cukup efisien untuk menyelesaikan masalah program linear, khususnya masalah pemrograman linear bilangan bulat, tanpa harus mengetahui secara eksplisit semua kolom dalam matriks kendalanya adalah metode column generation [6]. Ide dari metode column generation adalah cukup dengan menggunakan subhimpunan dari himpunan kolom yang besar dalam menyelesaikan masalah, kemudian kolom baru akan ditambahkan ke dalam subhimpunan tersebut hanya saat diperlukan, yaitu ketika variabel yang bersesuaian dengan kolom tersebut berpotensi mengoptimalkan fungsi tujuan. Salah satu masalah program linear yang melibatkan jumlah kolom yang sangat besar dalam matriks kendalanya adalah cutting stock problem. Cutting stock problem merupakan masalah pencarian pola-pola pemotongan yang sesuai pada bahan mentah, dimana terdapat permintaan dengan panjang berbeda-beda sedemikian sehingga banyaknya bahan mentah yang digunakan minimum. Pada cutting stock problem, setiap kolom