Scippy

GCG

Branch-and-Price & Column Generation for Everyone

dec_connected_noNewLinkingVars.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_connected_noNewLinkingVars.cpp
29  * @ingroup DETECTORS
30  * @brief detector connected_noNewLinkingVars (assigns all dependent open conss and vars and 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 
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 "connected_nonewlinkingvars" /**< name of detector */
51 #define DEC_DESC "detector connected_noNewLinkingVars" /**< 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_FREQCALLROUNDORIGINAL 1 /** frequency the detector gets called in detection loop while detecting the original problem */
56 #define DEC_MAXCALLROUNDORIGINAL INT_MAX /** last round the detector gets called while detecting the original problem */
57 #define DEC_MINCALLROUNDORIGINAL 0 /** first round the detector gets called while detecting the original problem */
58 #define DEC_PRIORITY 0 /**< priority of the constraint handler for separation */
59 #define DEC_DECCHAR '?' /**< display character of detector */
60 #define DEC_ENABLED FALSE /**< should the detection be enabled */
61 #define DEC_ENABLEDFINISHING FALSE /**< 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 
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 /*
86  * detector callback methods
87  */
88 
89 /** destructor of detector to free user data (called when GCG is exiting) */
90 #define freeConnected_noNewLinkingVars NULL
91 
92 /** destructor of detector to free detector data (called before the solving process begins) */
93 #define exitConnected_noNewLinkingVars NULL
94 
95 /** detection initialization function of detector (called before solving is about to begin) */
96 #define initConnected_noNewLinkingVars NULL
97 
98 
99 
100 /** detection function for partialdecs */
101 static
102 SCIP_RETCODE detection(
103  SCIP* scip, /**< SCIP data structure */
104  Partialdec_Detection_Data* partialdecdetectiondata /**< partialdecdetectiondata (including the detprobdata and workonpartialdec) where to store the new Partialdecs */
105 )
106 {
107  SCIP_CLOCK* temporaryClock;
108  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
109  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
110 
111  gcg::PARTIALDECOMP* partialdec = partialdecdetectiondata->workonpartialdec;
112 
113  partialdec->considerImplicits();
114 
115  //assign all dependent open vars and conss
116  partialdec->refineToBlocks();
117 
118  //complete the partialdec by bfs
119  partialdec->completeByConnected();
120 
121  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock) );
122 
123  partialdecdetectiondata->detectiontime = SCIPgetClockTime(scip, temporaryClock);
124  partialdecdetectiondata->nnewpartialdecs = 1;
125  SCIP_CALL( SCIPallocMemoryArray(scip, &(partialdecdetectiondata->newpartialdecs), 1) );
126  partialdecdetectiondata->newpartialdecs[0] = partialdec;
127  partialdecdetectiondata->newpartialdecs[0]->addDetectorChainInfo(DEC_DETECTORNAME);
128  partialdecdetectiondata->newpartialdecs[0]->addClockTime(SCIPgetClockTime(scip, temporaryClock));
129  // we used the provided partialdec -> prevent deletion
130  partialdecdetectiondata->workonpartialdec = NULL;
131  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
132 
133  return SCIP_OKAY;
134 }
135 
136 
137 static
138 DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecConnected_noNewLinkingVars)
139 {
140  *result = SCIP_DIDNOTFIND;
141  detection(scip, partialdecdetectiondata);
142  *result = SCIP_SUCCESS;
143 
144  return SCIP_OKAY;
145 }
146 
147 static
148 DEC_DECL_FINISHPARTIALDEC(finishPartialdecConnected_noNewLinkingVars)
149 {
150  *result = SCIP_DIDNOTFIND;
151  detection(scip, partialdecdetectiondata);
152  *result = SCIP_SUCCESS;
153 
154  return SCIP_OKAY;
155 }
156 #define detectorPostprocessPartialdecConnected_noNewLinkingVars NULL
157 
158 
159 #define setParamAggressiveConnected_noNewLinkingVars NULL
160 #define setParamDefaultConnected_noNewLinkingVars NULL
161 #define setParamFastConnected_noNewLinkingVars NULL
162 
163 
164 
165 /*
166  * detector specific interface methods
167  */
168 
169 /** creates the handler for connected_noNewLinkingVars detector and includes it in SCIP */
171  SCIP* scip /**< SCIP data structure */
172  )
173 {
174  DEC_DETECTORDATA* detectordata;
175 
176  /**@todo create connected_noNewLinkingVars detector data here*/
177  detectordata = NULL;
178 
180 
181  /**@todo add connected_noNewLinkingVars detector parameters */
182 
183  return SCIP_OKAY;
184 }
#define DEC_MAXCALLROUNDORIGINAL
void addClockTime(SCIP_Real clocktime)
adds detection time of one detector
#define DEC_MAXCALLROUND
GCG interface methods.
void addDetectorChainInfo(const char *decinfo)
add information about the detector chain
#define DEC_FREQCALLROUND
constraint handler for structure detection
#define setParamFastConnected_noNewLinkingVars
SCIP_RETCODE SCIPincludeDetectorConnected_noNewLinkingVars(SCIP *scip)
#define initConnected_noNewLinkingVars
void completeByConnected()
assigns all open constraints and open variables
various SCIP helper methods
void considerImplicits()
: assigns every open cons/var
#define DEC_ENABLEDPOSTPROCESSING
#define DEC_ENABLEDFINISHING
interface data structure for the detector calling methods
connected_noNewLinkingVars detector
void refineToBlocks()
refine partialdec with focus on blocks
#define setParamAggressiveConnected_noNewLinkingVars
static DEC_DECL_PROPAGATEPARTIALDEC(propagatePartialdecConnected_noNewLinkingVars)
static SCIP_RETCODE detection(SCIP *scip, Partialdec_Detection_Data *partialdecdetectiondata)
#define DEC_FREQCALLROUNDORIGINAL
class to manage partial decompositions
gcg::PARTIALDECOMP ** newpartialdecs
#define DEC_MINCALLROUNDORIGINAL
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 exitConnected_noNewLinkingVars
class storing (potentially incomplete) decompositions
#define DEC_USEFULRECALL
#define DEC_MINCALLROUND
#define detectorPostprocessPartialdecConnected_noNewLinkingVars
#define setParamDefaultConnected_noNewLinkingVars
#define DEC_DETECTORNAME
static DEC_DECL_FINISHPARTIALDEC(finishPartialdecConnected_noNewLinkingVars)
class storing partialdecs and the problem matrix
#define freeConnected_noNewLinkingVars
gcg::PARTIALDECOMP * workonpartialdec