GMSCutstock.cs
1// --------------------------------------------------------------- -*- C# -*-
2// File: Cutstock.cs
3// --------------------------------------------------------------------------
4using System;
5using System.IO;
6using GAMS;
7using System.Collections.Generic;
8
9namespace Cutstock
10{
20 {
21 static void Main(string[] args)
22 {
24 if (Environment.GetCommandLineArgs().Length > 1)
25 ws = new GAMSWorkspace(systemDirectory: Environment.GetCommandLineArgs()[1]);
26 else
27 ws = new GAMSWorkspace();
28 // instantiate GAMSOptions and define parameters
29 GAMSOptions opt = ws.AddOptions();
30 GAMSDatabase cutstockData = ws.AddDatabase("csdata");
31 opt.AllModelTypes = "Cplex";
32 opt.OptCR = 0.0; // Solve to optimality
33 int maxpattern = 35;
34 opt.Defines.Add("pmax", maxpattern.ToString());
35 opt.Defines.Add("solveMasterAs", "RMIP");
36
37 // define input data
38 Dictionary<string, double> d = new Dictionary<string, double>() { { "i1", 97 }, { "i2", 610 }, { "i3", 395 }, { "i4", 211 } };
39 Dictionary<string, double> w = new Dictionary<string, double>() { { "i1", 47 }, { "i2", 36 }, { "i3", 31 }, { "i4", 14 } };
40 int r = 100; // raw width
41
42 // cutstockData.AddSet("i", 1, "widths").AddRecords(d.Keys);
43 // cutstockData.AddParameter("d", 1, "demand").AddRecords(d);
44 // cutstockData.AddParameter("w", 1, "width").AddRecords(w);
45 // cutstockData.AddParameter("r", 0, "raw width").AddRecord().Value = r;
46
47 GAMSSet widths = cutstockData.AddSet("i", 1, "widths");
48 GAMSParameter rawWidth = cutstockData.AddParameter("r", 0, "raw width");
49 GAMSParameter demand = cutstockData.AddParameter("d", 1, "demand");
50 GAMSParameter width = cutstockData.AddParameter("w", 1, "width");
51
52 rawWidth.AddRecord().Value = r;
53 foreach (string i in d.Keys)
54 widths.AddRecord(i);
55 foreach (KeyValuePair<string, double> t in d)
56 demand.AddRecord(t.Key).Value = t.Value;
57 foreach (KeyValuePair<string, double> t in w)
58 width.AddRecord(t.Key).Value = t.Value;
59
60 // create initial checkpoint
61 GAMSCheckpoint masterCP = ws.AddCheckpoint();
62 GAMSJob masterInitJob = ws.AddJobFromString(GetMasterModel());
63 masterInitJob.Run(opt, masterCP, cutstockData);
64
65 GAMSJob masterJob = ws.AddJobFromString("execute_load 'csdata', aip, pp; solve master min z using %solveMasterAs%;", masterCP);
66
67 GAMSSet pattern = cutstockData.AddSet("pp", 1, "pattern index");
68 GAMSParameter patternData = cutstockData.AddParameter("aip", 2, "pattern data");
69
70 // Initial pattern: pattern i hold width i
71 int patternCount = 0;
72 foreach(KeyValuePair<string,double> t in w)
73 {
74 patternData.AddRecord(t.Key, pattern.AddRecord((++patternCount).ToString()).Key(0)).Value = (int)(r / t.Value);
75 }
76
77 // create model instance for sub job
78 GAMSCheckpoint subCP = ws.AddCheckpoint();
79 ws.AddJobFromString(GetSubModel()).Run(opt, subCP, cutstockData);
80 GAMSModelInstance subMI = subCP.AddModelInstance();
81
82 // define modifier demdual
83 GAMSParameter demandDual = subMI.SyncDB.AddParameter("demdual", 1, "dual of demand from master");
84 subMI.Instantiate("pricing min z using mip", opt, new GAMSModifier(demandDual));
85
86 // find new pattern
87 bool patternAdded = true;
88 do
89 {
90 masterJob.Run(opt, masterCP, cutstockData);
91 // Copy duals into gmssubMI.SyncDB DB
92 demandDual.Clear();
93 foreach (GAMSEquationRecord dem in masterJob.OutDB.GetEquation("demand"))
94 demandDual.AddRecord(dem.Key(0)).Value = dem.Marginal;
95
96 subMI.Solve();
97 if (subMI.SyncDB.GetVariable("z").FindRecord().Level < -0.00001)
98 {
99 if (patternCount == maxpattern)
100 {
101 Console.Out.WriteLine("Out of pattern. Increase maxpattern (currently {0}).", maxpattern);
102 patternAdded = false;
103 }
104 else
105 {
106 Console.WriteLine("New patter! Value: " + subMI.SyncDB.GetVariable("z").FindRecord().Level);
107 GAMSSetRecord s = pattern.AddRecord((++patternCount).ToString());
108 foreach (GAMSVariableRecord y in subMI.SyncDB.GetVariable("y"))
109 {
110 if (y.Level > 0.5)
111 {
112 patternData.AddRecord(y.Key(0), s.Key(0)).Value = Math.Round(y.Level);
113 }
114 }
115 }
116 }
117 else patternAdded = false;
118 } while (patternAdded);
119
120 // solve final MIP
121 opt.Defines["solveMasterAs"] = "MIP";
122 masterJob.Run(opt, cutstockData);
123 Console.WriteLine("Optimal Solution: {0}", masterJob.OutDB.GetVariable("z").FindRecord().Level);
124 foreach (GAMSVariableRecord xp in masterJob.OutDB.GetVariable("xp"))
125 {
126 if (xp.Level > 0.5)
127 {
128 Console.Out.Write(" pattern {0} {1} times: ", xp.Key(0), xp.Level);
129 GAMSParameterRecord aip = masterJob.OutDB.GetParameter("aip").FirstRecord(" ", xp.Key(0));
130 do
131 {
132 Console.Out.Write(" {0}: {1}", aip.Key(0), aip.Value);
133 } while (aip.MoveNext());
134 Console.Out.WriteLine();
135 }
136 }
137 // clean up of unmanaged ressources
138 cutstockData.Dispose();
139 subMI.Dispose();
140 opt.Dispose();
141 }
142
143 static String GetMasterModel()
144 {
145 String model = @"
146$Title Cutting Stock - Master problem
147
148Set i widths
149Parameter
150 w(i) width
151 d(i) demand
152Scalar
153 r raw width;
154$gdxin csdata
155$load i w d r
156
157$if not set pmax $set pmax 1000
158Set p possible patterns /1*%pmax%/
159 pp(p) dynamic subset of p
160Parameter
161 aip(i,p) number of width i in pattern growing in p;
162
163* Master model
164Variable xp(p) patterns used
165 z objective variable
166Integer variable xp; xp.up(p) = sum(i, d(i));
167
168Equation numpat number of patterns used
169 demand(i) meet demand;
170
171numpat.. z =e= sum(pp, xp(pp));
172demand(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i);
173
174model master /numpat, demand/;";
175
176 return model;
177 }
178 static String GetSubModel()
179 {
180 String submodel = @"
181$Title Cutting Stock - Pricing problem is a knapsack model
182
183Set i widths
184Parameter
185 w(i) width;
186Scalar
187 r raw width;
188
189$gdxin csdata
190$load i w r
191
192Parameter
193 demdual(i) duals of master demand constraint /#i eps/;
194
195Variable z, y(i) new pattern;
196Integer variable y; y.up(i) = ceil(r/w(i));
197
198Equation defobj
199 knapsack knapsack constraint;
200
201defobj.. z =e= 1 - sum(i, demdual(i)*y(i));
202knapsack.. sum(i, w(i)*y(i)) =l= r;
203option optcr=0;
204model pricing /defobj, knapsack/; pricing.optfile=1";
205
206 return submodel;
207 }
208 }
209}
GAMSModelInstance AddModelInstance(string modelInstanceName=null)
string Key(int index)
void Run(GAMSOptions gamsOptions=null, GAMSCheckpoint checkpoint=null, TextWriter output=null, Boolean createOutDB=true)
Dictionary< string, string > Defines
GAMSDatabase AddDatabase(string databaseName=null, string inModelName=null)
void Instantiate(string modelDefinition, params GAMSModifier[] modifiers)
new GAMSVariableRecord FindRecord(params string[] keys)
GAMSSet AddSet(string identifier, int dimension, string explanatoryText="")
GAMSParameter AddParameter(string identifier, int dimension, string explanatoryText="")
void Solve(SymbolUpdateType updateType=SymbolUpdateType.BaseCase, TextWriter output=null, GAMSModelInstanceOpt miOpt=null)
GAMSOptions AddOptions(GAMSOptions optFrom=null)
new GAMSParameterRecord AddRecord(params string[] keys)
GAMSVariable GetVariable(string variableIdentifier)