Scippy

GCG

Branch-and-Price & Column Generation for Everyone

dec_generalmastersetcover.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_generalmastersetcover.cpp
29  * @ingroup DETECTORS
30  * @brief detector for set covering constraints
31  * @author Michael Bastubbe
32  *
33  * This detector sets the following constraints to master:
34  * - set covering constraints
35  * - logical OR constraints
36  * - constraints with infinity rhs and nonnegative lhs
37  *
38  */
39 
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41 
43 #include "cons_decomp.h"
44 #include "class_partialdecomp.h"
45 #include "class_detprobdata.h"
46 #include "gcg.h"
47 #include "scip/cons_setppc.h"
48 #include "scip/scip.h"
49 #include "scip_misc.h"
50 #include "scip/clock.h"
51 
52 #include <iostream>
53 
54 /* constraint handler properties */
55 #define DEC_DETECTORNAME "generalmastersetcover" /**< name of detector */
56 #define DEC_DESC "detector generalmastersetcover" /**< description of detector*/
57 #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 */
58 #define DEC_MAXCALLROUND 0 /** last round the detector gets called */
59 #define DEC_MINCALLROUND 0 /** first round the detector gets called */
60 #define DEC_FREQCALLROUNDORIGINAL 1 /** frequency the detector gets called in detection loop while detecting the original problem */
61 #define DEC_MAXCALLROUNDORIGINAL 0 /** last round the detector gets called while detecting the original problem */
62 #define DEC_MINCALLROUNDORIGINAL 0 /** first round the detector gets called while detecting the original problem */
63 #define DEC_PRIORITY 0 /**< priority of the constraint handler for separation */
64 #define DEC_DECCHAR '?' /**< display character of detector */
65 #define DEC_ENABLED TRUE /**< should the detection be enabled */
66 #define DEC_ENABLEDFINISHING FALSE /**< should the finishing be enabled */
67 #define DEC_ENABLEDPOSTPROCESSING FALSE /**< should the postprocessing be enabled */
68 #define DEC_SKIP FALSE /**< should detector be skipped if other detectors found decompositions */
69 #define DEC_USEFULRECALL FALSE /**< is it useful to call this detector on a descendant of the propagated partialdec */
70 
71 /*
72  * Data structures
73  */
74 
75 /** @todo fill in the necessary detector data */
76 
77 /** detector handler data */
78 struct DEC_DetectorData
79 {
80 };
81 
82 /*
83  * Local methods
84  */
85 
86 /* put your local methods here, and declare them static */
87 
88 /*
89  * detector callback methods
90  */
91 
92 /** destructor of detector to free user data (called when GCG is exiting) */
93 #define freeGeneralmastersetcover NULL
94 
95 /** destructor of detector to free detector data (called before the solving process begins) */
96 #define exitGeneralmastersetcover NULL
97 
98 /** detection initialization function of detector (called before solving is about to begin) */
99 #define initGeneralmastersetcover NULL
100 
101 static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecGeneralmastersetcover)
102 {
103  *result = SCIP_DIDNOTFIND;
104 
105  char decinfo[SCIP_MAXSTRLEN];
106  SCIP_CLOCK* temporaryClock;
107  SCIP_CALL_ABORT(SCIPcreateClock(scip, &temporaryClock) );
108  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
109 
110  SCIP_CONS* cons;
111  SCIP_VAR** vars;
112  SCIP_Real* vals;
113  int nvars;
114  bool relevant = true;
115 
116 
117  gcg::PARTIALDECOMP* partialdec = partialdecdetectiondata->workonpartialdec;
118  auto& openconss = partialdec->getOpenconssVec();
119  for( auto itr = openconss.cbegin(); itr != openconss.cend(); )
120  {
121  bool found = false;
122  cons = partialdecdetectiondata->detprobdata->getCons(*itr);
123 
124  /* set open setcovering and logicor constraints to master */
125  if( GCGconsGetType(scip, cons) == setcovering || GCGconsGetType(scip, cons) == logicor )
126  {
127  itr = partialdec->fixConsToMaster(itr);
128  found = true;
129  }
130  /* set constraints with infinity rhs and nonnegative lhs to master */
131  else if(GCGconsGetType(scip, cons) != logicor && GCGconsGetType(scip, cons) != setpacking && GCGconsGetType(scip, cons) != setpartitioning )
132  {
133  nvars = GCGconsGetNVars(scip, cons);
134  vars = NULL;
135  vals = NULL;
136  if( !SCIPisInfinity(scip, GCGconsGetRhs(scip, cons)) )
137  relevant = false;
138  if( SCIPisNegative(scip, GCGconsGetLhs(scip, cons)) )
139  relevant = false;
140  if( nvars > 0 )
141  {
142  SCIP_CALL( SCIPallocMemoryArray(scip, &vars, nvars) );
143  SCIP_CALL( SCIPallocMemoryArray(scip, &vals, nvars) );
144  SCIP_CALL( GCGconsGetVars(scip, cons, vars, nvars) );
145  SCIP_CALL( GCGconsGetVals(scip, cons, vals, nvars) );
146  }
147  for( int j = 0; j < nvars && relevant; ++j )
148  {
149  assert(vars != NULL);
150  assert(vals != NULL);
151 
152  if( !SCIPvarIsIntegral(vars[j]) && !SCIPvarIsBinary(vars[j]) )
153  {
154  SCIPdebugPrintf("(%s is not integral) ", SCIPvarGetName(vars[j]) );
155  relevant = FALSE;
156  }
157  if( !SCIPisEQ(scip, vals[j], 1.0) )
158  {
159  SCIPdebugPrintf("(coeff for var %s is %.2f != 1.0) ", SCIPvarGetName(vars[j]), vals[j] );
160  relevant = FALSE;
161  }
162  }
163  SCIPfreeMemoryArrayNull(scip, &vals);
164  SCIPfreeMemoryArrayNull(scip, &vars);
165 
166  if(relevant)
167  {
168  itr = partialdec->fixConsToMaster(itr);
169  found = true;
170  }
171  }
172  if( !found )
173  {
174  ++itr;
175  }
176  }
177 
178  partialdec->sort();
179  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
180 
181  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
182  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 1) );
183  partialdecdetectiondata->newpartialdecs[0] = partialdec;
184  partialdecdetectiondata->nnewpartialdecs = 1;
185  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "genmastersetcover");
186  partialdecdetectiondata->newpartialdecs[0]->addDetectorChainInfo(decinfo);
187  partialdecdetectiondata->newpartialdecs[0]->addClockTime(SCIPgetClockTime(scip, temporaryClock));
188  // we used the provided partialdec -> prevent deletion
189  partialdecdetectiondata->workonpartialdec = NULL;
190  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
191 
192  *result = SCIP_SUCCESS;
193 
194  return SCIP_OKAY;
195 }
196 
197 #define finishPartialdecGeneralmastersetcover NULL
198 #define detectorPostprocessPartialdecGeneralmastersetcover NULL
199 
200 static
201 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveGeneralmastersetcover)
202 {
203  char setstr[SCIP_MAXSTRLEN];
204  const char* name = DECdetectorGetName(detector);
205  int newval;
206 
207  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
208  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
209 
210  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
211  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
212 
213  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxcallround", name);
214  SCIP_CALL( SCIPgetIntParam(scip, setstr, &newval) );
215  ++newval;
216  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
217  SCIPinfoMessage(scip, NULL, "After Setting %s = %d\n", setstr, newval);
218 
219  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origmaxcallround", name);
220  SCIP_CALL( SCIPgetIntParam(scip, setstr, &newval) );
221  ++newval;
222  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
223  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
224 
225  return SCIP_OKAY;
226 }
227 
228 
229 static
230 DEC_DECL_SETPARAMDEFAULT(setParamDefaultGeneralmastersetcover)
231 {
232  char setstr[SCIP_MAXSTRLEN];
233 
234  const char* name = DECdetectorGetName(detector);
235 
236  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
237  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
238 
239  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
240  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
241 
242  return SCIP_OKAY;
243 }
244 
245 static
246 DEC_DECL_SETPARAMFAST(setParamFastGeneralmastersetcover)
247 {
248  char setstr[SCIP_MAXSTRLEN];
249 
250  const char* name = DECdetectorGetName(detector);
251 
252  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
253  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
254 
255  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
256  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
257 
258  return SCIP_OKAY;
259 }
260 
261 
262 
263 /*
264  * detector specific interface methods
265  */
266 
267 /** creates the handler for generalmastersetcover detector and includes it in SCIP */
268 SCIP_RETCODE SCIPincludeDetectorGeneralmastersetcover(SCIP* scip /**< SCIP data structure */
269 )
270 {
271  DEC_DETECTORDATA* detectordata;
272 
273  /**@todo create generalmastersetcover detector data here*/
274  detectordata = NULL;
275 
276  SCIP_CALL(
280  detectordata, freeGeneralmastersetcover, initGeneralmastersetcover, exitGeneralmastersetcover, propagatePartialdecGeneralmastersetcover, finishPartialdecGeneralmastersetcover, detectorPostprocessPartialdecGeneralmastersetcover, setParamAggressiveGeneralmastersetcover, setParamDefaultGeneralmastersetcover, setParamFastGeneralmastersetcover));
281 
282  /**@todo add generalmastersetcover detector parameters */
283 
284  return SCIP_OKAY;
285 }
286 
287 
288 
289 
290 
291 
292 
293 
294 
#define freeGeneralmastersetcover
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
SCIP_Real GCGconsGetRhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:108
GCG interface methods.
#define initGeneralmastersetcover
std::vector< int >::const_iterator fixConsToMaster(std::vector< int >::const_iterator itr)
fixes a constraint to the master constraints
SCIP_Real GCGconsGetLhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:206
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
@ logicor
Definition: scip_misc.h:49
std::vector< int > & getOpenconssVec()
Gets a vector containing constraint ids not assigned yet as vector.
constraint handler for structure detection
#define DEC_ENABLEDPOSTPROCESSING
#define finishPartialdecGeneralmastersetcover
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:490
#define DEC_MINCALLROUND
#define DEC_SKIP
#define DEC_DECCHAR
various SCIP helper methods
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveGeneralmastersetcover)
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultGeneralmastersetcover)
#define DEC_MAXCALLROUNDORIGINAL
#define DEC_DESC
bool sort()
sorts the vars and conss data structures by their indices
@ setpacking
Definition: scip_misc.h:48
generalmastersetcover detector
@ setpartitioning
Definition: scip_misc.h:48
consType GCGconsGetType(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:51
#define DEC_ENABLED
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:621
#define DEC_FREQCALLROUNDORIGINAL
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:434
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecGeneralmastersetcover)
#define DEC_FREQCALLROUND
class to manage partial decompositions
SCIP_RETCODE SCIPincludeDetectorGeneralmastersetcover(SCIP *scip)
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)),)
#define DEC_PRIORITY
#define DEC_MAXCALLROUND
class storing (potentially incomplete) decompositions
#define DEC_DETECTORNAME
static DEC_DECL_SETPARAMFAST(setParamFastGeneralmastersetcover)
#define exitGeneralmastersetcover
#define detectorPostprocessPartialdecGeneralmastersetcover
#define DEC_USEFULRECALL
class storing partialdecs and the problem matrix
@ setcovering
Definition: scip_misc.h:48
#define DEC_ENABLEDFINISHING
#define DEC_MINCALLROUNDORIGINAL