dec_constype.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2018 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include "dec_constype.h"
37 #include "cons_decomp.h"
38 #include "class_seeed.h"
39 #include "class_seeedpool.h"
40 #include "gcg.h"
41 #include "scip/cons_setppc.h"
42 #include "scip/scip.h"
43 #include "scip_misc.h"
44 #include "scip/clock.h"
45 
46 #include <iostream>
47 
48 /* constraint handler properties */
49 #define DEC_DETECTORNAME "constype"
50 #define DEC_DESC "detector constype"
51 #define DEC_FREQCALLROUND 1
52 #define DEC_MAXCALLROUND 0
53 #define DEC_MINCALLROUND 0
54 #define DEC_FREQCALLROUNDORIGINAL 1
55 #define DEC_MAXCALLROUNDORIGINAL 0
56 #define DEC_MINCALLROUNDORIGINAL 0
57 #define DEC_PRIORITY 0
58 #define DEC_DECCHAR 't'
59 #define DEC_ENABLED FALSE
60 #define DEC_ENABLEDORIGINAL FALSE
61 #define DEC_ENABLEDFINISHING FALSE
62 #define DEC_ENABLEDPOSTPROCESSING FALSE
63 #define DEC_SKIP FALSE
64 #define DEC_USEFULRECALL FALSE
65 #define DEC_LEGACYMODE FALSE
66 /*
67  * Data structures
68  */
69 
73 struct DEC_DetectorData
74 {
75 };
76 
77 /*
78  * Local methods
79  */
80 
81 /* put your local methods here, and declare them static */
82 
84 std::vector< std::vector<int> > getSubsets(std::vector<int> set)
85 {
86  std::vector< std::vector<int> > subset;
87  std::vector<int> empty;
88  subset.push_back( empty );
89 
90  for ( size_t i = 0; i < set.size(); ++i )
91  {
92  std::vector< std::vector<int> > subsetTemp = subset;
93 
94  for (size_t j = 0; j < subsetTemp.size(); ++j)
95  subsetTemp[j].push_back( set[i] );
96 
97  for (size_t j = 0; j < subsetTemp.size(); ++j)
98  subset.push_back( subsetTemp[j] );
99  }
100  return subset;
101 }
102 
103 /*
104  * detector callback methods
105  */
106 
108 #define freeConstype NULL
109 
111 #if 0
112 static
114 { /*lint --e{715}*/
115 
116  SCIPerrorMessage("Exit function of detector <%s> not implemented!\n", DEC_DETECTORNAME);
117  SCIPABORT();
118 
119  return SCIP_OKAY;
120 }
121 #else
122 #define exitConstype NULL
123 #endif
124 
126 #if 0
127 static
129 { /*lint --e{715}*/
130 
131  SCIPerrorMessage("Init function of detector <%s> not implemented!\n", DEC_DETECTORNAME);
132  SCIPABORT();
133 
134  return SCIP_OKAY;
135 }
136 #else
137 #define initConstype NULL
138 #endif
139 
141 //static DEC_DECL_DETECTSTRUCTURE(detectConstype)
142 //{ /*lint --e{715}*/
143 // *result = SCIP_DIDNOTFIND;
144 //
145 // SCIPerrorMessage("Detection function of detector <%s> not implemented!\n", DEC_DETECTORNAME)
146 //; SCIPABORT(); /*lint --e{527}*/
147 //
148 // return SCIP_OKAY;
149 //}
150 
151 #define detectConstype NULL
152 
153 static DEC_DECL_PROPAGATESEEED(propagateSeeedConstype)
154 {
155  *result = SCIP_DIDNOTFIND;
156  char decinfo[SCIP_MAXSTRLEN];
157 
158  SCIP_CLOCK* temporaryClock;
159  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
160  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
161 
162  SCIP_CONS* cons;
163 
164  int seeedCounter = 0;
165  gcg::Seeed* seeedOrig;
166  gcg::Seeed* seeed;
167 
168  std::vector<consType> foundConstypes(0);
169  std::vector<int> constypesIndices(0);
170 
171  seeedOrig = seeedPropagationData->seeedToPropagate;
172 
173 
174 
175  for( int i = 0; i < seeedOrig->getNOpenconss(); ++i)
176  {
177  cons = seeedPropagationData->seeedpool->getConsForIndex(seeedOrig->getOpenconss()[i]);
178  consType cT = GCGconsGetType(cons);
179 
181  std::vector<consType>::const_iterator constypeIter = foundConstypes.begin();
182  for(; constypeIter != foundConstypes.end(); ++constypeIter)
183  {
184  if(*constypeIter == cT)
185  break;
186  }
187 
188  if( constypeIter == foundConstypes.end() )
189  {
190  foundConstypes.push_back(GCGconsGetType(cons) );
191  }
192  }
193 
194  for(size_t i = 0; i < foundConstypes.size(); ++i)
195  {
196  constypesIndices.push_back(i);
197  }
198 
199  std::vector< std::vector<int> > subsetsOfConstypes = getSubsets(constypesIndices);
200 
201  SCIP_CALL( SCIPallocMemoryArray(scip, &(seeedPropagationData->newSeeeds), subsetsOfConstypes.size() - 1) );
202  seeedPropagationData->nNewSeeeds = subsetsOfConstypes.size() - 1;
203 
204  for(size_t subset = 0; subset < subsetsOfConstypes.size(); ++subset)
205  {
206  if(subsetsOfConstypes[subset].size() == 0)
207  continue;
208 
209  seeed = new gcg::Seeed(seeedOrig);
211  for( int i = 0; i < seeed->getNOpenconss(); ++i)
212  {
213  for(size_t constypeId = 0; constypeId < subsetsOfConstypes[subset].size(); ++constypeId )
214  {
215  cons = seeedPropagationData->seeedpool->getConsForIndex(seeed->getOpenconss()[i]);
216  if( GCGconsGetType (cons) == foundConstypes[subsetsOfConstypes[subset][constypeId]] )
217  {
218  seeed->bookAsMasterCons(seeed->getOpenconss()[i]);
219  }
220  }
221  }
222  seeed->flushBooked();
223  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "constype");
224  seeedPropagationData->newSeeeds[0]->addDetectorChainInfo(decinfo);
225 
226  seeedPropagationData->newSeeeds[seeedCounter] = seeed;
227  seeedCounter++;
228  }
229 
230  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
231  for( int s = 0; s < seeedPropagationData->nNewSeeeds; ++s )
232  {
233  seeedPropagationData->newSeeeds[s]->addClockTime(SCIPclockGetTime(temporaryClock ) );
234  }
235  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
236 
237  *result = SCIP_SUCCESS;
238 
239  return SCIP_OKAY;
240 }
241 
242 #define finishSeeedConstype NULL
243 #define detectorPostprocessSeeedConstype NULL
244 static
245 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveConstype)
246 {
247  char setstr[SCIP_MAXSTRLEN];
248  const char* name = DECdetectorGetName(detector);
249 
250  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
251  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
252 
253  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
254  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
255 
256  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
257  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
258 
259  return SCIP_OKAY;
260 
261 }
262 
263 
264 static
265 DEC_DECL_SETPARAMDEFAULT(setParamDefaultConstype)
266 {
267 
268  return SCIP_OKAY;
269 
270 }
271 
272 static
273 DEC_DECL_SETPARAMFAST(setParamFastConstype)
274 {
275  char setstr[SCIP_MAXSTRLEN];
276 
277  const char* name = DECdetectorGetName(detector);
278 
279  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
280  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
281 
282  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
283  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
284 
285  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
286  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
287 
288 
289  return SCIP_OKAY;
290 
291 }
292 
293 
294 
295 /*
296  * detector specific interface methods
297  */
298 
301 )
302 {
303  DEC_DETECTORDATA* detectordata;
304 
306  detectordata = NULL;
307 
308  SCIP_CALL(
311  freeConstype, initConstype, exitConstype, propagateSeeedConstype, NULL, NULL, finishSeeedConstype, detectorPostprocessSeeedConstype, setParamAggressiveConstype, setParamDefaultConstype, setParamFastConstype));
312 
315  return SCIP_OKAY;
316 }
static DEC_DECL_PROPAGATESEEED(propagateSeeedConstype)
#define DEC_MAXCALLROUND
#define DEC_DECL_INITDETECTOR(x)
Definition: type_detector.h:70
#define DEC_USEFULRECALL
const int * getOpenconss()
returns array containing constraints not assigned yet
#define DEC_LEGACYMODE
GCG interface methods.
#define freeConstype
#define DEC_MINCALLROUNDORIGINAL
#define detectorPostprocessSeeedConstype
consType GCGconsGetType(SCIP_CONS *cons)
Definition: scip_misc.c:51
consType
Definition: scip_misc.h:47
#define DEC_MAXCALLROUNDORIGINAL
#define DEC_SKIP
SCIP_RETCODE flushBooked()
assigns all booked constraints and variables and deletes them from list of open cons and open vars ...
#define DEC_FREQCALLROUND
various SCIP helper methods
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
constype detector
#define DEC_MINCALLROUND
#define DEC_PRIORITY
std::vector< std::vector< int > > getSubsets(std::vector< int > set)
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveConstype)
#define DEC_DETECTORNAME
#define DEC_DECCHAR
#define DEC_ENABLEDFINISHING
#define finishSeeedConstype
SCIP_RETCODE DECincludeDetector(SCIP *scip, const char *name, const char decchar, const char *description, int freqCallRound, int maxCallRound, int minCallRound, int freqCallRoundOriginal, int maxCallRoundOriginal, int minCallRoundOriginal, int priority, SCIP_Bool enabled, SCIP_Bool enabledOriginal, SCIP_Bool enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, SCIP_Bool legacymode, DEC_DETECTORDATA *detectordata, DEC_DECL_DETECTSTRUCTURE((*detectStructure)), DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATESEEED((*propagateSeeedDetector)), DEC_DECL_PROPAGATEFROMTOOLBOX((*propagateFromToolboxDetector)), DEC_DECL_FINISHFROMTOOLBOX((*finishFromToolboxDetector)), DEC_DECL_FINISHSEEED((*finishSeeedDetector)), DEC_DECL_POSTPROCESSSEEED((*postprocessSeeedDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
includes one detector
#define exitConstype
static DEC_DECL_SETPARAMFAST(setParamFastConstype)
SCIP_RETCODE SCIPincludeDetectorConstype(SCIP *scip)
#define DEC_DESC
#define DEC_DECL_EXITDETECTOR(x)
Definition: type_detector.h:80
struct gcg::subset subset
#define DEC_ENABLEDORIGINAL
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultConstype)
#define DEC_FREQCALLROUNDORIGINAL
int getNOpenconss()
returns size of vector containing constraints not assigned yet
class with functions for seeed pool where a seeed is a (potentially incomplete) description of a deco...
SCIP_RETCODE bookAsMasterCons(int consToMaster)
books a constraint to be added to the master constraints (by calling flushBooked all bookings are in ...
#define DEC_ENABLEDPOSTPROCESSING
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
SCIP_RESULT result
Definition: dec_dbscan.cpp:88
#define detectConstype
constraint handler for structure detection
#define initConstype
#define DEC_ENABLED
SCIP_CONS * getConsForIndex(int consIndex)
returns the SCIP constraint related to a constraint index