Scippy

GCG

Branch-and-Price & Column Generation for Everyone

event_mastersol.c
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 event_mastersol.c
29  * @brief eventhdlr to transfer solutions found in the original problem to the master problem
30  * @author Christian Puchert
31  */
32 
33 /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include <string.h>
36 #include "event_mastersol.h"
37 #include "pricer_gcg.h"
38 #include "gcg.h"
39 #include "relax_gcg.h"
40 #include "event_relaxsol.h"
41 
42 #define EVENTHDLR_NAME "mastersol"
43 #define EVENTHDLR_DESC "event handler to to transfer solutions found in the original problem to the master problem"
44 
45 
46 /*
47  * Data structures
48  */
49 
50 /** event handler data */
52 {
53  SCIP_Bool triggered; /**< flag to indicate whether event has been triggered */
54 };
55 
56 
57 /*
58  * Callback methods of event handler
59  */
60 
61 /** destructor of event handler to free user data (called when SCIP is exiting) */
62 static
63 SCIP_DECL_EVENTFREE(eventFreeMastersol)
64 { /*lint --e{715}*/
65  SCIP_EVENTHDLRDATA* eventhdlrdata;
66 
67  assert(scip != NULL);
68  assert(eventhdlr != NULL);
69  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
70 
71  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
72  assert(eventhdlrdata != NULL);
73 
74  SCIPfreeMemory(scip, &eventhdlrdata);
75  SCIPeventhdlrSetData(eventhdlr, NULL);
76 
77  return SCIP_OKAY;
78 }
79 
80 /** initialization method of event handler (called after problem was transformed) */
81 static
82 SCIP_DECL_EVENTINIT(eventInitMastersol)
83 { /*lint --e{715}*/
84  SCIP_EVENTHDLRDATA* eventhdlrdata;
85 
86  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
87  assert(eventhdlrdata != NULL);
88 
89  /* notify SCIP that your event handler wants to react on the event types best solution found and node solved */
90  SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, NULL, NULL) );
91  eventhdlrdata->triggered = FALSE;
92 
93  return SCIP_OKAY;
94 }
95 
96 /** deinitialization method of event handler (called before transformed problem is freed) */
97 static
98 SCIP_DECL_EVENTEXIT(eventExitMastersol)
99 { /*lint --e{715}*/
100 
101  /* notify SCIP that your event handler wants to drop the event types best solution found and node solved */
102  SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_SOLFOUND, eventhdlr, NULL, -1) );
103 
104  return SCIP_OKAY;
105 }
106 
107 /** execution method of event handler */
108 static
109 SCIP_DECL_EVENTEXEC(eventExecMastersol)
110 { /*lint --e{715}*/
111  SCIP* masterprob;
112  SCIP_EVENTHDLRDATA* eventhdlrdata;
113  SCIP_SOL* sol;
114  SCIP_Bool discretization;
115 
116  assert(scip != NULL);
117  assert(eventhdlr != NULL);
118  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
119 
120  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
121  assert(eventhdlrdata != NULL);
122 
123  /* get new primal solution */
124  sol = SCIPeventGetSol(event);
125  assert(sol != NULL);
126 
127  /* get master problem */
128  masterprob = GCGgetMasterprob(scip);
129  assert(masterprob != NULL);
130 
131  eventhdlrdata->triggered = TRUE;
132 
133  /* get discretization parameter */
134  SCIP_CALL( SCIPgetBoolParam(scip, "relaxing/gcg/discretization", &discretization) );
135 
136  /* transfer solution to the master problem; ensure that
137  * * SCIP instances are in correct stages
138  * * the original solution does not already come from the master
139  * * Dantzig-Wolfe decomposition is being used
140  *
141  * NOTE: Care must be taken with the event handlers. When BENDERS or ORIGINAL mode is used, the relaxation solution
142  * event handler is not included. So GCGeventhdlrRelaxsolIsTriggered will always return FALSE.
143  */
144  if( SCIPgetStage(scip) > SCIP_STAGE_TRANSFORMED && SCIPgetStage(masterprob) > SCIP_STAGE_TRANSFORMED &&
145  SCIPgetStage(masterprob) < SCIP_STAGE_SOLVED &&
146  !GCGeventhdlrRelaxsolIsTriggered(scip, masterprob) &&
147  (SCIPsolGetHeur(sol) != NULL || discretization) && /* @todo: This check is possibly not needed anymore */
149  {
150  SCIPdebugMessage("Original feasible solution found by <%s> -- transferring to master problem\n",
151  SCIPsolGetHeur(sol) == NULL ? "relaxation" : SCIPheurGetName(SCIPsolGetHeur(sol)));
152  SCIP_CALL( GCGmasterTransOrigSolToMasterVars(masterprob, sol, NULL) );
153  }
154 
155  eventhdlrdata->triggered = FALSE;
156 
157  return SCIP_OKAY;
158 }
159 
160 /** creates event handler for mastersol event */
162  SCIP* scip /**< SCIP data structure */
163  )
164 {
165  SCIP_EVENTHDLR* eventhdlr;
166  SCIP_EVENTHDLRDATA* eventhdlrdata;
167 
168  eventhdlr = NULL;
169 
170  SCIP_CALL( SCIPallocMemory(scip, &eventhdlrdata) );
171  assert(eventhdlrdata != NULL);
172 
173  /* include event handler into SCIP */
174  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
175  eventExecMastersol, eventhdlrdata) );
176  assert(eventhdlr != NULL);
177 
178  /* set non fundamental callbacks via setter functions */
179  SCIP_CALL( SCIPsetEventhdlrFree(scip, eventhdlr, eventFreeMastersol) );
180  SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitMastersol) );
181  SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitMastersol) );
182 
183  return SCIP_OKAY;
184 }
185 
186 /** return whether event has been triggered */
188  SCIP* scip /**< SCIP data structure */
189  )
190 {
191  SCIP_EVENTHDLR* eventhdlr;
192  SCIP_EVENTHDLRDATA* eventhdlrdata;
193 
194  assert(scip != NULL);
195 
196  eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
197  assert(eventhdlr != NULL);
198 
199  eventhdlrdata = SCIPeventhdlrGetData(eventhdlr);
200  assert(eventhdlrdata != NULL);
201 
202  return eventhdlrdata->triggered;
203 }
static SCIP_DECL_EVENTEXIT(eventExitMastersol)
#define EVENTHDLR_NAME
@ DEC_DECMODE_BENDERS
Definition: type_decomp.h:62
static SCIP_DECL_EVENTFREE(eventFreeMastersol)
GCG interface methods.
static SCIP_DECL_EVENTINIT(eventInitMastersol)
@ DEC_DECMODE_ORIGINAL
Definition: type_decomp.h:63
SCIP_RETCODE SCIPincludeEventHdlrMastersol(SCIP *scip)
GCG variable pricer.
SCIP_Bool GCGeventhdlrRelaxsolIsTriggered(SCIP *scip, SCIP *masterprob)
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
SCIP_Bool GCGeventhdlrMastersolIsTriggered(SCIP *scip)
DEC_DECMODE GCGgetDecompositionMode(SCIP *scip)
Definition: relax_gcg.c:5123
SCIP_RETCODE GCGmasterTransOrigSolToMasterVars(SCIP *scip, SCIP_SOL *origsol, SCIP_Bool *stored)
#define EVENTHDLR_DESC
eventhdlr to transfer solutions found in the original problem to the master problem
static SCIP_DECL_EVENTEXEC(eventExecMastersol)
eventhandler to update the relaxation solution in the original problem when the master LP has been so...
GCG relaxator.