dec_densemasterconss.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_densemasterconss.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 <sstream>
47 
48 #include <iostream>
49 #include <algorithm>
50 
51 
52 /* constraint handler properties */
53 #define DEC_DETECTORNAME "densemasterconss"
54 #define DEC_DESC "detector densemasterconss"
55 #define DEC_FREQCALLROUND 1
56 #define DEC_MAXCALLROUND 0
57 #define DEC_MINCALLROUND 0
58 #define DEC_FREQCALLROUNDORIGINAL 1
59 #define DEC_MAXCALLROUNDORIGINAL INT_MAX
60 #define DEC_MINCALLROUNDORIGINAL 0
61 #define DEC_PRIORITY 0
62 #define DEC_DECCHAR 'd'
63 #define DEC_ENABLED TRUE
64 #define DEC_ENABLEDORIGINAL FALSE
65 #define DEC_ENABLEDFINISHING FALSE
66 #define DEC_ENABLEDPOSTPROCESSING FALSE
67 #define DEC_SKIP FALSE
68 #define DEC_USEFULRECALL FALSE
69 #define DEC_LEGACYMODE FALSE
71 /*
72  * Data structures
73  */
74 
78 struct DEC_DetectorData
79 {
80 };
81 
82 /*
83  * Local methods
84  */
85 
86 struct sort_pred {
87  bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
88  return left.first > right.first;
89  }
90 };
91 
92 /* put your local methods here, and declare them static */
93 
94 /*
95  * detector callback methods
96  */
97 
99 #define freeDensemasterconss NULL
100 
102 #if 0
103 static
105 { /*lint --e{715}*/
106 
107  SCIPerrorMessage("Exit function of detector <%s> not implemented!\n", DEC_DETECTORNAME);
108  SCIPABORT();
109 
110  return SCIP_OKAY;
111 }
112 #else
113 #define exitDensemasterconss NULL
114 #endif
115 
117 #if 0
118 static
120 { /*lint --e{715}*/
121 
122  SCIPerrorMessage("Init function of detector <%s> not implemented!\n", DEC_DETECTORNAME);
123  SCIPABORT();
124 
125  return SCIP_OKAY;
126 }
127 #else
128 #define initDensemasterconss NULL
129 #endif
130 
131 #define detectDensemasterconss NULL
132 
133 #define finishSeeedDensemasterconss NULL
134 
135 static DEC_DECL_PROPAGATESEEED(propagateSeeedDensemasterconss)
136 {
137  *result = SCIP_DIDNOTFIND;
138  char decinfo[SCIP_MAXSTRLEN];
139 
140  SCIP_CLOCK* temporaryClock;
141 
142  gcg::Seeedpool* seeedpool;
143  std::vector<gcg::Seeed*> foundseeeds(0);
144 
145  gcg::Seeed* seeedOrig;
146  gcg::Seeed* seeed;
147 
148  seeedOrig = seeedPropagationData->seeedToPropagate;
149  std::stringstream decdesc;
150 
151  SCIP_Real maxratio = 0.2;
152  int maxdiff = -1;
153  int maxdiffindex = -1;
154  int lastindex = -1;
155 
156  seeedpool = seeedPropagationData->seeedpool;
157  std::vector<std::pair<int,int>> nnonzeros = std::vector<std::pair<int,int>>(seeedpool->getNConss(), std::pair<int, int>(0,-1) );
158 
159  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
160  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
161 
162 
163  seeed = new gcg::Seeed(seeedOrig);
164 
165  lastindex = maxratio * seeedpool->getNConss();
167  for( int i = 0; i < seeed->getNOpenconss(); ++i )
168  {
169  int cons = seeed->getOpenconss()[i];
170  int nnonzeroscons = seeedpool->getNVarsForCons(cons);
171 
172  nnonzeros[cons] = std::pair<int,int>(nnonzeroscons, i);
173  }
174 
175  std::sort(nnonzeros.begin(), nnonzeros.end(), sort_pred() );
176 
177  for( int i = 0; i < lastindex && i < (int) nnonzeros.size() - 1; ++i )
178  {
179  if( maxdiff < nnonzeros[i].first - nnonzeros[i+1].first )
180  {
181  maxdiff = nnonzeros[i].first - nnonzeros[i+1].first;
182  maxdiffindex = i;
183  }
184  }
185 
186 
187  for( int i = 0; i < maxdiffindex; ++i )
188  {
189  seeed->bookAsMasterCons(seeed->getOpenconss()[nnonzeros[i].second]);
190  }
191 
192  decdesc << "densemasterconss" << "\\_" << maxdiffindex ;
193 
194  seeed->flushBooked();
195  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, decdesc.str().c_str());
196  seeed->addDetectorChainInfo(decinfo);
197 
198  foundseeeds.push_back(seeed);
199 
200 
201  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
202 
203  SCIP_CALL( SCIPallocMemoryArray(scip, &(seeedPropagationData->newSeeeds), foundseeeds.size() ) );
204  seeedPropagationData->nNewSeeeds = foundseeeds.size();
205 
206  SCIPinfoMessage(scip, NULL, "dec_densemasterconss found %d new seeed \n", seeedPropagationData->nNewSeeeds );
207 
208  for( int s = 0; s < seeedPropagationData->nNewSeeeds; ++s )
209  {
210  seeedPropagationData->newSeeeds[s] = foundseeeds[s];
211  seeedPropagationData->newSeeeds[s]->addClockTime(SCIPclockGetTime(temporaryClock ) );
212  }
213 
214  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
215 
216  *result = SCIP_SUCCESS;
217 
218  return SCIP_OKAY;
219 }
220 
221 #define detectorPostprocessSeeedDensemasterconss NULL
222 
223 static
224 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDensemasterconss)
225 {
226  char setstr[SCIP_MAXSTRLEN];
227  const char* name = DECdetectorGetName(detector);
228 
229  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
230  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
231 
232  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
233  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
234 
235  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
236  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
237 
238 
239  return SCIP_OKAY;
240 
241 }
242 
243 
244 static
245 DEC_DECL_SETPARAMDEFAULT(setParamDefaultDensemasterconss)
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, DEC_ENABLED) );
252 
253  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
254  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDORIGINAL ) );
255 
256  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
257  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
258 
259  return SCIP_OKAY;
260 
261 }
262 
263 static
264 DEC_DECL_SETPARAMFAST(setParamFastDensemasterconss)
265 {
266  char setstr[SCIP_MAXSTRLEN];
267  const char* name = DECdetectorGetName(detector);
268 
269  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
270  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
271 
272  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
273  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
274 
275  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
276  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
277 
278 
279  return SCIP_OKAY;
280 
281 }
282 
283 
284 
285 /*
286  * detector specific interface methods
287  */
288 
291 )
292 {
293  DEC_DETECTORDATA* detectordata;
294 
296  detectordata = NULL;
297 
298  SCIP_CALL(
301  detectDensemasterconss, freeDensemasterconss, initDensemasterconss, exitDensemasterconss, propagateSeeedDensemasterconss, NULL, NULL, finishSeeedDensemasterconss, detectorPostprocessSeeedDensemasterconss, setParamAggressiveDensemasterconss, setParamDefaultDensemasterconss, setParamFastDensemasterconss));
302 
305  return SCIP_OKAY;
306 }
#define DEC_ENABLEDPOSTPROCESSING
#define DEC_FREQCALLROUNDORIGINAL
#define DEC_DECL_INITDETECTOR(x)
Definition: type_detector.h:70
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
const int * getOpenconss()
returns array containing constraints not assigned yet
GCG interface methods.
SCIP_RETCODE SCIPincludeDetectorDensemasterconss(SCIP *scip)
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultDensemasterconss)
#define freeDensemasterconss
static DEC_DECL_PROPAGATESEEED(propagateSeeedDensemasterconss)
bool operator()(const std::pair< int, int > &left, const std::pair< int, int > &right)
#define DEC_DECCHAR
#define finishSeeedDensemasterconss
#define DEC_PRIORITY
#define DEC_USEFULRECALL
int getNConss()
returns the number of variables considered in the seeedpool
#define DEC_MINCALLROUND
SCIP_RETCODE flushBooked()
assigns all booked constraints and variables and deletes them from list of open cons and open vars ...
#define DEC_FREQCALLROUND
#define detectorPostprocessSeeedDensemasterconss
densemasterconss detector
various SCIP helper methods
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
#define DEC_SKIP
#define exitDensemasterconss
void addDetectorChainInfo(const char *decinfo)
adds a detectorchain information string to the corresponding vector (that carries information for eac...
#define DEC_MAXCALLROUNDORIGINAL
static DEC_DECL_SETPARAMFAST(setParamFastDensemasterconss)
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 initDensemasterconss
#define DEC_DECL_EXITDETECTOR(x)
Definition: type_detector.h:80
#define DEC_MAXCALLROUND
#define DEC_ENABLEDORIGINAL
int getNOpenconss()
returns size of vector containing constraints not assigned yet
#define DEC_LEGACYMODE
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDensemasterconss)
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_DESC
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
SCIP_RESULT result
Definition: dec_dbscan.cpp:88
#define DEC_DETECTORNAME
constraint handler for structure detection
#define DEC_MINCALLROUNDORIGINAL
#define detectDensemasterconss
#define DEC_ENABLEDFINISHING
#define DEC_ENABLED