cons_integralorig.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-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 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 /* #define SCIP_DEBUG */
37 #include <assert.h>
38 #include <string.h>
39 
40 #include "cons_integralorig.h"
41 #include "pricer_gcg.h"
42 #include "cons_masterbranch.h"
43 #include "pub_gcgvar.h"
44 #include "scip/struct_branch.h"
45 #include "relax_gcg.h"
46 #include "gcg.h"
47 
48 #include "branch_orig.h"
49 
50 #define CONSHDLR_NAME "integralorig"
51 #define CONSHDLR_DESC "integrality constraint"
52 #define CONSHDLR_ENFOPRIORITY 1000
53 #define CONSHDLR_CHECKPRIORITY 1000
54 #define CONSHDLR_EAGERFREQ -1
56 #define CONSHDLR_NEEDSCONS FALSE
60 struct SCIP_ConshdlrData
61 {
62  SCIP_BRANCHRULE** branchrules;
63  int nbranchrules;
64 };
65 
68  SCIP* scip,
69  SCIP_BRANCHRULE* branchrule
70  )
71 {
72  SCIP_CONSHDLR* conshdlr;
73  SCIP_CONSHDLRDATA* conshdlrdata;
74 
75  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
76  assert(conshdlr != NULL);
77 
78  conshdlrdata = SCIPconshdlrGetData(conshdlr);
79  assert(conshdlrdata != NULL);
80 
81  assert(conshdlrdata->nbranchrules >= 0);
82  if( conshdlrdata->nbranchrules == 0 )
83  {
84  SCIP_CALL( SCIPallocMemoryArray(scip, &(conshdlrdata->branchrules), 1) ); /*lint !e506*/
85  conshdlrdata->nbranchrules = 1;
86  }
87  else
88  {
89  SCIP_CALL( SCIPreallocMemoryArray(scip, &(conshdlrdata->branchrules), (size_t)conshdlrdata->nbranchrules+1) );
90  ++conshdlrdata->nbranchrules;
91  }
92 
93  assert(conshdlrdata->nbranchrules > 0);
94 
95  conshdlrdata->branchrules[conshdlrdata->nbranchrules-1] = branchrule;
96 
97  return SCIP_OKAY;
98 }
99 
101 static
102 void sortBranchrules(
103  SCIP_BRANCHRULE** branchrules,
104  int nbranchrules
105  )
106 {
107  SCIP_BRANCHRULE* tmp;
108  int pos;
109  int i;
110 
111  tmp = NULL;
112 
113  assert(nbranchrules >= 0);
114  assert(branchrules != NULL);
115 
116  for( pos=0; pos<nbranchrules; ++pos )
117  {
118  int maxi = pos;
119  for( i=pos+1; i<nbranchrules; ++i )
120  {
121  if( branchrules[i]->priority > branchrules[maxi]->priority )
122  {
123  maxi = i;
124  }
125  }
126  if( maxi != pos )
127  {
128  tmp = branchrules[pos];
129  branchrules[pos] = branchrules[maxi];
130  branchrules[maxi] = tmp;
131  }
132  }
133 }
134 
135 /*
136  * Callback methods
137  */
138 
140 static
141 SCIP_DECL_CONSENFOLP(consEnfolpIntegralOrig)
142 { /*lint --e{715}*/
143  SCIP* origprob;
144  SCIP_Bool discretization;
145  int i;
146  SCIP_CONSHDLRDATA* conshdlrdata;
147 
148  assert(conshdlr != NULL);
149  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
150  assert(scip != NULL);
151  assert(conss == NULL);
152  assert(nconss == 0);
153  assert(result != NULL);
154  assert(conshdlr != NULL);
155  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
156  assert(scip != NULL);
157 
158  origprob = GCGmasterGetOrigprob(scip);
159  assert(origprob != NULL);
160  conshdlrdata = SCIPconshdlrGetData(conshdlr);
161  assert(conshdlrdata != NULL);
162 
163  SCIPdebugMessage("LP solution enforcing method of integralorig constraint\n");
164 
165  *result = SCIP_FEASIBLE;
166 
167  /* if we use the discretization without continuous variables, we do not have to check for integrality of the solution in the
168  * original variable space, we obtain it by enforcing integrality of the master solution*/
169  SCIP_CALL( SCIPgetBoolParam(origprob, "relaxing/gcg/discretization", &discretization) );
170  if( discretization && SCIPgetNContVars(origprob) == 0 )
171  {
172  return SCIP_OKAY;
173  }
174 
175  /* if the transferred master solution is feasible, the current node is solved to optimality and can be pruned */
176  if( GCGrelaxIsOrigSolFeasible(origprob) )
177  {
178  SCIPdebugMessage("Orig sol is feasible\n");
179  *result = SCIP_FEASIBLE;
180  return SCIP_OKAY;
181  }
182 
183  sortBranchrules(conshdlrdata->branchrules, conshdlrdata->nbranchrules);
184 
185  i = 0;
186 
187  while( *result != SCIP_BRANCHED && i < conshdlrdata->nbranchrules )
188  {
189  assert(conshdlrdata->branchrules[i] != NULL);
190 
191  if( conshdlrdata->branchrules[i]->branchexeclp == NULL )
192  {
193  ++i;
194  continue;
195  }
196 
197  SCIPdebugMessage("Call exec lp method of %s\n", SCIPbranchruleGetName(conshdlrdata->branchrules[i]));
199  SCIP_CALL( conshdlrdata->branchrules[i]->branchexeclp(scip, conshdlrdata->branchrules[i], TRUE, result) );
200  ++i;
201  }
202 
203  return SCIP_OKAY;
204 
205 }
206 
207 
209 static
210 SCIP_DECL_CONSENFOPS(consEnfopsIntegralOrig)
211 { /*lint --e{715}*/
212  SCIP* origprob;
213  SCIP_Bool discretization;
214  SCIP_CONSHDLRDATA* conshdlrdata;
215  int i;
216 
217  assert(conshdlr != NULL);
218  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
219  assert(scip != NULL);
220  assert(conss == NULL);
221  assert(nconss == 0);
222  assert(result != NULL);
223 
224  origprob = GCGmasterGetOrigprob(scip);
225  assert(origprob != NULL);
226  conshdlrdata = SCIPconshdlrGetData(conshdlr);
227  assert(conshdlrdata != NULL);
228 
229  *result = SCIP_FEASIBLE;
230  i = 0;
231 
232  /* if we use the discretization without continuous variables, we do not have to check for integrality of the solution in the
233  * original variable space, we obtain it by enforcing integrality of the master solution*/
234  SCIP_CALL( SCIPgetBoolParam(origprob, "relaxing/gcg/discretization", &discretization) );
235  if( discretization && SCIPgetNContVars(origprob) == 0 )
236  {
237  return SCIP_OKAY;
238  }
239 
240  assert(SCIPgetNPseudoBranchCands(origprob) > 0);
241 
242  sortBranchrules(conshdlrdata->branchrules, conshdlrdata->nbranchrules);
243 
244  while( *result != SCIP_BRANCHED && i < conshdlrdata->nbranchrules )
245  {
246  assert(conshdlrdata->branchrules[i] != NULL);
247 
248  if( conshdlrdata->branchrules[i]->branchexecps == NULL )
249  {
250  ++i;
251  continue;
252  }
254  SCIP_CALL( conshdlrdata->branchrules[i]->branchexecps(scip, conshdlrdata->branchrules[i], TRUE, result) );
255  ++i;
256  }
257 
258  return SCIP_OKAY;
259 }
260 
261 
263 static
264 SCIP_DECL_CONSCHECK(consCheckIntegralOrig)
265 { /*lint --e{715}*/
266  SCIP* origprob;
267  SCIP_SOL* origsol;
268  SCIP_VAR** origvars;
269  int norigvars;
270  SCIP_Real solval;
271  SCIP_Bool discretization;
272  int v;
273 
274  assert(conshdlr != NULL);
275  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
276  assert(scip != NULL);
277 
278  origprob = GCGmasterGetOrigprob(scip);
279  assert(origprob != NULL);
280 
281  SCIPdebugMessage("Check method of integralorig constraint\n");
282 
283  *result = SCIP_FEASIBLE;
284 
285  /* if we use the discretization without continuous variables, we do not have to check for integrality of the solution in the
286  * original variable space, we obtain it by enforcing integrality of the master solution*/
287  SCIP_CALL( SCIPgetBoolParam(origprob, "relaxing/gcg/discretization", &discretization) );
288  if( discretization && SCIPgetNContVars(origprob) == 0 )
289  {
290  return SCIP_OKAY;
291  }
292 
294  SCIP_CALL( GCGtransformMastersolToOrigsol(origprob, sol, &origsol) );
295 
296  origvars = SCIPgetOrigVars(origprob);
297  norigvars = SCIPgetNOrigVars(origprob);
298 
299  /* check for each integral original variable whether it has a fractional value */
300  for( v = 0; v < norigvars && *result == SCIP_FEASIBLE; v++ )
301  {
302  if( SCIPvarGetType(origvars[v]) == SCIP_VARTYPE_CONTINUOUS )
303  continue;
304 
305  solval = 0.0;
306  assert(GCGvarIsOriginal(origvars[v]));
307 
308  solval = SCIPgetSolVal(origprob, origsol, origvars[v]);
309 
310  if( !SCIPisFeasIntegral(origprob, solval) )
311  {
312  *result = SCIP_INFEASIBLE;
313 
314  if( printreason )
315  {
316  SCIPinfoMessage(scip, NULL, "violation: integrality condition of variable <%s> = %.15g\n",
317  SCIPvarGetName(origvars[v]), solval);
318  }
319  }
320  }
321 
322  SCIPfreeSol(origprob, &origsol);
323 
324  return SCIP_OKAY;
325 }
326 
327 
329 static
330 SCIP_DECL_CONSLOCK(consLockIntegralOrig)
331 { /*lint --e{715}*/
332  return SCIP_OKAY;
333 }
334 
336 static
337 SCIP_DECL_CONSFREE(consFreeIntegralOrig)
338 {
339  SCIP_CONSHDLRDATA* conshdlrdata;
340 
341  assert(scip != NULL);
342  assert(conshdlr != NULL);
343  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
344 
345  conshdlrdata = SCIPconshdlrGetData(conshdlr);
346  assert(conshdlrdata != NULL);
347 
348  SCIPdebugMessage("freeing integralorig constraint handler\n");
349 
350  if( conshdlrdata->nbranchrules > 0 )
351  {
352  assert(conshdlrdata->branchrules != NULL);
353  SCIPfreeMemoryArray(scip, &(conshdlrdata->branchrules) );
354  conshdlrdata->branchrules = NULL;
355  conshdlrdata->nbranchrules = 0;
356  }
357 
358  /* free constraint handler storage */
359  assert(conshdlrdata->branchrules == NULL);
360  SCIPfreeMemory(scip, &conshdlrdata);
361 
362  return SCIP_OKAY;
363 }
364 
365 /*
366  * constraint specific interface methods
367  */
368 
371  SCIP* scip
372  )
373 {
374  SCIP_CONSHDLR* conshdlr;
375  SCIP_CONSHDLRDATA* conshdlrdata;
376 
377  /* create integral constraint handler data */
378  conshdlrdata = NULL;
379  SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
380  conshdlrdata->branchrules = NULL;
381  conshdlrdata->nbranchrules = 0;
382 
383  /* include constraint handler */
384  SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
386  consEnfolpIntegralOrig, consEnfopsIntegralOrig, consCheckIntegralOrig, consLockIntegralOrig,
387  conshdlrdata) );
388  assert(conshdlr != NULL);
389 
390  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeIntegralOrig) );
391 
392  return SCIP_OKAY;
393 }
static void sortBranchrules(SCIP_BRANCHRULE **branchrules, int nbranchrules)
static SCIP_DECL_CONSCHECK(consCheckIntegralOrig)
SCIP_RETCODE GCGconsIntegralorigAddBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule)
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:162
branching rule for original problem in GCG
GCG interface methods.
#define CONSHDLR_EAGERFREQ
static SCIP_DECL_CONSENFOLP(consEnfolpIntegralOrig)
#define CONSHDLR_NAME
#define CONSHDLR_NEEDSCONS
static SCIP_DECL_CONSENFOPS(consEnfopsIntegralOrig)
constraint handler for the integrality constraint
SCIP_RETCODE SCIPincludeConshdlrIntegralOrig(SCIP *scip)
#define CONSHDLR_DESC
GCG relaxator.
GCG variable pricer.
SCIP * GCGmasterGetOrigprob(SCIP *scip)
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4112
public methods for GCG variables
constraint handler for storing the branching decisions at each node of the tree
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_ENFOPRIORITY
static SCIP_DECL_CONSLOCK(consLockIntegralOrig)
static SCIP_DECL_CONSFREE(consFreeIntegralOrig)
SCIP_RETCODE GCGtransformMastersolToOrigsol(SCIP *scip, SCIP_SOL *mastersol, SCIP_SOL **origsol)
Definition: misc.c:124