Scippy

GCG

Branch-and-Price & Column Generation for Everyone

dec_postprocess.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-2021 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 
28 /**@file dec_postprocess.cpp
29  * @ingroup DETECTORS
30  * @brief checks if there are master constraints that can be assigned to one block (without any other changes)
31  * @author Michael Bastubbe
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include "dec_postprocess.h"
37 #include "cons_decomp.h"
38 #include "gcg.h"
39 #include "class_partialdecomp.h"
40 #include "class_detprobdata.h"
41 #include "scip/scip.h"
42 #include "scip_misc.h"
43 #include "scip/clock.h"
44 #include <iostream>
45 #include <algorithm>
46 #include <vector>
47 #include <queue>
48 
49 /* constraint handler properties */
50 #define DEC_DETECTORNAME "postprocess" /**< name of detector */
51 #define DEC_DESC "detector postprocess" /**< description of detector*/
52 #define DEC_FREQCALLROUND 1 /**< frequency the detector gets called in detection loop ,ie it is called in round r if and only if minCallRound <= r <= maxCallRound AND (r - minCallRound) mod freqCallRound == 0 */
53 #define DEC_MAXCALLROUND INT_MAX /**< last round the detector gets called */
54 #define DEC_MINCALLROUND 0 /**< first round the detector gets called */
55 #define DEC_PRIORITY 1000000 /**< priority of the constraint handler for separation */
56 #define DEC_FREQCALLROUNDORIGINAL 1 /**< frequency the detector gets called in detection loop while detecting the original problem */
57 #define DEC_MAXCALLROUNDORIGINAL INT_MAX /**< last round the detector gets called while detecting the original problem */
58 #define DEC_MINCALLROUNDORIGINAL 0 /**< first round the detector gets called while detecting the original problem */
59 #define DEC_DECCHAR 'p' /**< display character of detector */
60 #define DEC_ENABLED FALSE /**< should the detection be enabled */
61 #define DEC_ENABLEDFINISHING FALSE /**< should the finishing be enabled */
62 #define DEC_ENABLEDPOSTPROCESSING TRUE /**< should the postprocessing be enabled */
63 #define DEC_SKIP FALSE /**< should detector be skipped if other detectors found decompositions */
64 #define DEC_USEFULRECALL FALSE /**< is it useful to call this detector on a descendant of the propagated partialdec */
65 #define DEFAULT_USECONSSADJ TRUE
66 /*
67  * Data structures
68  */
69 
70 /** @todo fill in the necessary detector data */
71 
72 /** detector handler data */
73 struct DEC_DetectorData
74 {
75  SCIP_Bool useconssadj;
76 };
77 
78 
79 /*
80  * Local methods
81  */
82 
83 /* put your local methods here, and declare them static */
84 
85 
86 /*
87  * detector callback methods
88  */
89 
90 /** destructor of detector to free user data (called when GCG is exiting) */
91 /** destructor of detector to free detector data (called when SCIP is exiting) */
92 static
93 DEC_DECL_FREEDETECTOR(freePostprocess)
94 { /*lint --e{715}*/
95  DEC_DETECTORDATA *detectordata;
96 
97  assert(scip != NULL);
98  assert(detector != NULL);
99 
100  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
101 
102  detectordata = DECdetectorGetData(detector);
103  assert(detectordata != NULL);
104 
105  SCIPfreeMemory(scip, &detectordata);
106 
107  return SCIP_OKAY;
108 }
109 
110 
111 
112 
113 /** destructor of detector to free detector data (called before the solving process begins) */
114 #define exitPostprocess NULL
115 
116 /** detection initialization function of detector (called before solving is about to begin) */
117 #define initPostprocess NULL
118 
119 #define propagatePartialdecPostprocess NULL
120 #define finishPartialdecPostprocess NULL
121 
122 static
123 DEC_DECL_POSTPROCESSPARTIALDEC(postprocessPartialdecPostprocess)
124 {
125  *result = SCIP_DIDNOTFIND;
126 
127  SCIP_CLOCK* temporaryClock;
128  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
129  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
130  char decinfo[SCIP_MAXSTRLEN];
131  SCIP_Bool success;
132  SCIP_Bool byconssadj;
133 
134  gcg::PARTIALDECOMP* partialdec = partialdecdetectiondata->workonpartialdec;
135  gcg::DETPROBDATA* detprobdata = partialdecdetectiondata->detprobdata;
136  assert(partialdecdetectiondata->workonpartialdec->getDetprobdata() == detprobdata);
137 
138  SCIPgetBoolParam(scip, "detection/detectors/postprocess/useconssadj", &byconssadj);
139 
140  if ( byconssadj && !detprobdata->isConssAdjInitialized() )
141  detprobdata->createConssAdjacency();
142 
143  //complete the partialdec by bfs
144  if ( byconssadj )
145  {
146  success = FALSE;
147  std::vector<int> constoreassign;
148  std::vector<int> blockforconstoreassign;
149 
150  partialdec->sort();
151 
152  std::vector<int> blockforvar(partialdec->getNVars(), -1 );
153 
154  for( int b = 0; b < partialdec->getNBlocks(); ++b )
155  {
156  for( size_t j = 0; j < (size_t) partialdec->getNVarsForBlock(b); ++j )
157  {
158  blockforvar[partialdec->getVarsForBlock(b)[j]] = b;
159  }
160  }
161 
162  for( int mc = 0; mc < partialdec->getNMasterconss(); ++mc )
163  {
164  int masterconsid = partialdec->getMasterconss()[mc];
165  int hittenblock = -1;
166 
167  SCIP_Bool hitsmastervar = FALSE;
168  SCIP_Bool varhitsotherblock = FALSE;
169 
170  for( int var = 0; var < detprobdata->getNVarsForCons(masterconsid); ++var )
171  {
172  int varid = detprobdata->getVarsForCons(masterconsid)[var];
173  if( partialdec->isVarMastervar(varid) )
174  {
175  hitsmastervar = TRUE;
176  break;
177  }
178 
179  if ( blockforvar[varid] != -1 )
180  {
181  if( hittenblock == -1 )
182  hittenblock = blockforvar[varid];
183  else if( hittenblock != blockforvar[varid] )
184  {
185  varhitsotherblock = TRUE;
186  break;
187  }
188  }
189  }
190 
191  if( hitsmastervar || varhitsotherblock )
192  continue;
193 
194  if ( hittenblock != -1 )
195  {
196  constoreassign.push_back(masterconsid);
197  blockforconstoreassign.push_back(hittenblock);
198  }
199  }
200 
201  for( size_t i = 0; i < constoreassign.size() ; ++i )
202  {
203  partialdec->setConsToBlock(constoreassign[i], blockforconstoreassign[i]);
204  partialdec->removeMastercons(constoreassign[i]);
205  }
206 
207  if( !constoreassign.empty() )
208  success = TRUE;
209 
210  partialdec->prepare();
211  }
212  else
213  success = FALSE;
214 
215  if ( !success )
216  {
217  partialdecdetectiondata->nnewpartialdecs = 0;
218  *result = SCIP_DIDNOTFIND;
219  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
220  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
221  return SCIP_OKAY;
222  }
223  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
224 
225  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
226  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 1) );
227  partialdecdetectiondata->newpartialdecs[0] = partialdec;
228  partialdecdetectiondata->nnewpartialdecs = 1;
229  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "postprocess");
230  partialdecdetectiondata->newpartialdecs[0]->addDetectorChainInfo(decinfo);
231  partialdecdetectiondata->newpartialdecs[0]->addClockTime(SCIPgetClockTime(scip, temporaryClock));
232  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
233  // we used the provided partialdec -> prevent deletion
234  partialdecdetectiondata->workonpartialdec = NULL;
235 
236  *result = SCIP_SUCCESS;
237 
238  return SCIP_OKAY;
239 }
240 
241 
242 static
243 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressivePostprocess)
244 {
245  char setstr[SCIP_MAXSTRLEN];
246 
247  const char* name = DECdetectorGetName(detector);
248 
249  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
250  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
251 
252  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
253  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE ) );
254 
255  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/postprocessingenabled", name);
256  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
257 
258 
259  return SCIP_OKAY;
260 
261 }
262 
263 
264 static
265 DEC_DECL_SETPARAMDEFAULT(setParamDefaultPostprocess)
266 {
267  char setstr[SCIP_MAXSTRLEN];
268 
269  const char* name = DECdetectorGetName(detector);
270 
271  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
272  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
273 
274  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
275  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING) );
276 
277  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/postprocessingenabled", name);
278  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDPOSTPROCESSING ) );
279 
280 
281  return SCIP_OKAY;
282 
283 }
284 
285 static
286 DEC_DECL_SETPARAMFAST(setParamFastPostprocess)
287 {
288  char setstr[SCIP_MAXSTRLEN];
289 
290  const char* name = DECdetectorGetName(detector);
291 
292  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
293  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
294 
295  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
296  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
297 
298  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/postprocessingenabled", name);
299  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
300 
301 
302  return SCIP_OKAY;
303 
304 }
305 
306 
307 
308 /*
309  * detector specific interface methods
310  */
311 
312 /** creates the handler for postprocess detector and includes it in SCIP */
314  SCIP* scip /**< SCIP data structure */
315  )
316 {
317  DEC_DETECTORDATA* detectordata;
318 
319  /**@todo create postprocess detector data here*/
320  detectordata = NULL;
321  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
322  assert(detectordata != NULL);
323 
324  detectordata->useconssadj = TRUE;
325 
328  postprocessPartialdecPostprocess, setParamAggressivePostprocess, setParamDefaultPostprocess, setParamFastPostprocess) );
329 
330  /* add consname detector parameters */
331  /**@todo add postprocess detector parameters */
332  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/postprocess/useconssadj", "should the constraint adjacency be used", &detectordata->useconssadj, FALSE, DEFAULT_USECONSSADJ, NULL, NULL) );
333 
334 
335  return SCIP_OKAY;
336 }
#define DEC_USEFULRECALL
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
#define DEC_MAXCALLROUNDORIGINAL
GCG interface methods.
std::vector< int > & getVarsForBlock(int block)
Gets array containing vars of a block.
#define exitPostprocess
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
SCIP_RETCODE SCIPincludeDetectorPostprocess(SCIP *scip)
#define propagatePartialdecPostprocess
constraint handler for structure detection
static DEC_DECL_SETPARAMFAST(setParamFastPostprocess)
#define DEC_ENABLED
std::vector< int > & getMasterconss()
Gets array containing all master conss indices.
static DEC_DECL_FREEDETECTOR(freePostprocess)
#define finishPartialdecPostprocess
int getNVarsForBlock(int block)
Gets size of the vector containing vars assigned to a block.
postprocess detector
#define DEC_FREQCALLROUND
various SCIP helper methods
#define DEC_MINCALLROUNDORIGINAL
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultPostprocess)
void setConsToBlock(int consToBlock, int block)
adds a constraint to a block, does not delete this cons from list of open conss
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
bool sort()
sorts the vars and conss data structures by their indices
void createConssAdjacency()
create the constraint adjacency datastructure that is used (if created) for some methods to faster ac...
#define DEC_DECCHAR
#define DEC_SKIP
static DEC_DECL_POSTPROCESSPARTIALDEC(postprocessPartialdecPostprocess)
#define DEC_PRIORITY
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressivePostprocess)
#define DEC_ENABLEDFINISHING
class to manage partial decompositions
bool isVarMastervar(int var)
Checks whether the var is a master var.
int getNBlocks()
Gets the number of blocks.
#define DEC_FREQCALLROUNDORIGINAL
#define initPostprocess
#define DEFAULT_USECONSSADJ
void removeMastercons(int consid)
removes the given cons from master
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
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 enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, DEC_DETECTORDATA *detectordata, DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATEPARTIALDEC((*propagatePartialdecDetector)), DEC_DECL_FINISHPARTIALDEC((*finishPartialdecDetector)), DEC_DECL_POSTPROCESSPARTIALDEC((*postprocessPartialdecDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
SCIP_Bool isConssAdjInitialized()
determines whether or not the constraint-constraint adjacency data structure is initilized
class storing (potentially incomplete) decompositions
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
int getNMasterconss()
Gets size of the vector containing master conss.
#define DEC_MINCALLROUND
class storing partialdecs and the problem matrix
#define DEC_ENABLEDPOSTPROCESSING
#define DEC_DETECTORNAME
#define DEC_MAXCALLROUND
#define DEC_DESC
int getNVars()
Gets number of vars.