P$1$

Consider a cutting$-$stock problem where an unlimited supply of rolls of length $27$ is available. Three smaller

types of rolls of sizes $7,9$ and $12$ are required to be produced to satisfy a demand of $30,25$ and $15$ rolls,

respectively for each kind. Let us denote $(a,b,c)$ a cutting pattern where a rolls of size $7,b$ rolls of size $9$ and $c$

rolls of size $12$ are produced from a roll of length $27,$ such that $7a+9b+12c27.$

Write the associated master problem $($MP$)$ initialized with the cutting patterns $(3,0,0),(0,3,0),(0,0,2)$

Write the associated subproblem $($SP$),$ assuming that we denote ${}_7,{}_9,{}_{12}$ the dual variable associated

with the demand constraint associated with every small roll

Find the optimal solution to the linear relaxation of the MP by column generation. Solve the associated

linear or integer problems using the solver of your choice. For instance, you may consider the online solver

available at

Please write down the problems that you solve

at every iterationentre resolution process.