Hi Niitan, After thinking about your problem some more, here are a few questions --
-- do you need to solve the problem to optimality or is a feasible solution good enough? For the data given in your second problem a feasible solution is found in less than a second. There's also feasible solution to your problem using 13 pieces of raw material rather than 14. -- Can your largest problems be decomposed into smaller ones? You may have 200 products and 500 stock pieces, but is the infrastructure in place to execute a production plan of that complexity? If that's the problem you need to solve then you will need to look into methods specifically tailored to the stock cutting problem. On the other hand, perhaps the infrastructure suggests a decomposed into subtasks such as a single order, single work shift, or single work area. Also, embedded in the MathProg model is a 'Big M' type constraint. It's not needed to determine feasibility. If you do keep it in, the parameter bigM needs to be larger than your largest stock piece. I'll contact you privately with an updated model reflecting the necessary changes. Jeff On Sun, Mar 10, 2013 at 9:17 AM, Jeffrey Kantor <[email protected]> wrote: > Niitin, > > The simple MathProg model I developed for your small problem will never > work for your full scale application. Producing 200 product pieces from > 500 stock pieces would correspond to 200 x 500 = 10,000 binary variables. > Given the large number of symmetries in the solution to the problem, that's > not a feasible approach. > > Column generation is a standard approach to these problems. Rather than > directly assign product pieces to stock pieces, in column generation you > consider a set of cutting patterns. Each cutting pattern breaks a stock > piece into known product pieces. The optimization problem is to then > determine an optimal number of times to use each pattern. Each pattern > corresponds to a column in an integer LP. The trick is to start with a > base set of patterns then generate new patterns on the fly (hence 'column > generation') to solve your specific problem. > > Unfortunately, MathProg doesn't provide a means to add columns on the fly. > Therefore you'll need to look into use of the glpk api. It's not as bad > as it sounds, and you can into the cspsol for a head start. Also google > 'cutting stock column generation' for some excellent resources. > > Jeff > > > > > On Sun, Mar 10, 2013 at 5:34 AM, Nitin Patel <[email protected]>wrote: > >> Thank you Mr Jeff**** >> >> ** ** >> >> Thanks for quick replay. Actual problem has more stocks (10 to 15 >> different lengths with 500 quantities) and demands (10 to 15 different >> lengths with 200 quantities).**** >> >> I am new to GLPK-Mathprog . It will take some time to learn things. I >> know VB / Excel VBA.**** >> >> ** ** >> >> I do not understand matter you have mention in second paragraph. It is my >> fault as I am new to this subject. (OR & GLPK)**** >> >> ** ** >> >> AS per you “Larger problems would require more care. In particular, stock >> cutting is often solved using a column generation.” Can you provide some >> more information for the same?**** >> >> For below small data it took 413 Seconds. Can we reduce time using >> “column generation”?**** >> >> ** ** >> >> ** ** >> >> param : PRODUCTS : pLength demand :=**** >> >> '110m' 110 1**** >> >> '107m' 107 6**** >> >> '105m' 105 4**** >> >> '103m' 103 3**** >> >> '100m' 100 2**** >> >> '96m' 96 4**** >> >> '94m' 94 1**** >> >> '91m' 91 3**** >> >> '86m' 86 3**** >> >> '78m' 78 2**** >> >> '76m' 76 2**** >> >> '69m' 69 5;**** >> >> ** ** >> >> **** >> >> param : RAW : rLength avail :=**** >> >> '280m' 280 14;**** >> >> ** ** >> >> ** ** >> >> Thanks**** >> >> ** ** >> >> Niitn Patel**** >> >> ** ** >> >> ** ** >> >> ** ** >> >> ** ** >> >> *From:* Jeffrey Kantor [mailto:[email protected]] >> *Sent:* Sunday, March 10, 2013 1:57 AM >> *To:* [email protected] >> *Cc:* GLPK >> *Subject:* Re: [Help-glpk] Stock Cutting problem**** >> >> ** ** >> >> This is a relatively small scale problem so it can be solved as the >> assignment of product pieces to stock pieces. Appended below is a MathProg >> solution which you can cut and paste into http://MathP.org or >> http://www.nd.edu/~jeff/mathprog/mathprog.html for testing. This >> solution uses indexed sets to enumerate the individual product and stock >> pieces of materials.**** >> >> ** ** >> >> For the given data is no waste piece could be less than 1 meter, so it >> isn't necessary to consider the issue of minimizing small scrap. That could >> be handled with an additional binary variable for each piece of raw >> material, but wasn't necessary given the problem data. Another aspect is >> that minimizing the number of pieces cut leaves a lot of solution >> symmetries. The computation is faster by introducing weights, which has the >> nice side effect of producing a 'no-waste' solution for the given problem >> data.**** >> >> ** ** >> >> Larger problems would require more care. In particular, stock cutting is >> often solved using a column generation.**** >> >> ** ** >> >> Jeff**** >> >> ** ** >> >> ** ** >> >> # Stock Cutting Problem**** >> >> ** ** >> >> # Product catalog**** >> >> set PRODUCTS;**** >> >> param pLength{PRODUCTS};**** >> >> param demand{PRODUCTS};**** >> >> ** ** >> >> # Raw Materials**** >> >> set RAW;**** >> >> param rLength{RAW};**** >> >> param avail{RAW};**** >> >> ** ** >> >> # Set of production pieces indexed by products**** >> >> set Q{p in PRODUCTS} := 1..demand[p] ;**** >> >> ** ** >> >> # Set of stock pieces indexed by raw materials**** >> >> set S{r in RAW} := 1..avail[r];**** >> >> ** ** >> >> # Cutting assignments**** >> >> var y{p in PRODUCTS, q in Q[p], r in RAW, s in S[r]} binary;**** >> >> ** ** >> >> # Indicator if an item of raw material is used**** >> >> var u{r in RAW, s in S[r]} binary;**** >> >> ** ** >> >> # Length of waste from each piece of raw material**** >> >> var w{r in RAW, s in S[r]} >= 0;**** >> >> ** ** >> >> # Cut each product piece only once**** >> >> s.t. A{p in PRODUCTS, q in Q[p]} : sum{r in RAW, s in S[r]} y[p,q,r,s] = >> 1;**** >> >> ** ** >> >> # For each product, cut enough pieces to exactly meet demand**** >> >> s.t. B{p in PRODUCTS} : sum{q in Q[p], r in RAW, s in S[r]} y[p,q,r,s] = >> demand[p];**** >> >> ** ** >> >> # For each piece of raw material, do not exceed length**** >> >> s.t. C{r in RAW, s in S[r]} : **** >> >> sum{p in PRODUCTS, q in Q[p]} pLength[p]*y[p,q,r,s] + w[r,s] = >> rLength[r];**** >> >> **** >> >> # Determine if a piece of raw material is used.**** >> >> s.t. D{r in RAW, s in S[r]} : 15*u[r,s] >= sum{p in PRODUCTS, q in Q[p]} >> y[p,q,r,s];**** >> >> ** ** >> >> # Minimize number of bars, with weights to favoring long pieces**** >> >> minimize NumberOfBars: sum{r in RAW, s in S[r]} rLength[r]*u[r,s];**** >> >> ** ** >> >> solve;**** >> >> ** ** >> >> printf "Cutting Plan\n";**** >> >> for {r in RAW} : {**** >> >> printf " Raw Material Type %s \n", r;**** >> >> for {s in S[r]} : {**** >> >> printf " Piece %g : Remainder = %2g : Cut products ", s, >> w[r,s];**** >> >> for {p in PRODUCTS} : {**** >> >> for {q in Q[p] : y[p,q,r,s]} : {**** >> >> printf "%s ", p;**** >> >> }**** >> >> }**** >> >> printf "\n";**** >> >> }**** >> >> printf "\n";**** >> >> }**** >> >> ** ** >> >> printf "Production Plan\n";**** >> >> for {p in PRODUCTS} : {**** >> >> printf " Product %s \n", p;**** >> >> for {q in Q[p]} : {**** >> >> printf " Piece %g : Cut from stock ", q;**** >> >> for {r in RAW} : {**** >> >> for {s in S[r] : y[p,q,r,s]} : {**** >> >> printf "%s ", r;**** >> >> }**** >> >> }**** >> >> printf "\n";**** >> >> }**** >> >> printf "\n";**** >> >> }**** >> >> ** ** >> >> data;**** >> >> ** ** >> >> param : PRODUCTS : pLength demand :=**** >> >> '7m' 7 3**** >> >> '6m' 6 2**** >> >> '4m' 4 6**** >> >> '3m' 3 1 ;**** >> >> **** >> >> param : RAW : rLength avail :=**** >> >> '15m' 15 3**** >> >> '10m' 10 3;**** >> >> **** >> >> end;**** >> >> ** ** >> >> ** ** >> >> On Sat, Mar 9, 2013 at 12:07 PM, Nitin Patel <[email protected]> >> wrote:**** >> >> How to solve stock cutting problem with multiple length stock available >> and demand is under.**** >> >> **** >> >> Stock length available---**** >> >> 15 m – 3 Numbers**** >> >> 10 m – 3 Numbers**** >> >> **** >> >> Demand---**** >> >> 7m – 3 Numbers**** >> >> 6m – 2 Numbers**** >> >> 4m – 6 Numbers**** >> >> 3m – 1 Number**** >> >> **** >> >> How to solve it so that minimize wastage**** >> >> **** >> >> We should utilize minimum number of stocks**** >> >> If unused length is more than 0.5 m then we can utilize it for next >> cutting schedule and it is not wastage.**** >> >> **** >> >> **** >> >> Thanks**** >> >> **** >> >> Nitin patel**** >> >> **** >> >> **** >> >> **** >> >> >> _______________________________________________ >> Help-glpk mailing list >> [email protected] >> https://lists.gnu.org/mailman/listinfo/help-glpk**** >> >> ** ** >> > >
_______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
