GMSCutstock.cs
1// --------------------------------------------------------------- -*- C# -*-
2 // File: Cutstock.cs
3 // --------------------------------------------------------------------------
4 using System;
5 using System.IO;
6 using GAMS;
7 using System.Collections.Generic;
8 
9 namespace Cutstock
10 {
19  class Cutstock
20  {
21  static void Main(string[] args)
22  {
23  GAMSWorkspace ws;
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 
148 Set i widths
149 Parameter
150  w(i) width
151  d(i) demand
152 Scalar
153  r raw width;
154 $gdxin csdata
155 $load i w d r
156 
157 $if not set pmax $set pmax 1000
158 Set p possible patterns /1*%pmax%/
159  pp(p) dynamic subset of p
160 Parameter
161  aip(i,p) number of width i in pattern growing in p;
162 
163 * Master model
164 Variable xp(p) patterns used
165  z objective variable
166 Integer variable xp; xp.up(p) = sum(i, d(i));
167 
168 Equation numpat number of patterns used
169  demand(i) meet demand;
170 
171 numpat.. z =e= sum(pp, xp(pp));
172 demand(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i);
173 
174 model 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 
183 Set i widths
184 Parameter
185  w(i) width;
186 Scalar
187  r raw width;
188 
189 $gdxin csdata
190 $load i w r
191 
192 Parameter
193  demdual(i) duals of master demand constraint /#i eps/;
194 
195 Variable z, y(i) new pattern;
196 Integer variable y; y.up(i) = ceil(r/w(i));
197 
198 Equation defobj
199  knapsack knapsack constraint;
200 
201 defobj.. z =e= 1 - sum(i, demdual(i)*y(i));
202 knapsack.. sum(i, w(i)*y(i)) =l= r;
203 option optcr=0;
204 model pricing /defobj, knapsack/; pricing.optfile=1";
205 
206  return submodel;
207  }
208  }
209 }
void Instantiate(string modelDefinition, params GAMSModifier[] modifiers)
string Key(int index)
Dictionary< string, string > Defines
new GAMSParameterRecord AddRecord(params string[] keys)
new GAMSVariableRecord FindRecord(params string[] keys)
GAMSOptions AddOptions(GAMSOptions optFrom=null)
GAMSModelInstance AddModelInstance(string modelInstanceName=null)
GAMSVariable GetVariable(string variableIdentifier)
void Solve(SymbolUpdateType updateType=SymbolUpdateType.BaseCase, TextWriter output=null, GAMSModelInstanceOpt miOpt=null)
GAMSParameter AddParameter(string identifier, int dimension, string explanatoryText="")
void Run(GAMSOptions gamsOptions=null, GAMSCheckpoint checkpoint=null, TextWriter output=null, Boolean createOutDB=true)
GAMSDatabase AddDatabase(string databaseName=null, string inModelName=null)
GAMSSet AddSet(string identifier, int dimension, string explanatoryText="", SetType setType=SetType.multi)