Scippy

GCG

Branch-and-Price & Column Generation for Everyone

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-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_densemasterconss.cpp
29  * @ingroup DETECTORS
30  * @brief detector densemasterconss (put your description here)
31  * @author Michael Bastubbe
32  */
33 
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_partialdecomp.h"
39 #include "class_detprobdata.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" /**< name of detector */
54 #define DEC_DESC "detector densemasterconss" /**< description of detector*/
55 #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 */
56 #define DEC_MAXCALLROUND 0 /** last round the detector gets called */
57 #define DEC_MINCALLROUND 0 /** first round the detector gets called */
58 #define DEC_FREQCALLROUNDORIGINAL 1 /** frequency the detector gets called in detection loop while detecting the original problem */
59 #define DEC_MAXCALLROUNDORIGINAL INT_MAX /** last round the detector gets called while detecting the original problem */
60 #define DEC_MINCALLROUNDORIGINAL 0 /** first round the detector gets called while detecting the original problem */
61 #define DEC_PRIORITY 0 /**< priority of the constraint handler for separation */
62 #define DEC_DECCHAR 'd' /**< display character of detector */
63 #define DEC_ENABLED TRUE /**< should the detection be enabled */
64 #define DEC_ENABLEDFINISHING FALSE /**< should the detection be enabled */
65 #define DEC_ENABLEDPOSTPROCESSING FALSE /**< should the postprocessing be enabled */
66 #define DEC_SKIP FALSE /**< should detector be skipped if other detectors found decompositions */
67 #define DEC_USEFULRECALL FALSE /**< is it useful to call this detector on a descendant of the propagated partialdec */
68 
69 /*
70  * Data structures
71  */
72 
73 /** @todo fill in the necessary detector data */
74 
75 /** detector handler data */
76 struct DEC_DetectorData
77 {
78 };
79 
80 /*
81  * Local methods
82  */
83 
84 struct sort_pred {
85  bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
86  return left.first > right.first;
87  }
88 };
89 
90 /* put your local methods here, and declare them static */
91 
92 /*
93  * detector callback methods
94  */
95 
96 /** destructor of detector to free user data (called when GCG is exiting) */
97 #define freeDensemasterconss NULL
98 
99 /** destructor of detector to free detector data (called before the solving process begins) */
100 #define exitDensemasterconss NULL
101 
102 /** detection initialization function of detector (called before solving is about to begin) */
103 #define initDensemasterconss NULL
104 
105 #define detectDensemasterconss NULL
106 
107 #define finishPartialdecDensemasterconss NULL
108 
109 static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecDensemasterconss)
110 {
111  *result = SCIP_DIDNOTFIND;
112  char decinfo[SCIP_MAXSTRLEN];
113 
114  SCIP_CLOCK* temporaryClock;
115 
116  gcg::DETPROBDATA* detprobdata;
117  gcg::PARTIALDECOMP* partialdec = partialdecdetectiondata->workonpartialdec;
118  std::stringstream decdesc;
119 
120  SCIP_Real maxratio = 0.2;
121  int maxdiff = -1;
122  int maxdiffindex = -1;
123  int lastindex = -1;
124 
125  detprobdata = partialdecdetectiondata->detprobdata;
126 
127  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
128  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
129 
130  lastindex = maxratio * detprobdata->getNConss();
131  /* fix open conss that have a) type of the current subset or b) decomp info ONLY_MASTER as master conss */
132  std::vector<std::pair<int,int>> nnonzeros;
133  nnonzeros.reserve(detprobdata->getNConss());
134  for( int cons: partialdec->getOpenconssVec() )
135  {
136  nnonzeros[cons] = std::pair<int,int>(detprobdata->getNVarsForCons(cons), cons);
137  }
138 
139  std::sort(nnonzeros.begin(), nnonzeros.end(), sort_pred() );
140 
141  for( int i = 0; i < lastindex && i < (int) nnonzeros.size() - 1; ++i )
142  {
143  if( maxdiff < nnonzeros[i].first - nnonzeros[i+1].first )
144  {
145  maxdiff = nnonzeros[i].first - nnonzeros[i+1].first;
146  maxdiffindex = i;
147  }
148  }
149 
150  for( int i = 0; i < maxdiffindex; ++i )
151  {
152  partialdec->fixConsToMaster(nnonzeros[i].second);
153  }
154 
155  decdesc << "densemasterconss" << "\\_" << maxdiffindex ;
156 
157  partialdec->sort();
158  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, decdesc.str().c_str());
159  partialdec->addDetectorChainInfo(decinfo);
160 
161  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
162 
163  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
164  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 1) );
165  partialdecdetectiondata->nnewpartialdecs = 1;
166 
167  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "dec_densemasterconss found %d new partialdec \n", partialdecdetectiondata->nnewpartialdecs );
168 
169  partialdecdetectiondata->newpartialdecs[0] = partialdec;
170  partialdecdetectiondata->newpartialdecs[0]->addClockTime(SCIPgetClockTime(scip, temporaryClock));
171  // we used the provided partialdec -> prevent deletion
172  partialdecdetectiondata->workonpartialdec = NULL;
173 
174  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
175 
176  *result = SCIP_SUCCESS;
177 
178  return SCIP_OKAY;
179 }
180 
181 #define detectorPostprocessPartialdecDensemasterconss NULL
182 
183 static
184 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDensemasterconss)
185 {
186  char setstr[SCIP_MAXSTRLEN];
187  const char* name = DECdetectorGetName(detector);
188 
189  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
190  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
191 
192  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
193  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
194 
195  return SCIP_OKAY;
196 }
197 
198 
199 static
200 DEC_DECL_SETPARAMDEFAULT(setParamDefaultDensemasterconss)
201 {
202  char setstr[SCIP_MAXSTRLEN];
203  const char* name = DECdetectorGetName(detector);
204 
205  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
206  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
207 
208  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
209  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
210 
211  return SCIP_OKAY;
212 }
213 
214 static
215 DEC_DECL_SETPARAMFAST(setParamFastDensemasterconss)
216 {
217  char setstr[SCIP_MAXSTRLEN];
218  const char* name = DECdetectorGetName(detector);
219 
220  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
221  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
222 
223  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
224  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
225 
226 
227  return SCIP_OKAY;
228 }
229 
230 
231 /*
232  * detector specific interface methods
233  */
234 
235 /** creates the handler for densemasterconss detector and includes it in SCIP */
236 SCIP_RETCODE SCIPincludeDetectorDensemasterconss(SCIP* scip /**< SCIP data structure */
237 )
238 {
239  DEC_DETECTORDATA* detectordata;
240 
241  /**@todo create densemasterconss detector data here*/
242  detectordata = NULL;
243 
244  SCIP_CALL(
247  freeDensemasterconss, initDensemasterconss, exitDensemasterconss, propagatePartialdecDensemasterconss, finishPartialdecDensemasterconss, detectorPostprocessPartialdecDensemasterconss, setParamAggressiveDensemasterconss, setParamDefaultDensemasterconss, setParamFastDensemasterconss));
248 
249  /**@todo add densemasterconss detector parameters */
250 
251  return SCIP_OKAY;
252 }
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
int getNConss()
returns the number of variables considered in the detprobdata
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
GCG interface methods.
#define exitDensemasterconss
#define detectorPostprocessPartialdecDensemasterconss
std::vector< int >::const_iterator fixConsToMaster(std::vector< int >::const_iterator itr)
fixes a constraint to the master constraints
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
std::vector< int > & getOpenconssVec()
Gets a vector containing constraint ids not assigned yet as vector.
#define DEC_MINCALLROUND
constraint handler for structure detection
#define DEC_ENABLEDPOSTPROCESSING
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveDensemasterconss)
bool operator()(const std::pair< int, int > &left, const std::pair< int, int > &right)
#define DEC_FREQCALLROUND
#define DEC_FREQCALLROUNDORIGINAL
#define DEC_DESC
#define DEC_SKIP
#define DEC_DETECTORNAME
various SCIP helper methods
#define initDensemasterconss
#define DEC_ENABLED
#define DEC_DECCHAR
#define DEC_PRIORITY
bool sort()
sorts the vars and conss data structures by their indices
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultDensemasterconss)
SCIP_RETCODE SCIPincludeDetectorDensemasterconss(SCIP *scip)
#define freeDensemasterconss
densemasterconss detector
#define DEC_ENABLEDFINISHING
#define DEC_MAXCALLROUNDORIGINAL
class to manage partial decompositions
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)),)
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecDensemasterconss)
class storing (potentially incomplete) decompositions
#define finishPartialdecDensemasterconss
#define DEC_MINCALLROUNDORIGINAL
class storing partialdecs and the problem matrix
#define DEC_USEFULRECALL
#define DEC_MAXCALLROUND
static DEC_DECL_SETPARAMFAST(setParamFastDensemasterconss)