Scippy

GCG

Branch-and-Price & Column Generation for Everyone

dec_compgreedily.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_compgreedily.cpp
29  * @ingroup DETECTORS
30  * @brief detector compgreedily (assigns the open cons and open vars of the partialdec greedily)
31  * @author Michael Bastubbe
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include "dec_compgreedily.h"
37 #include "cons_decomp.h"
38 #include "class_partialdecomp.h"
39 #include "class_detprobdata.h"
40 #include "scip/clock.h"
41 #include <iostream>
42 
43 /* constraint handler properties */
44 #define DEC_DETECTORNAME "compgreedily" /**< name of detector */
45 #define DEC_DESC "detector compgreedily" /**< description of detector*/
46 #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 */
47 #define DEC_MAXCALLROUND INT_MAX /** last round the detector gets called */
48 #define DEC_MINCALLROUND 0 /** first round the detector gets called */
49 #define DEC_FREQCALLROUNDORIGINAL 1 /** frequency the detector gets called in detection loop while detecting the original problem */
50 #define DEC_MAXCALLROUNDORIGINAL INT_MAX /** last round the detector gets called while detecting the original problem */
51 #define DEC_MINCALLROUNDORIGINAL 0 /** first round the detector gets called while detecting the original problem */
52 #define DEC_PRIORITY 0 /**< priority of the constraint handler for separation */
53 #define DEC_DECCHAR 'g' /**< display character of detector */
54 #define DEC_ENABLED FALSE /**< should the detection be enabled */
55 #define DEC_ENABLEDFINISHING FALSE /**< should the finishing be enabled */
56 #define DEC_ENABLEDPOSTPROCESSING FALSE /**< should the finishing be enabled */
57 #define DEC_SKIP FALSE /**< should detector be skipped if other detectors found decompositions */
58 #define DEC_USEFULRECALL FALSE /**< is it useful to call this detector on a descendant of the propagated partialdec */
59 
60 /** parameter limits for emphasis default */
61 
62 #define DEFAULT_LIMITHALFPERIMETERENABLEDFINISHING 20000 /** limit in terms of nrows + ncols for enabling finishing */
63 #define DEFAULT_LIMITHALFPERIMETERENABLEDORIGINAL 10000 /** limit in terms of nrows + ncols for enabling in detecting for unpresolved problem */
64 
65 
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 };
76 
77 
78 /*
79  * Local methods
80  */
81 
82 /* put your local methods here, and declare them static */
83 
84 /*
85  * detector callback methods
86  */
87 
88 /** destructor of detector to free user data (called when GCG is exiting) */
89 
90 #define freeCompgreedily NULL
91 
92 /** destructor of detector to free detector data (called before the solving process begins) */
93 
94 #define exitCompgreedily NULL
95 
96 #define initCompgreedily NULL
97 
98 static
99 DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecCompgreedily)
100 {
101  *result = SCIP_DIDNOTFIND;
102 
103  char decinfo[SCIP_MAXSTRLEN];
104  SCIP_CLOCK* temporaryClock;
105  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
106  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
107 
108  gcg::PARTIALDECOMP* partialdec = partialdecdetectiondata->workonpartialdec;
109 
110  //assign open conss and vars greedily
111  partialdec->completeGreedily();
112 
113  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
114 
115  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
116  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 1) );
117  partialdecdetectiondata->newpartialdecs[0] = partialdec;
118  partialdecdetectiondata->nnewpartialdecs = 1;
119 
120  partialdecdetectiondata->newpartialdecs[0]->addClockTime(SCIPgetClockTime(scip, temporaryClock));
121  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
122  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "compgreed");
123  partialdecdetectiondata->newpartialdecs[0]->addDetectorChainInfo(decinfo);
124  // we used the provided partialdec -> prevent deletion
125  partialdecdetectiondata->workonpartialdec = NULL;
126 
127  *result = SCIP_SUCCESS;
128 
129  return SCIP_OKAY;
130 }
131 
132 static
133 DEC_DECL_FINISHPARTIALDEC(finishPartialdecCompgreedily)
134 {
135  *result = SCIP_DIDNOTFIND;
136  char decinfo[SCIP_MAXSTRLEN];
137 
138  SCIP_CLOCK* temporaryClock;
139  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
140  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
141 
142  gcg::PARTIALDECOMP* partialdec = partialdecdetectiondata->workonpartialdec;
143 
144  //assign open conss and vars greedily
145  partialdec->completeGreedily();
146 
147  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
148 
149  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
150  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 1) );
151  partialdecdetectiondata->newpartialdecs[0] = partialdec;
152  partialdecdetectiondata->nnewpartialdecs = 1;
153  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "compgreed");
154  partialdecdetectiondata->newpartialdecs[0]->addDetectorChainInfo(decinfo);
155  partialdecdetectiondata->newpartialdecs[0]->addClockTime(SCIPgetClockTime(scip, temporaryClock));
156  // we used the provided partialdec -> prevent deletion
157  partialdecdetectiondata->workonpartialdec = NULL;
158 
159  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
160 
161  *result = SCIP_SUCCESS;
162 
163  return SCIP_OKAY;
164 }
165 
166 #define detectorPostprocessPartialdecCompgreedily NULL
167 
168 
169 static
170 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveCompgreedily)
171 {
172  char setstr[SCIP_MAXSTRLEN];
173 
174  const char* name = DECdetectorGetName(detector);
175 
176  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
177  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
178 
179  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
180  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
181 
182  return SCIP_OKAY;
183 }
184 
185 
186 static
187 DEC_DECL_SETPARAMDEFAULT(setParamDefaultCompgreedily)
188 {
189  char setstr[SCIP_MAXSTRLEN];
190 
191  const char* name = DECdetectorGetName(detector);
192 
193  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
194  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
195 
196  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
197  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
198 
199  return SCIP_OKAY;
200 }
201 
202 static
203 DEC_DECL_SETPARAMFAST(setParamFastCompgreedily)
204 {
205  char setstr[SCIP_MAXSTRLEN];
206 
207  const char* name = DECdetectorGetName(detector);
208 
209  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
210  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
211 
212  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
213  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
214 
215  return SCIP_OKAY;
216 
217 }
218 
219 
220 /*
221  * detector specific interface methods
222  */
223 
224 /** creates the handler for compgreedily detector and includes it in SCIP */
225 SCIP_RETCODE SCIPincludeDetectorCompgreedily(
226  SCIP* scip /**< SCIP data structure */
227  )
228 {
229  DEC_DETECTORDATA* detectordata;
230 
231  /**@todo create compgreedily detector data here*/
232  detectordata = NULL;
233 
234  SCIP_CALL( DECincludeDetector(scip, DEC_DETECTORNAME, DEC_DECCHAR, DEC_DESC, DEC_FREQCALLROUND, DEC_MAXCALLROUND, DEC_MINCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_ENABLED, DEC_ENABLEDFINISHING, DEC_ENABLEDPOSTPROCESSING, DEC_SKIP, DEC_USEFULRECALL, detectordata, freeCompgreedily,initCompgreedily, exitCompgreedily, propagatePartialdecCompgreedily, finishPartialdecCompgreedily, detectorPostprocessPartialdecCompgreedily, setParamAggressiveCompgreedily, setParamDefaultCompgreedily, setParamFastCompgreedily) );
235 
236  /**@todo add compgreedily detector parameters */
237 
238  return SCIP_OKAY;
239 }
gcg::PARTIALDECOMP::addClockTime
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
Definition: class_partialdecomp.cpp:286
DECdetectorGetName
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
Definition: cons_decomp.cpp:2618
DEC_PRIORITY
#define DEC_PRIORITY
Definition: dec_compgreedily.cpp:52
DEC_DECL_SETPARAMAGGRESSIVE
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveCompgreedily)
Definition: dec_compgreedily.cpp:170
gcg::PARTIALDECOMP::addDetectorChainInfo
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
Definition: class_partialdecomp.cpp:315
DEC_MINCALLROUND
#define DEC_MINCALLROUND
Definition: dec_compgreedily.cpp:48
DEC_FREQCALLROUND
#define DEC_FREQCALLROUND
Definition: dec_compgreedily.cpp:46
dec_compgreedily.h
compgreedily detector
DEC_MINCALLROUNDORIGINAL
#define DEC_MINCALLROUNDORIGINAL
Definition: dec_compgreedily.cpp:51
SCIPincludeDetectorCompgreedily
SCIP_RETCODE SCIPincludeDetectorCompgreedily(SCIP *scip)
Definition: dec_compgreedily.cpp:225
DEC_DESC
#define DEC_DESC
Definition: dec_compgreedily.cpp:45
cons_decomp.h
constraint handler for structure detection
DEC_USEFULRECALL
#define DEC_USEFULRECALL
Definition: dec_compgreedily.cpp:58
DEC_DECL_PROPAGATEPARTIALDEC
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecCompgreedily)
Definition: dec_compgreedily.cpp:99
DEC_DECL_FINISHPARTIALDEC
static DEC_DECL_FINISHPARTIALDEC(finishPartialdecCompgreedily)
Definition: dec_compgreedily.cpp:133
freeCompgreedily
#define freeCompgreedily
Definition: dec_compgreedily.cpp:90
initCompgreedily
#define initCompgreedily
Definition: dec_compgreedily.cpp:96
DEC_ENABLED
#define DEC_ENABLED
Definition: dec_compgreedily.cpp:54
DEC_DECCHAR
#define DEC_DECCHAR
Definition: dec_compgreedily.cpp:53
DEC_MAXCALLROUNDORIGINAL
#define DEC_MAXCALLROUNDORIGINAL
Definition: dec_compgreedily.cpp:50
exitCompgreedily
#define exitCompgreedily
Definition: dec_compgreedily.cpp:94
DEC_DECL_SETPARAMDEFAULT
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultCompgreedily)
Definition: dec_compgreedily.cpp:187
gcg::PARTIALDECOMP::completeGreedily
void completeGreedily()
assigns all open constraints and open variables
Definition: class_partialdecomp.cpp:2382
DEC_ENABLEDFINISHING
#define DEC_ENABLEDFINISHING
Definition: dec_compgreedily.cpp:55
DEC_FREQCALLROUNDORIGINAL
#define DEC_FREQCALLROUNDORIGINAL
Definition: dec_compgreedily.cpp:49
DEC_MAXCALLROUND
#define DEC_MAXCALLROUND
Definition: dec_compgreedily.cpp:47
DEC_DETECTORNAME
#define DEC_DETECTORNAME
Definition: dec_compgreedily.cpp:44
DEC_DECL_SETPARAMFAST
static DEC_DECL_SETPARAMFAST(setParamFastCompgreedily)
Definition: dec_compgreedily.cpp:203
gcg::PARTIALDECOMP
class to manage partial decompositions
Definition: class_partialdecomp.h:78
detectorPostprocessPartialdecCompgreedily
#define detectorPostprocessPartialdecCompgreedily
Definition: dec_compgreedily.cpp:166
DEC_ENABLEDPOSTPROCESSING
#define DEC_ENABLEDPOSTPROCESSING
Definition: dec_compgreedily.cpp:56
DECincludeDetector
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)),)
Definition: cons_decomp.cpp:3041
DEC_SKIP
#define DEC_SKIP
Definition: dec_compgreedily.cpp:57
DEC_DetectorData
Definition: dec_compgreedily.cpp:73
class_partialdecomp.h
class storing (potentially incomplete) decompositions
class_detprobdata.h
class storing partialdecs and the problem matrix