Scippy

GCG

Branch-and-Price & Column Generation for Everyone

dec_connectedbase.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_connectedbase.cpp
29  * @ingroup DETECTORS
30  * @brief detector connectedbase (completes the partialdec by bfs)
31  * @author Martin Bergner
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include "dec_connectedbase.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 "connectedbase" /**< name of detector */
51 #define DEC_DESC "detector connectedbase" /**< 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 0 /**< 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 'C' /**< display character of detector */
60 #define DEC_ENABLED FALSE /**< should the detection be enabled */
61 #define DEC_ENABLEDFINISHING TRUE /**< should the finishing be enabled */
62 #define DEC_ENABLEDPOSTPROCESSING FALSE /**< should the finishing 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(freeConnectedbase)
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 /** destructor of detector to free detector data (called before the solving process begins) */
112 #define exitConnectedbase NULL
113 
114 /** detection initialization function of detector (called before solving is about to begin) */
115 #define initConnectedbase NULL
116 
117 #define propagatePartialdecConnectedbase NULL
118 
119 
120 static
121 DEC_DECL_FINISHPARTIALDEC(finishPartialdecConnectedbase)
122 {
123  *result = SCIP_DIDNOTFIND;
124 
125  SCIP_CLOCK* temporaryClock;
126  char decinfo[SCIP_MAXSTRLEN];
127 
128  SCIP_Bool byconssadj;
129 
130  gcg::PARTIALDECOMP* partialdec = partialdecdetectiondata->workonpartialdec;
131  gcg::DETPROBDATA* detprobdata = partialdecdetectiondata->detprobdata;
132  assert(partialdecdetectiondata->workonpartialdec->getDetprobdata() == detprobdata);
133 
134  SCIPgetBoolParam(scip, "detection/detectors/connectedbase/useconssadj", &byconssadj);
135 
136  if ( byconssadj && !detprobdata->isConssAdjInitialized() )
137  detprobdata->createConssAdjacency();
138 
139  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
140  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
141 
142  //complete the partialdec by bfs
143  if( byconssadj && partialdec->getNLinkingvars() == 0 )
144  partialdec->completeByConnectedConssAdjacency();
145  else
146  partialdec->completeByConnected();
147 
148  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
149 
150  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
151  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 1) );
152  partialdecdetectiondata->newpartialdecs[0] = partialdec;
153  partialdecdetectiondata->nnewpartialdecs = 1;
154  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "connected");
155  partialdecdetectiondata->newpartialdecs[0]->addDetectorChainInfo(decinfo);
156 
157  partialdecdetectiondata->newpartialdecs[0]->addClockTime( SCIPgetClockTime(scip, temporaryClock) );
158  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
159  // we used the provided partialdec -> prevent deletion
160  partialdecdetectiondata->workonpartialdec = NULL;
161 
162  *result = SCIP_SUCCESS;
163 
164  return SCIP_OKAY;
165 }
166 
167 
168 #define detectorPostprocessPartialdecConnectedbase NULL
169 
170 
171 static
172 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveConnectedbase)
173 {
174  char setstr[SCIP_MAXSTRLEN];
175 
176  const char* name = DECdetectorGetName(detector);
177 
178 
179  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
180  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE ) );
181 
182 
183  return SCIP_OKAY;
184 
185 }
186 
187 
188 static
189 DEC_DECL_SETPARAMDEFAULT(setParamDefaultConnectedbase)
190 {
191  char setstr[SCIP_MAXSTRLEN];
192 
193  const char* name = DECdetectorGetName(detector);
194 
195  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
196  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
197 
198  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
199  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
200 
201  return SCIP_OKAY;
202 
203 }
204 
205 
206 static
207 DEC_DECL_SETPARAMFAST(setParamFastConnectedbase)
208 {
209  char setstr[SCIP_MAXSTRLEN];
210 
211  const char* name = DECdetectorGetName(detector);
212 
213  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
214  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
215 
216  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
217  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE ) );
218 
219  return SCIP_OKAY;
220 
221 }
222 
223 
224 /*
225  * detector specific interface methods
226  */
227 
228 /** creates the handler for connectedbase detector and includes it in SCIP */
230  SCIP* scip /**< SCIP data structure */
231  )
232 {
233  DEC_DETECTORDATA* detectordata;
234 
235  /**@todo create connectedbase detector data here*/
236  detectordata = NULL;
237  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
238  assert(detectordata != NULL);
239 
240  detectordata->useconssadj = TRUE;
241 
243 
244  /* add consname detector parameters */
245  /**@todo add connectedbase detector parameters */
246  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/connectedbase/useconssadj", "should the constraint adjacency be used", &detectordata->useconssadj, FALSE, DEFAULT_USECONSSADJ, NULL, NULL) );
247 
248  return SCIP_OKAY;
249 }
#define initConnectedbase
static DEC_DECL_FREEDETECTOR(freeConnectedbase)
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
GCG interface methods.
#define DEC_ENABLEDFINISHING
#define DEC_DECCHAR
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
#define DEC_DETECTORNAME
static DEC_DECL_SETPARAMFAST(setParamFastConnectedbase)
constraint handler for structure detection
#define detectorPostprocessPartialdecConnectedbase
SCIP_RETCODE SCIPincludeDetectorConnectedbase(SCIP *scip)
#define DEC_MINCALLROUND
static DEC_DECL_FINISHPARTIALDEC(finishPartialdecConnectedbase)
#define DEC_FREQCALLROUND
void completeByConnected()
assigns all open constraints and open variables
various SCIP helper methods
#define propagatePartialdecConnectedbase
#define DEC_DESC
#define DEC_MAXCALLROUNDORIGINAL
#define DEC_ENABLEDPOSTPROCESSING
#define DEC_SKIP
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
#define DEFAULT_USECONSSADJ
connectedbase detector
int getNLinkingvars()
Gets size of the vector containing linking vars.
void createConssAdjacency()
create the constraint adjacency datastructure that is used (if created) for some methods to faster ac...
#define DEC_FREQCALLROUNDORIGINAL
#define DEC_USEFULRECALL
class to manage partial decompositions
#define exitConnectedbase
#define DEC_MAXCALLROUND
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
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultConnectedbase)
#define DEC_MINCALLROUNDORIGINAL
class storing partialdecs and the problem matrix
#define DEC_PRIORITY
void completeByConnectedConssAdjacency()
assigns all open constraints and open variables
#define DEC_ENABLED
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveConnectedbase)