sepa_master.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 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include <assert.h>
36 #include <stdio.h>
37 #include <string.h>
38 
39 #include "scip/scip.h"
40 #include "scip/lp.h"
41 #include "sepa_master.h"
42 #include "gcg.h"
43 #include "relax_gcg.h"
44 #include "pricer_gcg.h"
45 
46 
47 #define SEPA_NAME "master"
48 #define SEPA_DESC "separator for separating cuts in the original problem, called in the master"
49 #define SEPA_PRIORITY 1000
50 
51 #define SEPA_FREQ 1
52 #define SEPA_MAXBOUNDDIST 1.0
53 #define SEPA_USESSUBSCIP FALSE
54 #define SEPA_DELAY FALSE
56 #define STARTMAXCUTS 50
57 #define MAXCUTSINC 20
60 /*
61  * Data structures
62  */
63 
65 struct SCIP_SepaData
66 {
67  SCIP_ROW** mastercuts;
68  SCIP_ROW** origcuts;
69  int ncuts;
70  int maxcuts;
71  SCIP_Bool enable;
72  int separationsetting;
73 };
74 
75 
76 /*
77  * Local methods
78  */
79 
80 
82 static
83 SCIP_RETCODE ensureSizeCuts(
84  SCIP* scip,
85  SCIP_SEPADATA* sepadata,
86  int size
87  )
88 {
89  assert(scip != NULL);
90  assert(sepadata != NULL);
91  assert(sepadata->mastercuts != NULL);
92  assert(sepadata->origcuts != NULL);
93  assert(sepadata->ncuts <= sepadata->maxcuts);
94  assert(sepadata->ncuts >= 0);
95 
96  if( sepadata->maxcuts < size )
97  {
98  while ( sepadata->maxcuts < size )
99  {
100  sepadata->maxcuts += MAXCUTSINC;
101  }
102  SCIP_CALL( SCIPreallocMemoryArray(scip, &(sepadata->mastercuts), sepadata->maxcuts) );
103  SCIP_CALL( SCIPreallocMemoryArray(scip, &(sepadata->origcuts), sepadata->maxcuts) );
104  }
105  assert(sepadata->maxcuts >= size);
106 
107  return SCIP_OKAY;
108 }
109 
110 /*
111  * Callback methods of separator
112  */
113 
114 #define sepaCopyMaster NULL
115 #define sepaInitMaster NULL
116 #define sepaInitsolMaster NULL
117 #define sepaExecsolMaster NULL
118 
120 static
121 SCIP_DECL_SEPAFREE(sepaFreeMaster)
122 {
123  SCIP_SEPADATA* sepadata;
124 
125  sepadata = SCIPsepaGetData(sepa);
126 
127  SCIPfreeMemoryArray(scip, &(sepadata->origcuts));
128  SCIPfreeMemoryArray(scip, &(sepadata->mastercuts));
129 
130  SCIPfreeMemory(scip, &sepadata);
131 
132  return SCIP_OKAY;
133 }
134 
136 static
137 SCIP_DECL_SEPAEXIT(sepaExitMaster)
138 {
139  SCIP* origscip;
140  SCIP_SEPADATA* sepadata;
141  int i;
142 
143  sepadata = SCIPsepaGetData(sepa);
144  assert(sepadata != NULL);
145 
146  origscip = GCGmasterGetOrigprob(scip);
147  assert(origscip != NULL);
148 
149  for( i = 0; i < sepadata->ncuts; i++ )
150  {
151  SCIP_CALL( SCIPreleaseRow(origscip, &(sepadata->origcuts[i])) );
152  }
153 
154  sepadata->ncuts = 0;
155 
156  return SCIP_OKAY;
157 }
158 
160 static
161 SCIP_DECL_SEPAEXITSOL(sepaExitsolMaster)
162 {
163  SCIP_SEPADATA* sepadata;
164  int i;
165 
166  sepadata = SCIPsepaGetData(sepa);
167  assert(sepadata != NULL);
168 
169  assert(GCGmasterGetOrigprob(scip) != NULL);
170 
171  for( i = 0; i < sepadata->ncuts; i++ )
172  {
173  SCIP_CALL( SCIPreleaseRow(scip, &(sepadata->mastercuts[i])) );
174  }
175 
176  return SCIP_OKAY;
177 }
178 
180 static
181 SCIP_DECL_SEPAEXECLP(sepaExeclpMaster)
182 {
183  SCIP* origscip;
184  SCIP_Bool delayed;
185  SCIP_Bool cutoff;
186  SCIP_ROW** cuts;
187  SCIP_ROW* mastercut;
188  SCIP_VAR** rowvars;
189  SCIP_SEPADATA* sepadata;
190 
191  SCIP_VAR** mastervars;
192  SCIP_Real* mastervals;
193  int nmastervars;
194 
195  char name[SCIP_MAXSTRLEN];
196 
197  int ncuts;
198  int norigcuts;
199  int i;
200  int j;
201  SCIP_Bool feasible;
202 
203  SCIP_Bool isroot;
204 
205  assert(scip != NULL);
206  assert(result != NULL);
207 
208  origscip = GCGmasterGetOrigprob(scip);
209  assert(origscip != NULL);
210 
211  sepadata = SCIPsepaGetData(sepa);
212  assert(sepadata != NULL);
213 
214  SCIPdebugMessage("sepaExeclpMaster\n");
215 
216  *result = SCIP_DIDNOTFIND;
217 
218  if( !sepadata->enable )
219  {
220  *result = SCIP_DIDNOTRUN;
221  return SCIP_OKAY;
222  }
223 
224  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
225  {
226  SCIPdebugMessage("master LP not solved to optimality, do no separation!\n");
227  return SCIP_OKAY;
228  }
229 
230  if( GCGgetNRelPricingprobs(origscip) < GCGgetNPricingprobs(origscip) )
231  {
232  SCIPdebugMessage("aggregated pricing problems, do no separation!\n");
233  *result = SCIP_DIDNOTRUN;
234  return SCIP_OKAY;
235  }
236 
237  /* ensure to separate current sol */
238  SCIP_CALL( GCGrelaxUpdateCurrentSol(origscip) );
239 
240  if( GCGrelaxIsOrigSolFeasible(origscip) )
241  {
242  SCIPdebugMessage("Current solution is feasible, no separation necessary!\n");
243  *result = SCIP_DIDNOTRUN;
244  return SCIP_OKAY;
245  }
246 
247  isroot = SCIPgetCurrentNode(scip) == SCIPgetRootNode(scip);
248 
249  /* set parameter setting for separation */
250  SCIP_CALL( SCIPsetSeparating(origscip, (SCIP_PARAMSETTING) sepadata->separationsetting, TRUE) );
251 
252  SCIP_CALL( SCIPseparateSol(origscip, GCGrelaxGetCurrentOrigSol(origscip),
253  isroot, TRUE, FALSE, &delayed, &cutoff) );
254 
255  SCIPdebugMessage("SCIPseparateSol() found %d cuts!\n", SCIPgetNCuts(origscip));
256 
257  if( delayed && !cutoff )
258  {
259  SCIPdebugMessage("call delayed separators\n");
260 
261  SCIP_CALL( SCIPseparateSol(origscip, GCGrelaxGetCurrentOrigSol(origscip),
262  isroot, TRUE, TRUE, &delayed, &cutoff) );
263  }
264 
265  /* if cut off is detected set result pointer and return SCIP_OKAY */
266  if( cutoff )
267  {
268  *result = SCIP_CUTOFF;
269  SCIP_CALL( SCIPendProbing(origscip) );
270 
271  /* disable separating again */
272  SCIP_CALL( SCIPsetSeparating(origscip, SCIP_PARAMSETTING_OFF, TRUE) );
273 
274  return SCIP_OKAY;
275  }
276 
277  cuts = SCIPgetCuts(origscip);
278  ncuts = SCIPgetNCuts(origscip);
279 
280  /* save cuts in the origcuts array in the separator data */
281  norigcuts = sepadata->ncuts;
282  SCIP_CALL( ensureSizeCuts(scip, sepadata, sepadata->ncuts + ncuts) );
283 
284  for( i = 0; i < ncuts; i++ )
285  {
286  sepadata->origcuts[norigcuts] = cuts[i];
287  SCIP_CALL( SCIPcaptureRow(origscip, sepadata->origcuts[norigcuts]) );
288  norigcuts++;
289  }
290 
291  SCIP_CALL( SCIPclearCuts(origscip) );
292 
293  mastervars = SCIPgetVars(scip);
294  nmastervars = SCIPgetNVars(scip);
295  SCIP_CALL( SCIPallocBufferArray(scip, &mastervals, nmastervars) );
296 
297  for( i = 0; i < ncuts; i++ )
298  {
299  SCIP_ROW* origcut;
300  SCIP_COL** cols;
301  int ncols;
302  SCIP_Real* vals;
303 
304  origcut = sepadata->origcuts[norigcuts-ncuts+i]; /*lint !e679*/
305 
306  /* get columns and vals of the cut */
307  ncols = SCIProwGetNNonz(origcut);
308  cols = SCIProwGetCols(origcut);
309  vals = SCIProwGetVals(origcut);
310 
311  /* get the variables corresponding to the columns in the cut */
312  SCIP_CALL( SCIPallocBufferArray(scip, &rowvars, ncols) );
313  for( j = 0; j < ncols; j++ )
314  {
315  rowvars[j] = SCIPcolGetVar(cols[j]);
316  }
317 
318  /* create new cut in the master problem */
319  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "mc_%s", SCIProwGetName(origcut));
320  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &mastercut, sepa, name,
321  ( SCIPisInfinity(scip, -SCIProwGetLhs(origcut)) ?
322  SCIProwGetLhs(origcut) : SCIProwGetLhs(origcut) - SCIProwGetConstant(origcut)),
323  ( SCIPisInfinity(scip, SCIProwGetRhs(origcut)) ?
324  SCIProwGetRhs(origcut) : SCIProwGetRhs(origcut) - SCIProwGetConstant(origcut)),
325  SCIProwIsLocal(origcut), TRUE, FALSE) );
326 
327  /* transform the original variables to master variables and add them to the cut */
328  GCGtransformOrigvalsToMastervals(GCGmasterGetOrigprob(scip), rowvars, vals, ncols, mastervars, mastervals, nmastervars);
329  SCIP_CALL( SCIPaddVarsToRow(scip, mastercut, nmastervars, mastervars, mastervals) );
330 
331  /* add the cut to the master problem */
332  SCIP_CALL( SCIPaddRow(scip, mastercut, FALSE, &feasible) );
333  sepadata->mastercuts[sepadata->ncuts] = mastercut;
334  sepadata->ncuts++;
335 
336 #ifdef SCIP_DEBUG
337  SCIPdebugMessage("Cut %d:\n", i);
338  SCIP_CALL( SCIPprintRow(scip, mastercut, NULL) );
339  SCIPdebugMessage("\n\n");
340 #endif
341 
342  SCIPfreeBufferArray(scip, &rowvars);
343  }
344 
345  assert(norigcuts == sepadata->ncuts);
346 
347  if( ncuts > 0 )
348  *result = SCIP_SEPARATED;
349 
350  SCIPdebugMessage("%d cuts are in the original sepastore!\n", SCIPgetNCuts(origscip));
351  SCIPdebugMessage("%d cuts are in the master sepastore!\n", SCIPgetNCuts(scip));
352 
353  /* disable separation for original problem again */
354  SCIP_CALL( SCIPsetSeparating(origscip, SCIP_PARAMSETTING_OFF, TRUE) );
355 
356  SCIPfreeBufferArray(scip, &mastervals);
357 
358  return SCIP_OKAY;
359 }
360 
361 
362 /*
363  * separator specific interface methods
364  */
365 
368  SCIP* scip
369  )
370 {
371  SCIP_SEPADATA* sepadata;
372 
373  /* create master separator data */
374  SCIP_CALL( SCIPallocMemory(scip, &sepadata) );
375 
376  SCIP_CALL( SCIPallocMemoryArray(scip, &(sepadata->origcuts), STARTMAXCUTS) ); /*lint !e506*/
377  SCIP_CALL( SCIPallocMemoryArray(scip, &(sepadata->mastercuts), STARTMAXCUTS) ); /*lint !e506*/
378  sepadata->maxcuts = STARTMAXCUTS;
379  sepadata->ncuts = 0;
380 
381  /* include separator */
383  sepaCopyMaster, sepaFreeMaster, sepaInitMaster, sepaExitMaster,
384  sepaInitsolMaster, sepaExitsolMaster,
385  sepaExeclpMaster, sepaExecsolMaster,
386  sepadata) );
387 
388  SCIP_CALL( SCIPaddBoolParam(GCGmasterGetOrigprob(scip), "sepa/" SEPA_NAME "/enable", "enable master separator",
389  &(sepadata->enable), FALSE, TRUE, NULL, NULL) );
390 
391  SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "sepa/" SEPA_NAME "/paramsetting", "parameter returns which parameter setting is used for "
392  "separation (default = 0, aggressive = 1, fast = 2", &(sepadata->separationsetting), FALSE, 1, 0, 2, NULL, NULL) );
393 
394  return SCIP_OKAY;
395 }
396 
397 
400  SCIP* scip
401  )
402 {
403  SCIP_SEPA* sepa;
404  SCIP_SEPADATA* sepadata;
405 
406  assert(scip != NULL);
407 
408  sepa = SCIPfindSepa(scip, SEPA_NAME);
409  assert(sepa != NULL);
410 
411  sepadata = SCIPsepaGetData(sepa);
412  assert(sepadata != NULL);
413 
414  return sepadata->origcuts;
415 }
416 
419  SCIP* scip
420  )
421 {
422  SCIP_SEPA* sepa;
423  SCIP_SEPADATA* sepadata;
424 
425  assert(scip != NULL);
426 
427  sepa = SCIPfindSepa(scip, SEPA_NAME);
428  assert(sepa != NULL);
429 
430  sepadata = SCIPsepaGetData(sepa);
431  assert(sepadata != NULL);
432 
433  return sepadata->ncuts;
434 }
435 
438  SCIP* scip
439  )
440 {
441  SCIP_SEPA* sepa;
442  SCIP_SEPADATA* sepadata;
443 
444  assert(scip != NULL);
445 
446  sepa = SCIPfindSepa(scip, SEPA_NAME);
447  assert(sepa != NULL);
448 
449  sepadata = SCIPsepaGetData(sepa);
450  assert(sepadata != NULL);
451 
452  return sepadata->mastercuts;
453 }
454 
456 SCIP_RETCODE GCGsepaAddMastercuts(
457  SCIP* scip,
458  SCIP_ROW* origcut,
459  SCIP_ROW* mastercut
460 )
461 {
462  SCIP_SEPA* sepa;
463  SCIP_SEPADATA* sepadata;
464 
465  assert(scip != NULL);
466 
467  sepa = SCIPfindSepa(scip, SEPA_NAME);
468  assert(sepa != NULL);
469 
470  sepadata = SCIPsepaGetData(sepa);
471  assert(sepadata != NULL);
472 
473  SCIP_CALL( ensureSizeCuts(scip, sepadata, sepadata->ncuts + 1) );
474 
475  sepadata->origcuts[sepadata->ncuts] = origcut;
476  sepadata->mastercuts[sepadata->ncuts] = mastercut;
477  SCIP_CALL( SCIPcaptureRow(scip, sepadata->origcuts[sepadata->ncuts]) );
478  SCIP_CALL( SCIPcaptureRow(scip, sepadata->mastercuts[sepadata->ncuts]) );
479 
480  ++(sepadata->ncuts);
481 
482  return SCIP_OKAY;
483 }
#define SEPA_PRIORITY
Definition: sepa_master.c:49
#define SEPA_USESSUBSCIP
Definition: sepa_master.c:53
#define sepaCopyMaster
Definition: sepa_master.c:114
static SCIP_DECL_SEPAEXITSOL(sepaExitsolMaster)
Definition: sepa_master.c:161
GCG interface methods.
#define SEPA_FREQ
Definition: sepa_master.c:51
static SCIP_RETCODE ensureSizeCuts(SCIP *scip, SCIP_SEPADATA *sepadata, int size)
Definition: sepa_master.c:83
SCIP_RETCODE GCGsepaAddMastercuts(SCIP *scip, SCIP_ROW *origcut, SCIP_ROW *mastercut)
Definition: sepa_master.c:456
static SCIP_DECL_SEPAEXECLP(sepaExeclpMaster)
Definition: sepa_master.c:181
#define SEPA_DESC
Definition: sepa_master.c:48
master separator
SCIP_SOL * GCGrelaxGetCurrentOrigSol(SCIP *scip)
Definition: relax_gcg.c:4093
#define SEPA_NAME
Definition: sepa_master.c:47
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3897
SCIP_ROW ** GCGsepaGetMastercuts(SCIP *scip)
Definition: sepa_master.c:437
SCIP_RETCODE GCGrelaxUpdateCurrentSol(SCIP *scip)
Definition: relax_gcg.c:4650
int GCGgetNRelPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3877
static SCIP_DECL_SEPAFREE(sepaFreeMaster)
Definition: sepa_master.c:121
#define sepaExecsolMaster
Definition: sepa_master.c:117
SCIP_RETCODE SCIPincludeSepaMaster(SCIP *scip)
Definition: sepa_master.c:367
GCG relaxator.
GCG variable pricer.
SCIP_Bool enable
Definition: sepa_basis.c:87
SCIP * GCGmasterGetOrigprob(SCIP *scip)
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4112
void GCGtransformOrigvalsToMastervals(SCIP *scip, SCIP_VAR **origvars, SCIP_Real *origvals, int norigvars, SCIP_VAR **mastervars, SCIP_Real *mastervals, int nmastervars)
Definition: misc.c:548
static SCIP_DECL_SEPAEXIT(sepaExitMaster)
Definition: sepa_master.c:137
#define sepaInitsolMaster
Definition: sepa_master.c:116
int separationsetting
Definition: sepa_basis.c:93
#define SEPA_MAXBOUNDDIST
Definition: sepa_master.c:52
#define MAXCUTSINC
Definition: sepa_master.c:57
int GCGsepaGetNCuts(SCIP *scip)
Definition: sepa_master.c:418
#define STARTMAXCUTS
Definition: sepa_master.c:56
#define sepaInitMaster
Definition: sepa_master.c:115
#define SEPA_DELAY
Definition: sepa_master.c:54
SCIP_ROW ** origcuts
Definition: sepa_basis.c:77
SCIP_ROW ** mastercuts
Definition: sepa_basis.c:76
SCIP_ROW ** GCGsepaGetOrigcuts(SCIP *scip)
Definition: sepa_master.c:399