Scippy

GCG

Branch-and-Price & Column Generation for Everyone

pricer_gcg.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 pricer_gcg.cpp
29  * @brief pricer for generic column generation
30  * @author Gerald Gamrath
31  * @author Martin Bergner
32  * @author Alexander Gross
33  * @author Christian Puchert
34  * @author Michael Bastubbe
35  * @author Jonas Witt
36  */
37 
38 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
39 /* #define SCIP_DEBUG */
40 /* #define PRINTDUALSOLS */
41 
42 #include <cassert>
43 #include <cstring>
44 
45 /*lint -e64 disable useless and wrong lint warning */
46 
47 #ifdef __INTEL_COMPILER
48 #ifndef _OPENMP
49 #pragma warning disable 3180 /* disable wrong and useless omp warnings */
50 #endif
51 #endif
52 #include "scip/scip.h"
53 #include "gcg.h"
54 
55 #include "scip/cons_linear.h"
56 #include "scip/cons_knapsack.h"
57 
58 #include "pricer_gcg.h"
59 #include "objpricer_gcg.h"
60 #include "sepa_master.h"
61 #include "sepa_basis.h"
62 
63 #include "relax_gcg.h"
64 #include "scip_misc.h"
65 #include "pub_gcgvar.h"
66 #include "pub_gcgcol.h"
67 #include "pub_pricingjob.h"
68 #include "pub_pricingprob.h"
69 #include "pub_solver.h"
70 #include "solver.h"
71 #include "cons_masterbranch.h"
72 #include "objscip/objscip.h"
73 #include "objpricer_gcg.h"
74 #include "class_pricingtype.h"
76 #include "class_stabilization.h"
77 #include "branch_generic.h"
78 #include "event_display.h"
79 #include "pub_colpool.h"
80 
81 #ifdef SCIP_STATISTIC
82 #include "scip/struct_scip.h"
83 #include "scip/struct_stat.h"
84 #endif
85 
86 #ifdef _OPENMP
87 #include <omp.h>
88 #endif
89 
90 using namespace scip;
91 
92 #define PRICER_NAME "gcg"
93 #define PRICER_DESC "pricer for gcg"
94 #define PRICER_PRIORITY 5000000
95 #define PRICER_DELAY TRUE /* only call pricer if all problem variables have non-negative reduced costs */
96 
97 #define DEFAULT_ABORTPRICINGINT TRUE /**< should the pricing be aborted when integral */
98 #define DEFAULT_ABORTPRICINGGAP 0.00 /**< gap between dual bound and RMP objective at which pricing is aborted */
99 #define DEFAULT_DISPINFOS FALSE /**< should additional information be displayed */
100 #define DEFAULT_DISABLECUTOFF 2 /**< should the cutoffbound be applied in master LP solving? (0: on, 1:off, 2:auto) */
101 #define DEFAULT_THREADS 0 /**< number of threads (0 is OpenMP default) */
102 #define DEFAULT_STABILIZATION TRUE /**< should stabilization be used */
103 #define DEFAULT_STABILIZATIONTREE FALSE /**< should stabilization be used in nodes other than the root node*/
104 #define DEFAULT_HYBRIDASCENT FALSE /**< should hybridization of smoothing with an ascent method be enabled */
105 #define DEFAULT_HYBRIDASCENT_NOAGG FALSE /**< should hybridization of smoothing with an ascent method be enabled
106  * if pricing problems cannot be aggregation */
107 
108 #define DEFAULT_USECOLPOOL TRUE /**< should the colpool be checked for negative redcost cols before solving the pricing problems? */
109 #define DEFAULT_COLPOOL_AGELIMIT 100 /**< default age limit for columns in column pool */
110 
111 #define DEFAULT_PRICE_ORTHOFAC 0.0
112 #define DEFAULT_PRICE_OBJPARALFAC 0.0
113 #define DEFAULT_PRICE_REDCOSTFAC 1.0
114 #define DEFAULT_PRICE_MINCOLORTH 0.0
115 #define DEFAULT_PRICE_EFFICIACYCHOICE 0
116 
117 #define DEFAULT_USEARTIFICIALVARS FALSE /**< add artificial vars to master (instead of using Farkas pricing) */
118 #define DEFAULT_USEMAXOBJ TRUE /**< default value for using maxobj for big M objective of artificial variables */
119 #define DEFAULT_ONLYRELIABLEBIGM TRUE /**< default value for only using maxobj for big M objective of artificial variables if it is reliable */
120 #define DEFAULT_FACTORUNRELIABLE 1000 /**< default factor to use for objective of unbounded variables */
121 #define DEFAULT_BIGMARTIFICIAL 1000 /**< default value for big M objective of artificial variables (if maxobj is not used)*/
122 
123 #define EVENTHDLR_NAME "probdatavardeleted"
124 #define EVENTHDLR_DESC "event handler for variable deleted event"
125 
126 /** small macro to simplify printing pricer information */
127 #define GCGpricerPrintInfo(scip, pricerdata, ...) do { \
128  if( pricerdata->dispinfos ) { \
129  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, __VA_ARGS__);\
130  } else {\
131  SCIPdebugMessage(__VA_ARGS__); \
132  }\
133  }while( FALSE )
134 
135 #define PRICER_STAT_ARRAYLEN_TIME 1024 /**< length of the array for Time histogram representation */
136 #define PRICER_STAT_BUCKETSIZE_TIME 10 /**< size of the buckets for Time histogram representation */
137 #define PRICER_STAT_ARRAYLEN_VARS 1024 /**< length of the array for foundVars histogram representation */
138 #define PRICER_STAT_BUCKETSIZE_VARS 1 /**< size of the buckets for foundVars histogram representation */
139 
140 /*
141  * Data structures
142  */
143 
144 /** variable pricer data */
146 {
147  int npricingprobs; /**< number of pricing problems */
148  SCIP** pricingprobs; /**< pointers to the pricing problems */
149  SCIP_Real* dualsolconv; /**< array of dual solutions for the convexity constraints */
150  SCIP_Real* solvals; /**< solution values of variables in the pricing problems */
151  int maxsolvals; /**< capacity of solvals */
152  int* npointsprob; /**< number of variables representing points created by the pricing probs */
153  int* nraysprob; /**< number of variables representing rays created by the pricing probs */
154  SCIP_Longint currnodenr; /**< current node number in the masterproblem */
155  SCIP_Bool newnode; /**< indicate whether we are at a new branch-and-bound node */
156  SCIP_HASHMAP* mapcons2idx; /**< hashmap mapping constraints to their index in the conss array */
157  int npricingprobsnotnull; /**< number of non-Null pricing problems*/
158 
159  SCIP_VAR** pricedvars; /**< array of all priced variables */
160  int npricedvars; /**< number of priced variables */
161  int maxpricedvars; /**< maximal number of priced variables */
162 
163  SCIP_VAR** artificialvars; /**< array of artificial variables */
164  int nartificialvars; /**< number of artificial variables */
165  int maxartificialvars; /**< capacity of artificialvars */
166  SCIP_Bool artificialused; /**< returns if artificial variables are used in current node's LP solution */
167 
168  SCIP_Real** realdualvalues; /**< real dual values for pricing variables */
169  int* maxrealdualvalues; /**< capacities of realdualvalues */
170  int maxrealdualvaluescapacity; /**< capacity of maxrealdualvalues */
171 
172  /* variables used for statistics */
173  SCIP_CLOCK* freeclock; /**< time for freeing pricing problems */
174  SCIP_CLOCK* transformclock; /**< time for transforming pricing problems */
175  int solvedsubmipsoptimal; /**< number of optimal pricing runs */
176  int solvedsubmipsheur; /**< number of heuristical pricing runs*/
177  int calls; /**< number of total pricing calls */
178  SCIP_Longint pricingiters; /**< sum of all pricing simplex iterations */
179 
180  /* solver data */
181  GCG_SOLVER** solvers; /**< pricing solvers array */
182  int nsolvers; /**< number of pricing solvers */
183 
184  /* event handler */
185  SCIP_EVENTHDLR* eventhdlr; /**< event handler */
186 
187  /* parameter values */
188  SCIP_VARTYPE vartype; /**< vartype of created master variables */
189  int nroundsredcost; /**< number of reduced cost rounds */
190  SCIP_Bool abortpricingint; /**< should the pricing be aborted on integral solutions? */
191  SCIP_Bool dispinfos; /**< should pricing information be displayed? */
192  int disablecutoff; /**< should the cutoffbound be applied in master LP solving (0: on, 1:off, 2:auto)? */
193  SCIP_Real abortpricinggap; /**< gap between dual bound and RMP objective at which pricing is aborted */
194  SCIP_Bool stabilization; /**< should stabilization be used */
195  SCIP_Bool stabilizationtree; /**< should stabilization be used in nodes other than the root node */
196  SCIP_Bool usecolpool; /**< should the colpool be checked for negative redcost cols before solving the pricing problems? */
197  SCIP_Bool useartificialvars; /**< use artificial variables to make RMP feasible (instead of applying Farkas pricing) */
198  SCIP_Real maxobj; /**< maxobj bound that can be used for big M objective of artificial variables */
199  SCIP_Bool usemaxobj; /**< use maxobj for big M objective of artificial variables */
200  SCIP_Bool onlyreliablebigm; /**< only use maxobj for big M objective of artificial variables if it is reliable */
201  SCIP_Real factorunreliable; /**< factor to use for objective of unbounded variables */
202  SCIP_Real bigmartificial; /**< value for for big M objective of artificial variables (if maxobj is not used) */
203  SCIP_Bool hybridascent; /**< should hybridization of smoothing with an ascent method be enabled */
204  SCIP_Bool hybridascentnoagg; /**< should hybridization of smoothing with an ascent method be enabled
205  * if pricing problems cannot be aggregation */
206  int colpoolagelimit; /**< agelimit of columns in colpool */
207 
208  /* price storage */
209  SCIP_Real redcostfac; /**< factor of -redcost/norm in score function */
210  SCIP_Real objparalfac; /**< factor of objective parallelism in score function */
211  SCIP_Real orthofac; /**< factor of orthogonalities in score function */
212  SCIP_Real mincolorth; /**< minimal orthogonality of columns to add
213  (with respect to columns added in the current round) */
214  SCIP_Real maxpricecols; /**< maximum number of columns per round */
215  SCIP_Real maxpricecolsfarkas; /**< maximum number of columns per Farkas round */
216  GCG_EFFICIACYCHOICE efficiacychoice; /**< choice to base efficiacy on */
217 
218  /* statistics */
219  int oldvars; /**< Vars of last pricing iteration */
220  int* farkascallsdist; /**< Calls of each farkas pricing problem */
221  int* farkasfoundvars; /**< Found vars of each farkas pricing problem */
222  double* farkasnodetimedist; /**< Time spend in each farkas pricing problem */
223 
224  int* redcostcallsdist; /**< Calls of each redcost pricing problem */
225  int* redcostfoundvars; /**< Found vars of each redcost pricing problem */
226  double* redcostnodetimedist; /**< Time spend in each redcost pricing problem */
227  double rootnodedegeneracy; /**< degeneracy of the root node */
228  double avgrootnodedegeneracy; /**< average degeneray of all nodes */
229  int ndegeneracycalcs; /**< number of observations */
230 
231 #ifdef SCIP_STATISTIC
232  int nrootbounds; /**< number of stored bounds */
233  SCIP_Real* rootpbs; /**< array of primal bounds for the root LP, one bound for each pricing call */
234  SCIP_Real* rootdbs; /**< array of dual bounds for the root LP, one bound for each pricing call */
235  SCIP_Real* roottimes; /**< array of times spent for root LP */
236  SCIP_Real* rootdualdiffs; /**< array of differences to last dual solution */
237  int maxrootbounds; /**< maximal number of bounds */
238  SCIP_Real rootfarkastime; /**< time of last Farkas call */
239  SCIP_Real dualdiff; /**< difference to last dual solution */
240  int dualdiffround; /**< value of nrootbounds when difference to last dual solution was computed */
241  SCIP_SOL* rootlpsol; /**< optimal root LP solution */
242  SCIP_Real*** dualvalues; /**< array of dual values for pricing variables for each root redcost call*/
243  SCIP_Real** dualsolconvs; /**< array of dual solutions for the convexity constraints for each root redcost call*/
244  int* nodetimehist; /**< Histogram of nodetime distribution */
245  int* foundvarshist; /**< Histogram of foundvars distribution */
246 #endif
247 };
248 
249 
251 
252 /** information method for a parameter change of disablecutoff */
253 static
254 SCIP_DECL_PARAMCHGD(paramChgdDisablecutoff)
255 { /*lint --e{715}*/
256  SCIP* masterprob;
257  int newval;
258 
259  masterprob = GCGgetMasterprob(scip);
260  newval = SCIPparamGetInt(param);
261 
262  SCIP_CALL( SCIPsetIntParam(masterprob, "lp/disablecutoff", newval) );
263 
264  return SCIP_OKAY;
265 }
266 
267 
268 /*
269  * Callback methods of event handler
270  */
271 
272 /** destructor of event handler to free user data (called when SCIP is exiting) */
273 #define eventFreeVardeleted NULL
274 
275 /** initialization method of event handler (called after problem was transformed) */
276 #define eventInitVardeleted NULL
277 
278 /** deinitialization method of event handler (called before transformed problem is freed) */
279 #define eventExitVardeleted NULL
280 
281 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
282 #define eventInitsolVardeleted NULL
283 
284 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
285 #define eventExitsolVardeleted NULL
286 
287 /** frees specific event data */
288 #define eventDeleteVardeleted NULL
289 
290 /** execution method of event handler */
291 static
292 SCIP_DECL_EVENTEXEC(eventExecVardeleted)
293 { /*lint --e{715}*/
294  SCIP_VAR* var;
295  ObjPricerGcg* pricer;
296  SCIP_PRICERDATA* pricerdata;
297  SCIP_VAR** origvars;
298  int i;
299 
300  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
301  assert(pricer != NULL);
302 
303  pricerdata = pricer->getPricerdata();
304  assert(pricerdata != NULL);
305 
306  assert(SCIPeventGetType(event) == SCIP_EVENTTYPE_VARDELETED);
307  var = SCIPeventGetVar(event);
308  assert(var != NULL);
309 
310  SCIPdebugMessage("remove master variable %s from pricerdata and corresponding original variables\n", SCIPvarGetName(var));
311 
312  assert(GCGvarIsMaster(var));
313  origvars = GCGmasterVarGetOrigvars(var);
314  assert(origvars != NULL);
315 
316  /* remove master variable from corresponding pricing original variables */
317  for( i = 0; i < GCGmasterVarGetNOrigvars(var); ++i )
318  {
319  SCIP_CALL( GCGoriginalVarRemoveMasterVar(scip, origvars[i], var) );
320  }
321 
322  /* remove variable from array of stored priced variables */
323  i = GCGmasterVarGetIndex(var);
324  assert(i < pricerdata->npricedvars);
325 
326  if( i >= 0 )
327  {
328  assert(pricerdata->pricedvars[i] == var);
329 
330  /* drop vardeleted event on variable */
331  SCIP_CALL(
332  SCIPdropVarEvent(scip, pricerdata->pricedvars[i], SCIP_EVENTTYPE_VARDELETED, pricerdata->eventhdlr, NULL, -1));
333 
334  SCIP_CALL(SCIPreleaseVar(scip, &(pricerdata->pricedvars[i])));
335  (pricerdata->npricedvars)--;
336  assert(pricerdata->pricedvars[pricerdata->npricedvars] != NULL || i == pricerdata->npricedvars);
337  pricerdata->pricedvars[i] = pricerdata->pricedvars[pricerdata->npricedvars];
338  if( i < pricerdata->npricedvars )
339  GCGmasterVarSetIndex(pricerdata->pricedvars[i], i);
340  (pricerdata->oldvars)--;
341 
342 #ifndef NDEBUG
343  for ( ; i < pricerdata->npricedvars; ++i )
344  {
345  assert(pricerdata->pricedvars[i] != var);
346  }
347 #endif
348  }
349 
350  return SCIP_OKAY;
351 }
352 
353 
354 /*
355  * Local methods
356  */
357 
358 /** return TRUE or FALSE whether the master LP is solved to optimality */
359 SCIP_Bool ObjPricerGcg::isMasterLPOptimal() const
360 {
361  assert(GCGisMaster(scip_));
362 
363  return SCIPgetLPSolstat(scip_) == SCIP_LPSOLSTAT_OPTIMAL;
364 }
365 
366 /** get the number of columns to be added to the master LP in the current pricing round */
368 {
369  assert(pricingtype != NULL);
370 
371  return pricingtype->getMaxcolsround();
372 }
373 
374 /** get the number of columns per pricing problem to be added to the master LP in the current pricing round */
376 {
377  assert(pricingtype != NULL);
378 
379  return pricingtype->getMaxcolsprob();
380 }
381 
382 /** ensures size of pricedvars array */
383 SCIP_RETCODE ObjPricerGcg::ensureSizePricedvars(
384  int size /**< needed size */
385  )
386 {
387  assert(pricerdata != NULL);
388  assert(pricerdata->pricedvars != NULL);
389 
390  if( pricerdata->maxpricedvars < size )
391  {
392  int oldsize = pricerdata->maxpricedvars;
393  pricerdata->maxpricedvars = SCIPcalcMemGrowSize(scip_, size);
394  SCIP_CALL( SCIPreallocBlockMemoryArray(scip_, &(pricerdata->pricedvars), oldsize, pricerdata->maxpricedvars) );
395  }
396  assert(pricerdata->maxpricedvars >= size);
397 
398  return SCIP_OKAY;
399 }
400 
401 
402 #ifdef SCIP_STATISTIC
403 /** ensures size of root bounds arrays */
404 SCIP_RETCODE ObjPricerGcg::ensureSizeRootBounds(
405  int size /**< needed size */
406  )
407 {
408  assert(pricerdata != NULL);
409  assert(pricerdata->rootdbs != NULL);
410  assert(pricerdata->rootpbs != NULL);
411  assert(pricerdata->roottimes != NULL);
412  assert(pricerdata->rootdualdiffs != NULL);
413  assert(pricerdata->dualvalues != NULL);
414  assert(pricerdata->dualsolconvs != NULL);
415 
416  if( pricerdata->maxrootbounds < size )
417  {
418  int oldsize = pricerdata->maxrootbounds;
419  pricerdata->maxrootbounds = SCIPcalcMemGrowSize(scip_, size);
420  SCIP_CALL( SCIPreallocBlockMemoryArray(scip_, &(pricerdata->rootpbs), oldsize, pricerdata->maxrootbounds) );
421  SCIP_CALL( SCIPreallocBlockMemoryArray(scip_, &(pricerdata->rootdbs), oldsize, pricerdata->maxrootbounds) );
422  SCIP_CALL( SCIPreallocBlockMemoryArray(scip_, &(pricerdata->roottimes), oldsize, pricerdata->maxrootbounds) );
423  SCIP_CALL( SCIPreallocBlockMemoryArray(scip_, &(pricerdata->rootdualdiffs), oldsize, pricerdata->maxrootbounds) );
424  SCIP_CALL( SCIPreallocBlockMemoryArray(scip_, &(pricerdata->dualvalues), oldsize, pricerdata->maxrootbounds) );
425  SCIP_CALL( SCIPreallocBlockMemoryArray(scip_, &(pricerdata->dualsolconvs), oldsize, pricerdata->maxrootbounds) );
426  }
427  assert(pricerdata->maxrootbounds >= size);
428 
429  return SCIP_OKAY;
430 }
431 #endif
432 
433 #ifdef SCIP_STATISTIC
434 /** gets the NodeTimeDistribution in the form of a histogram */
435 static
436 void GCGpricerGetNodeTimeHistogram(
437  SCIP_PRICERDATA* pricerdata, /**< pricerdata data structure */
438  SCIP_Real time /**< time the pricingproblem needed */
439  )
440 {
441  int i;
442  assert(pricerdata != NULL);
443  /* 1000* because mapping milliseconds on the index i */
444  i = 1000*time/PRICER_STAT_BUCKETSIZE_TIME; /*lint !e524 */
445 
446  if( i >= PRICER_STAT_ARRAYLEN_TIME )
447  {
449  }
450 
451  assert(i < PRICER_STAT_ARRAYLEN_TIME);
452  assert(i >= 0);
453  pricerdata->nodetimehist[i]++;
454 
455 }
456 
457 
458 /** gets the FoundVarsDistribution in form of a histogram */
459 static
460 void GCGpricerGetFoundVarsHistogram(
461  SCIP_PRICERDATA* pricerdata, /**< pricerdata data structure */
462  int foundvars /**< foundVars in pricingproblem */
463  )
464 {
465  int i;
466  assert(pricerdata != NULL);
467  i = foundvars/PRICER_STAT_BUCKETSIZE_VARS;
468  if( i >= PRICER_STAT_ARRAYLEN_VARS )
469  {
471  }
472 
473  assert(i < PRICER_STAT_ARRAYLEN_VARS);
474  assert(i >= 0);
475  pricerdata->foundvarshist[i]++;
476 
477 }
478 
479 
480 /** gets the statistics of the pricingprobs like calls, foundvars and time */
481 static
482 void GCGpricerCollectStatistic(
483  SCIP_PRICERDATA* pricerdata, /**< pricerdata data structure */
484  GCG_PRICETYPE type, /**< type of pricing: optimal or heuristic */
485  int probindex, /**< index of the pricingproblem */
486  SCIP_Real time /**< time the pricingproblem needed */
487  )
488 {
489  int foundvars;
490  assert(pricerdata != NULL);
491  foundvars = pricerdata->npricedvars - pricerdata->oldvars;
492 
493  if( type == GCG_PRICETYPE_FARKAS )
494  {
495 
496  pricerdata->farkascallsdist[probindex]++; /*Calls*/
497  pricerdata->farkasfoundvars[probindex] += foundvars;
498  pricerdata->farkasnodetimedist[probindex] += time; /*Time*/
499 
500  }
501  else if( type == GCG_PRICETYPE_REDCOST )
502  {
503 
504  pricerdata->redcostcallsdist[probindex]++;
505  pricerdata->redcostfoundvars[probindex] += foundvars;
506  pricerdata->redcostnodetimedist[probindex] += time;
507 
508  }
509 
510  GCGpricerGetNodeTimeHistogram(pricerdata, time);
511  GCGpricerGetFoundVarsHistogram(pricerdata, foundvars);
512 
513  pricerdata->oldvars = pricerdata->npricedvars;
514 }
515 #endif
516 
517 /** frees all solvers */
518 SCIP_RETCODE ObjPricerGcg::solversFree()
519 {
520  int i;
521  assert(pricerdata != NULL);
522  assert((pricerdata->solvers == NULL) == (pricerdata->nsolvers == 0));
523  assert(pricerdata->nsolvers > 0);
524 
525  for( i = 0; i < pricerdata->nsolvers; i++ )
526  {
527  SCIP_CALL( GCGsolverFree(scip_, &pricerdata->solvers[i]) );
528  }
529 
530  return SCIP_OKAY;
531 }
532 
533 /** calls the init method on all solvers */
534 SCIP_RETCODE ObjPricerGcg::solversInit()
535 {
536  int i;
537  assert(pricerdata != NULL);
538  assert((pricerdata->solvers == NULL) == (pricerdata->nsolvers == 0));
539  assert(pricerdata->nsolvers > 0);
540 
541  for( i = 0; i < pricerdata->nsolvers; i++ )
542  {
543  SCIP_CALL( GCGsolverInit(scip_, pricerdata->solvers[i]) );
544  }
545 
546  return SCIP_OKAY;
547 }
548 
549 /** calls the exit method on all solvers */
550 SCIP_RETCODE ObjPricerGcg::solversExit()
551 {
552  int i;
553  assert(pricerdata != NULL);
554  assert((pricerdata->solvers == NULL) == (pricerdata->nsolvers == 0));
555  assert(pricerdata->nsolvers > 0);
556 
557  for( i = 0; i < pricerdata->nsolvers; i++ )
558  {
559  SCIP_CALL( GCGsolverExit(scip_, pricerdata->solvers[i]) );
560  }
561 
562  return SCIP_OKAY;
563 }
564 
565 /** calls the initsol method on all solvers */
566 SCIP_RETCODE ObjPricerGcg::solversInitsol()
567 {
568  int i;
569  assert(pricerdata != NULL);
570 
571  if( pricerdata->npricingprobs == 0 )
572  return SCIP_OKAY;
573 
574  assert((pricerdata->solvers == NULL) == (pricerdata->nsolvers == 0));
575  assert(pricerdata->nsolvers > 0);
576 
577  for( i = 0; i < pricerdata->nsolvers; i++ )
578  {
579  SCIP_CALL( GCGsolverInitsol(scip_, pricerdata->solvers[i]) );
580  }
581 
582  return SCIP_OKAY;
583 }
584 
585 /** calls the exitsol method of all solvers */
586 SCIP_RETCODE ObjPricerGcg::solversExitsol()
587 {
588  int i;
589  assert(pricerdata != NULL);
590  assert((pricerdata->solvers == NULL) == (pricerdata->nsolvers == 0));
591  assert(pricerdata->nsolvers > 0);
592 
593  if( pricerdata->npricingprobs == 0 )
594  return SCIP_OKAY;
595 
596  for( i = 0; i < pricerdata->nsolvers; i++ )
597  {
598  SCIP_CALL( GCGsolverExitsol(scip_, pricerdata->solvers[i]) );
599  }
600 
601  return SCIP_OKAY;
602 }
603 
604 /** returns the gegeneracy of the masterproblem */
605 SCIP_RETCODE ObjPricerGcg::computeCurrentDegeneracy(
606  double* degeneracy /**< pointer to store degeneracy */
607  )
608 {
609  int nrows;
610  SCIP_COL** cols;
611  SCIP_ROW** rows;
612  int i;
613  int countz = 0;
614  int* indizes = NULL;
615 
616  assert(degeneracy != NULL);
617 
618  nrows = SCIPgetNLPRows(scip_);
619 
620  if( nrows > 0 ) {
621  cols = SCIPgetLPCols(scip_);
622  rows = SCIPgetLPRows(scip_);
623 
624  SCIP_CALL(SCIPallocBufferArray(scip_, &indizes, (size_t) nrows));
625 
626  /* gives indices of Columns in Basis and indices of vars in Basis */
627  SCIP_CALL(SCIPgetLPBasisInd(scip_, indizes));
628 
629  for (i = 0; i < nrows; i++) {
630  SCIP_Real currentVal;
631  int colindex = indizes[i];
632 
633  /* is column if >= 0 it is column in basis, < 0 is for row */
634  if (colindex >= 0) {
635  SCIP_COL *col;
636  col = cols[colindex];
637  currentVal = SCIPcolGetPrimsol(col);
638 
639  if (SCIPisEQ(scip_, currentVal, SCIPcolGetLb(col)) || SCIPisEQ(scip_, currentVal, SCIPcolGetUb(col)))
640  countz++;
641  } else {
642  SCIP_ROW *row = rows[-indizes[i] - 1];
643  SCIP_Real lhs = SCIProwGetLhs(row);
644 
645  currentVal = SCIPgetRowActivity(scip_, row);
646 
647  if (SCIPisEQ(scip_, currentVal, SCIProwGetRhs(row)) || SCIPisEQ(scip_, currentVal, SCIProwGetLhs(row)))
648  countz++;
649  }
650  }
651  SCIPfreeBufferArray(scip_, &indizes);
652 
653  /* Degeneracy in % */
654  *degeneracy = ((double) countz / nrows);
655  } else {
656  *degeneracy = 0.0;
657  }
658 
659  assert(*degeneracy <= 1.0 && *degeneracy >= 0);
660 
661  return SCIP_OKAY;
662 }
663 
664 /** set subproblem memory limit */
665 SCIP_RETCODE ObjPricerGcg::setPricingProblemMemorylimit(
666  SCIP* pricingscip /**< SCIP of the pricingproblem */
667  )
668 {
669  SCIP_Real memlimit;
670 
671  assert(pricingscip != NULL);
672 
673  assert(GCGisOriginal(origprob));
674 
675  SCIP_CALL( SCIPgetRealParam(origprob, "limits/memory", &memlimit) );
676 
677  if( !SCIPisInfinity(origprob, memlimit) )
678  {
679  memlimit -= SCIPgetMemUsed(origprob)/1048576.0 + GCGgetPricingprobsMemUsed(origprob) - SCIPgetMemUsed(pricingscip)/1048576.0;
680  if( memlimit < 0 )
681  memlimit = 0.0;
682  SCIP_CALL( SCIPsetRealParam(pricingscip, "limits/memory", memlimit) );
683  }
684 
685  return SCIP_OKAY;
686 }
687 
688 
689 /** for a pricing problem, get the dual solution value or Farkas value of the convexity constraint */
691  PricingType* pricetype, /**< Farkas or Reduced cost pricing */
692  int probnr /**< index of corresponding pricing problem */
693  )
694 {
695  if( !GCGisPricingprobRelevant(origprob, probnr) )
696  return -1.0 * SCIPinfinity(scip_);
697  else
698  return pricetype->consGetDual(scip_, GCGgetConvCons(origprob, probnr));
699 }
700 
701 /** computes the pricing problem objectives
702  * @todo this method could use more parameters as it is private
703  */
705  PricingType* pricetype, /**< Farkas or Reduced cost pricing */
706  SCIP_Bool stabilize /**< do we use stabilization ? */
707  )
708 {
709  SCIP_CONS** origconss;
710  SCIP_CONS** masterconss;
711  int nmasterconss;
712  SCIP_VAR** probvars;
713  int nprobvars;
714 
715  SCIP_ROW** mastercuts;
716  int nmastercuts;
717  SCIP_ROW** origcuts;
718  SCIP_COL** cols;
719  SCIP_Real* consvals;
720  SCIP_Real dualsol;
721 
722  SCIP_VAR** consvars = NULL;
723  int nconsvars;
724  int i;
725  int j;
726 
727  assert(pricerdata != NULL);
728  assert(stabilization != NULL);
729 
730  /* get the constraints of the master problem and the corresponding constraints in the original problem */
731  nmasterconss = GCGgetNMasterConss(origprob);
732  masterconss = GCGgetMasterConss(origprob);
733  origconss = GCGgetOrigMasterConss(origprob);
734 
735  /* set objective value of all variables in the pricing problems to 0 (for farkas pricing) /
736  * to the original objective of the variable (for redcost pricing)
737  */
738  for( i = 0; i < pricerdata->npricingprobs; i++ )
739  {
740  if( pricerdata->pricingprobs[i] == NULL )
741  continue;
742  probvars = SCIPgetVars(pricerdata->pricingprobs[i]);
743  nprobvars = SCIPgetNVars(pricerdata->pricingprobs[i]);
744 
745  for( j = 0; j < nprobvars; j++ )
746  {
747  assert(GCGvarGetBlock(probvars[j]) == i);
748  assert( GCGoriginalVarIsLinking(GCGpricingVarGetOrigvars(probvars[j])[0]) || (GCGvarGetBlock(GCGpricingVarGetOrigvars(probvars[j])[0]) == i));
749 
750  SCIP_CALL( SCIPchgVarObj(pricerdata->pricingprobs[i], probvars[j], pricetype->varGetObj(probvars[j])));
751 
752  pricerdata->realdualvalues[i][j] = pricetype->varGetObj(probvars[j]);
753 #ifdef PRINTDUALSOLS
754  SCIPdebugMessage("pricingobj var <%s> %f, realdualvalues %f\n", SCIPvarGetName(probvars[j]), pricetype->varGetObj(probvars[j]), pricerdata->realdualvalues[i][j]);
755 #endif
756  }
757  }
758 
759  /* compute reduced cost for linking variable constraints and update objectives in the pricing problems
760  * go through constraints, and select correct variable
761  */
762 
763  int nlinkconss;
764  SCIP_CONS** linkconss;
765  int* linkconssblock;
766  nlinkconss = GCGgetNVarLinkingconss(origprob);
767  linkconss = GCGgetVarLinkingconss(origprob);
768  linkconssblock = GCGgetVarLinkingconssBlock(origprob);
769 
770  for( i = 0; i < nlinkconss; ++i)
771  {
772  SCIP_VAR** linkconsvars;
773  SCIP_CONS* linkcons = linkconss[i];
774  int block = linkconssblock[i];
775 
776  linkconsvars = SCIPgetVarsLinear(scip_, linkcons);
777 
778  SCIP_VAR* linkvar = linkconsvars[0];
779 
780  SCIP_VAR* pricingvar = GCGlinkingVarGetPricingVars(GCGmasterVarGetOrigvars(linkvar)[0])[block];
781  assert(GCGvarIsPricing(pricingvar));
782  if( stabilize )
783  {
784  dualsol = stabilization->linkingconsGetDual(i);
785  }
786  else
787  {
788  dualsol = pricetype->consGetDual(scip_, linkcons);
789  }
790 
791  /* add dual solution value to the pricing variable:
792  * lambda variables get coef -1 in linking constraints --> add dualsol
793  */
794  SCIP_CALL( SCIPaddVarObj(pricerdata->pricingprobs[block], pricingvar, dualsol) );
795  assert(SCIPvarGetProbindex(pricingvar) >= 0 && SCIPvarGetProbindex(pricingvar) < SCIPgetNVars(pricerdata->pricingprobs[block]));
796  pricerdata->realdualvalues[block][SCIPvarGetProbindex(pricingvar)] += pricetype->consGetDual(scip_, linkcons);
797 
798 #ifdef PRINTDUALSOLS
799  SCIPdebugMessage("pricingobj var <%s> %f, realdualvalues %f\n", SCIPvarGetName(pricingvar), dualsol, pricetype->consGetDual(scip_, linkcons));
800 #endif
801  }
802 
803  /* compute reduced cost and update objectives in the pricing problems */
804  for( i = 0; i < nmasterconss; i++ )
805  {
806  if( stabilize )
807  {
808  SCIP_CALL( stabilization->consGetDual(i, &dualsol) );
809  }
810  else
811  {
812  dualsol = pricetype->consGetDual(scip_, masterconss[i]);
813  }
814 
815  if( !SCIPisZero(scip_, dualsol) || !SCIPisZero(scip_, pricetype->consGetDual(scip_, masterconss[i])) )
816  {
817 #ifdef PRINTDUALSOLS
818  SCIPdebugMessage("mastercons <%s> dualsol: %g\n", SCIPconsGetName(masterconss[i]), dualsol);
819 #endif
820 
821  /* for all variables in the constraint, modify the objective of the corresponding variable in a pricing problem */
822  nconsvars = GCGconsGetNVars(origprob, origconss[i]);
823  SCIP_CALL( SCIPallocBufferArray(scip_, &consvars, nconsvars) );
824  SCIP_CALL( SCIPallocBufferArray(scip_, &consvals, nconsvars) );
825  GCGconsGetVars(origprob, origconss[i], consvars, nconsvars);
826  GCGconsGetVals(origprob, origconss[i], consvals, nconsvars);
827  for( j = 0; j < nconsvars; j++ )
828  {
829  int blocknr;
830  blocknr = GCGvarGetBlock(consvars[j]);
831  assert(GCGvarIsOriginal(consvars[j]));
832  /* nothing to be done if variable belongs to redundant block or variable was directly transferred to the master
833  * or variable is linking variable (which means, the directly transferred copy is part of the master cons)
834  */
835  if( blocknr >= 0 && pricerdata->pricingprobs[blocknr] != NULL )
836  {
837  assert(GCGoriginalVarGetPricingVar(consvars[j]) != NULL);
838  /* modify the objective of the corresponding variable in the pricing problem */
839  SCIP_CALL( SCIPaddVarObj(pricerdata->pricingprobs[blocknr],
840  GCGoriginalVarGetPricingVar(consvars[j]), -1.0 * dualsol * consvals[j]) );
841 
842  pricerdata->realdualvalues[blocknr][SCIPvarGetProbindex(GCGoriginalVarGetPricingVar(consvars[j]))] += -1.0 * consvals[j] * pricetype->consGetDual(scip_, masterconss[i]);
843 
844 #ifdef PRINTDUALSOLS
845  SCIPdebugMessage("pricingobj var <%s> %f, realdualvalues %f\n",
846  SCIPvarGetName(GCGoriginalVarGetPricingVar(consvars[j])), dualsol, -1.0 * consvals[j] * pricetype->consGetDual(scip_, masterconss[i]));
847 #endif
848  }
849  }
850  SCIPfreeBufferArray(scip_, &consvals);
851  SCIPfreeBufferArray(scip_, &consvars);
852  }
853  }
854 
855  /* get the cuts of the master problem and the corresponding cuts in the original problem */
856  mastercuts = GCGsepaGetMastercuts(scip_);
857  nmastercuts = GCGsepaGetNCuts(scip_);
858  origcuts = GCGsepaGetOrigcuts(scip_);
859 
860  assert(mastercuts != NULL);
861  assert(origcuts != NULL);
862 
863  /* compute reduced cost and update objectives in the pricing problems */
864  for( i = 0; i < nmastercuts; i++ )
865  {
866  if( stabilize )
867  {
868  SCIP_CALL( stabilization->rowGetDual(i, &dualsol) );
869  }
870  else
871  {
872  dualsol = pricetype->rowGetDual(mastercuts[i]);
873  }
874 
875  if( !SCIPisZero(scip_, dualsol) || !SCIPisZero(scip_, pricetype->rowGetDual(mastercuts[i])) )
876  {
877  /* get columns and vals of the cut */
878  nconsvars = SCIProwGetNNonz(origcuts[i]);
879  cols = SCIProwGetCols(origcuts[i]);
880  consvals = SCIProwGetVals(origcuts[i]);
881 
882  /* get the variables corresponding to the columns in the cut */
883  SCIP_CALL( SCIPallocBufferArray(scip_, &consvars, nconsvars) );
884  for( j = 0; j < nconsvars; j++ )
885  consvars[j] = SCIPcolGetVar(cols[j]);
886 
887  /* for all variables in the cut, modify the objective of the corresponding variable in a pricing problem */
888  for( j = 0; j < nconsvars; j++ )
889  {
890  int blocknr;
891  blocknr = GCGvarGetBlock(consvars[j]);
892  assert(GCGvarIsOriginal(consvars[j]));
893  /* nothing to be done if variable belongs to redundant block or
894  * variable was directly transferred to the master
895  * or variable is linking variable (which means, the directly transferred copy is part of the master cut) */
896  if( blocknr >= 0 && pricerdata->pricingprobs[blocknr] != NULL )
897  {
898  assert(GCGoriginalVarGetPricingVar(consvars[j]) != NULL);
899  /* modify the objective of the corresponding variable in the pricing problem */
900  SCIP_CALL( SCIPaddVarObj(pricerdata->pricingprobs[blocknr],
901  GCGoriginalVarGetPricingVar(consvars[j]), -1.0 * dualsol * consvals[j]) );
902 
903  pricerdata->realdualvalues[blocknr][SCIPvarGetProbindex(GCGoriginalVarGetPricingVar(consvars[j]))] += -1.0 *consvals[j]* pricetype->rowGetDual(mastercuts[i]);
904 
905 #ifdef PRINTDUALSOLS
906  SCIPdebugMessage("pricingobj var <%s> %f, realdualvalues %f\n",
907  SCIPvarGetName(GCGoriginalVarGetPricingVar(consvars[j])), dualsol, -1.0 * consvals[j] * pricetype->rowGetDual(mastercuts[i]));
908 #endif
909  }
910  }
911  SCIPfreeBufferArray(scip_, &consvars);
912  }
913  }
914 
915  /* get dual solutions / farkas values of the convexity constraints */
916  for( i = 0; i < pricerdata->npricingprobs; i++ )
917  {
918  assert( GCGisPricingprobRelevant(origprob, i) == (GCGgetConvCons(origprob, i) != NULL) );
919 
920  if( !GCGisPricingprobRelevant(origprob, i) )
921  {
922  pricerdata->dualsolconv[i] = -1.0 * SCIPinfinity(scip_);
923  continue;
924  }
925 
926  pricerdata->dualsolconv[i] = pricetype->consGetDual(scip_, GCGgetConvCons(origprob, i));
927 
928 #ifdef PRINTDUALSOLS
929  if( GCGisPricingprobRelevant(origprob, i) )
930  {
931  SCIPdebugMessage("convcons <%s> dualsol: %g\n", SCIPconsGetName(GCGgetConvCons(origprob, i)), pricerdata->dualsolconv[i]);
932  }
933 #endif
934  }
935 
936  return SCIP_OKAY;
937 }
938 
939 /** add master variable to all constraints */
940 SCIP_RETCODE ObjPricerGcg::addVariableToMasterconstraints(
941  SCIP_VAR* newvar, /**< The new variable to add */
942  int prob, /**< number of the pricing problem the solution belongs to */
943  SCIP_VAR** solvars, /**< array of variables with non-zero value in the solution of the pricing problem */
944  SCIP_Real* solvals, /**< array of values in the solution of the pricing problem for variables in array solvars*/
945  int nsolvars /**< number of variables in array solvars */
946  )
947 {
948  int i;
949  int c;
950  int idx;
951 
952  SCIP_CONS** masterconss;
953  int nmasterconss;
954  SCIP_Real* mastercoefs;
955  SCIP_CONS* linkcons;
956 
957  assert(pricerdata != NULL);
958 
959  nmasterconss = GCGgetNMasterConss(origprob);
960  masterconss = GCGgetMasterConss(origprob);
961 
962  SCIP_CALL( SCIPallocBufferArray(scip_, &mastercoefs, nmasterconss) ); /*lint !e530*/
963  BMSclearMemoryArray(mastercoefs, nmasterconss);
964 
965  /* compute coef of the variable in the master constraints */
966  for( i = 0; i < nsolvars; i++ )
967  {
968  if( !SCIPisZero(scip_, solvals[i]) )
969  {
970  SCIP_CONS** linkconss;
971  SCIP_VAR** origvars;
972  SCIP_Real* coefs;
973  int ncoefs;
974 
975  assert(GCGvarIsPricing(solvars[i]));
976  origvars = GCGpricingVarGetOrigvars(solvars[i]);
977  assert(GCGvarIsOriginal(origvars[0]));
978 
979  coefs = GCGoriginalVarGetCoefs(origvars[0]);
980  ncoefs = GCGoriginalVarGetNCoefs(origvars[0]);
981  assert(!SCIPisInfinity(scip_, solvals[i]));
982 
983  /* original variable is a linking variable, just add it to the linkcons */
984  if( GCGoriginalVarIsLinking(origvars[0]) )
985  {
986 #ifndef NDEBUG
987  SCIP_VAR** pricingvars;
988  pricingvars = GCGlinkingVarGetPricingVars(origvars[0]);
989 #endif
990  linkconss = GCGlinkingVarGetLinkingConss(origvars[0]);
991 
992  /* the linking constraints could be NULL if the Benders' decomposition is used. */
993  if( linkconss != NULL )
994  {
995  assert(pricingvars[prob] == solvars[i]);
996  assert(linkconss[prob] != NULL);
997  SCIP_CALL( SCIPaddCoefLinear(scip_, linkconss[prob], newvar, -solvals[i]) );
998  }
999  continue;
1000  }
1001 
1002  /* for each coef, add coef * solval to the coef of the new variable for the corresponding constraint */
1003  for( c = 0; c < ncoefs; c++ )
1004  {
1005  linkconss = GCGoriginalVarGetMasterconss(origvars[0]);
1006  assert(!SCIPisZero(scip_, coefs[c]));
1007  SCIP_CALL( SCIPgetTransformedCons(scip_, linkconss[c], &linkcons) );
1008 
1009  idx = (int)(size_t)SCIPhashmapGetImage(pricerdata->mapcons2idx, linkcons); /*lint !e507*/
1010  assert(0 <= idx && idx < nmasterconss);
1011  assert(masterconss[idx] == linkcons);
1012  mastercoefs[idx] += coefs[c] * solvals[i];
1013  }
1014 
1015  }
1016  }
1017 
1018  /* add the variable to the master constraints */
1019  for( i = 0; i < nmasterconss; i++ )
1020  {
1021  if( !SCIPisZero(scip_, mastercoefs[i]) )
1022  {
1023  assert(!SCIPisInfinity(scip_, mastercoefs[i]) && !SCIPisInfinity(scip_, -mastercoefs[i]));
1024  SCIP_CALL( SCIPaddCoefLinear(scip_, masterconss[i], newvar, mastercoefs[i]) );
1025  }
1026  }
1027 
1028  SCIPfreeBufferArray(scip_, &mastercoefs);
1029  return SCIP_OKAY;
1030 }
1031 
1032 /** add master variable to all constraints */
1033 SCIP_RETCODE ObjPricerGcg::addVariableToMasterconstraintsFromGCGCol(
1034  SCIP_VAR* newvar, /**< The new variable to add */
1035  GCG_COL* gcgcol /**< GCG column data structure */
1036  )
1037 {
1038  SCIP_CONS** masterconss;
1039  int nmasterconss;
1040  SCIP_Real* mastercoefs;
1041  int nlinkvars;
1042  int* linkvars;
1043 
1044  SCIP_VAR** solvars; /* array of variables with non-zero value in the solution of the pricing problem */
1045  SCIP_Real* solvals; /* array of values in the solution of the pricing problem for variables in array solvars*/
1046 #ifndef NDEBUG
1047  int nsolvars; /* number of variables in array solvars */
1048 #endif
1049 
1050  int i;
1051  int prob;
1052 
1053  assert(pricerdata != NULL);
1054 
1055  nmasterconss = GCGgetNMasterConss(origprob);
1056  masterconss = GCGgetMasterConss(origprob);
1057 
1058  SCIP_CALL( computeColMastercoefs(gcgcol) );
1059 
1060  mastercoefs = GCGcolGetMastercoefs(gcgcol);
1061 
1062  nlinkvars = GCGcolGetNLinkvars(gcgcol);
1063  linkvars = GCGcolGetLinkvars(gcgcol);
1064  solvars = GCGcolGetVars(gcgcol);
1065  solvals = GCGcolGetVals(gcgcol);
1066 #ifndef NDEBUG
1067  nsolvars = GCGcolGetNVars(gcgcol);
1068 #endif
1069 
1070  prob = GCGcolGetProbNr(gcgcol);
1071 
1072  /* compute coef of the variable in the master constraints */
1073  for( i = 0; i < nlinkvars; i++ )
1074  {
1075  SCIP_CONS** linkconss;
1076  SCIP_VAR** origvars;
1077 
1078  assert(linkvars[i] < nsolvars );
1079  assert(GCGvarIsPricing(solvars[linkvars[i]]));
1080  origvars = GCGpricingVarGetOrigvars(solvars[linkvars[i]]);
1081  assert(GCGvarIsOriginal(origvars[0]));
1082 
1083  assert(!SCIPisInfinity(scip_, solvals[linkvars[i]]));
1084 
1085  assert(GCGoriginalVarIsLinking(origvars[0]));
1086  /* original variable is a linking variable, just add it to the linkcons */
1087 #ifndef NDEBUG
1088  SCIP_VAR** pricingvars;
1089  pricingvars = GCGlinkingVarGetPricingVars(origvars[0]);
1090 #endif
1091  linkconss = GCGlinkingVarGetLinkingConss(origvars[0]);
1092 
1093  assert(pricingvars[prob] == solvars[linkvars[i]]);
1094  assert(linkconss[prob] != NULL);
1095  SCIP_CALL( SCIPaddCoefLinear(scip_, linkconss[prob], newvar, -solvals[linkvars[i]]) );
1096  }
1097 
1098  /* add the variable to the master constraints */
1099  for( i = 0; i < nmasterconss; i++ )
1100  {
1101  if( !SCIPisZero(scip_, mastercoefs[i]) )
1102  {
1103  assert(!SCIPisInfinity(scip_, mastercoefs[i]) && !SCIPisInfinity(scip_, -mastercoefs[i]));
1104  SCIP_CALL( SCIPaddCoefLinear(scip_, masterconss[i], newvar, mastercoefs[i]) );
1105  }
1106  }
1107 
1108  return SCIP_OKAY;
1109 }
1110 
1111 
1112 /** compute master coefficients of column */
1114  GCG_COL* gcgcol /**< GCG column data structure */
1115  )
1116 {
1117  int i;
1118 
1119  SCIP_VAR** solvars;
1120  SCIP_Real* solvals;
1121  int nsolvars;
1122 
1123  int c;
1124  int idx;
1125 
1126  assert(scip_ != NULL);
1127  assert(gcgcol != NULL);
1128 
1129  nsolvars = GCGcolGetNVars(gcgcol);
1130  solvars = GCGcolGetVars(gcgcol);
1131  solvals = GCGcolGetVals(gcgcol);
1132 
1133  int nmasterconss;
1134  SCIP_Real* mastercoefs;
1135  SCIP_CONS* linkcons;
1136  SCIP* pricingprob;
1137 
1138  int* linkvars;
1139  int nlinkvars;
1140 
1141  pricingprob = GCGcolGetPricingProb(gcgcol);
1142 
1143  nmasterconss = GCGgetNMasterConss(origprob);
1144 
1145  assert(GCGcolGetNMastercoefs(gcgcol) == 0 || GCGcolGetNMastercoefs(gcgcol) == nmasterconss);
1146 
1147  if( GCGcolGetInitializedCoefs(gcgcol) )
1148  {
1149 // SCIPdebugMessage("Coefficients already computed, nmastercoefs = %d\n", GCGcolGetNMastercoefs(gcgcol));
1150  return SCIP_OKAY;
1151  }
1152 
1153  if( nmasterconss > 0)
1154  {
1155  SCIP_CALL( SCIPallocBufferArray(pricingprob, &mastercoefs, nmasterconss) ); /*lint !e530*/
1156  BMSclearMemoryArray(mastercoefs, nmasterconss);
1157  }
1158 
1159  SCIP_CALL( SCIPallocBufferArray(pricingprob, &linkvars, nsolvars) ); /*lint !e530*/
1160 
1161  nlinkvars = 0;
1162 
1163  /* compute coef of the variable in the master constraints */
1164  for( i = 0; i < nsolvars; i++ )
1165  {
1166  if( !SCIPisZero(origprob, solvals[i]) )
1167  {
1168  SCIP_CONS** linkconss;
1169  SCIP_VAR** origvars;
1170  SCIP_Real* coefs;
1171  int ncoefs;
1172 
1173  assert(GCGvarIsPricing(solvars[i]));
1174  origvars = GCGpricingVarGetOrigvars(solvars[i]);
1175  assert(GCGvarIsOriginal(origvars[0]));
1176 
1177  coefs = GCGoriginalVarGetCoefs(origvars[0]);
1178  ncoefs = GCGoriginalVarGetNCoefs(origvars[0]);
1179  assert(!SCIPisInfinity(origprob, solvals[i]));
1180 
1181  /* original variable is a linking variable, just add it to the linkcons */
1182  if( GCGoriginalVarIsLinking(origvars[0]) )
1183  {
1184  linkvars[nlinkvars] = i;
1185  ++nlinkvars;
1186 
1187  continue;
1188  }
1189 
1190  /* for each coef, add coef * solval to the coef of the new variable for the corresponding constraint */
1191  for( c = 0; c < ncoefs; c++ )
1192  {
1193  linkconss = GCGoriginalVarGetMasterconss(origvars[0]);
1194  assert(!SCIPisZero(origprob, coefs[c]));
1195  SCIP_CALL( SCIPgetTransformedCons(scip_, linkconss[c], &linkcons) );
1196 
1197  idx = (int)(size_t)SCIPhashmapGetImage(pricerdata->mapcons2idx, linkcons); /*lint !e507*/
1198  assert(0 <= idx && idx < nmasterconss);
1199  assert(!SCIPisInfinity(scip_, ABS(coefs[c] * solvals[i])));
1200  mastercoefs[idx] += coefs[c] * solvals[i];
1201  assert(!SCIPisInfinity(scip_, ABS(mastercoefs[idx])));
1202  }
1203  }
1204  }
1205 
1206  SCIP_CALL( GCGcolSetMastercoefs(gcgcol, mastercoefs, nmasterconss) );
1207 
1208  SCIP_CALL( GCGcolSetLinkvars(gcgcol, linkvars, nlinkvars) );
1209 
1210  SCIP_CALL( GCGcolSetInitializedCoefs(gcgcol) );
1211 
1212  SCIPfreeBufferArray(pricingprob, &linkvars); /*lint !e530*/
1213 
1214  if( nmasterconss > 0)
1215  SCIPfreeBufferArray(pricingprob, &mastercoefs); /*lint !e530*/
1216 
1217  return SCIP_OKAY;
1218 }
1219 
1220 /** add variable with computed coefficients to the master cuts */
1221 SCIP_RETCODE ObjPricerGcg::addVariableToMastercuts(
1222  SCIP_VAR* newvar, /**< The new variable to add */
1223  int prob, /**< number of the pricing problem the solution belongs to */
1224  SCIP_VAR** solvars, /**< array of variables with non-zero value in the solution of the pricing problem */
1225  SCIP_Real* solvals, /**< array of values in the solution of the pricing problem for variables in array solvars*/
1226  int nsolvars /**< number of variables in array solvars */
1227  )
1228 {
1229  SCIP_ROW** mastercuts;
1230  int nmastercuts;
1231  SCIP_ROW** origcuts;
1232 
1233  SCIP_COL** cols;
1234  SCIP_Real conscoef;
1235  SCIP_VAR* var;
1236  SCIP_Real* consvals;
1237 
1238  int i;
1239  int j;
1240  int k;
1241 
1242  assert(scip_ != NULL);
1243  assert(newvar != NULL);
1244  assert(solvars != NULL || nsolvars == 0);
1245  assert(solvals != NULL || nsolvars == 0);
1246 
1247  /* get the cuts of the master problem and the corresponding cuts in the original problem */
1248  mastercuts = GCGsepaGetMastercuts(scip_);
1249  nmastercuts = GCGsepaGetNCuts(scip_);
1250  origcuts = GCGsepaGetOrigcuts(scip_);
1251 
1252  assert(mastercuts != NULL);
1253  assert(origcuts != NULL);
1254 
1255  /* compute coef of the variable in the cuts and add it to the cuts */
1256  for( i = 0; i < nmastercuts; i++ )
1257  {
1258  if( !SCIProwIsInLP(mastercuts[i]) )
1259  continue;
1260 
1261  /* get columns of the cut and their coefficients */
1262  cols = SCIProwGetCols(origcuts[i]);
1263  consvals = SCIProwGetVals(origcuts[i]);
1264 
1265  conscoef = 0;
1266 
1267  for( j = 0; j < SCIProwGetNNonz(origcuts[i]); j++ )
1268  {
1269  int blocknr;
1270  var = SCIPcolGetVar(cols[j]);
1271  blocknr = GCGvarGetBlock(var);
1272  assert(GCGvarIsOriginal(var));
1273 
1274  /* if the belongs to the same block and is no linking variable, update the coef */
1275  if( blocknr == prob )
1276  for( k = 0; k < nsolvars; k++ )
1277  if( solvars[k] == GCGoriginalVarGetPricingVar(var) )
1278  {
1279  conscoef += (consvals[j] * solvals[k]);
1280  break;
1281  }
1282  }
1283 
1284  if( !SCIPisZero(scip_, conscoef) )
1285  SCIP_CALL( SCIPaddVarToRow(scip_ , mastercuts[i], newvar, conscoef) );
1286  }
1287 
1288  return SCIP_OKAY;
1289 }
1290 
1291 /** add variable with computed coefficients to the master cuts */
1292 SCIP_RETCODE ObjPricerGcg::addVariableToMastercutsFromGCGCol(
1293  SCIP_VAR* newvar, /**< The new variable to add */
1294  GCG_COL* gcgcol /**< GCG column data structure */
1295  )
1296 {
1297  SCIP_ROW** mastercuts;
1298  int nmastercuts;
1299  SCIP_Real* mastercutcoefs;
1300  int i;
1301 
1302  assert(scip_ != NULL);
1303  assert(newvar != NULL);
1304 
1305  /* get the cuts of the master problem and the corresponding cuts in the original problem */
1306  mastercuts = GCGsepaGetMastercuts(scip_);
1307  nmastercuts = GCGsepaGetNCuts(scip_);
1308 
1309  assert(mastercuts != NULL);
1310 
1311  SCIP_CALL( computeColMastercuts(gcgcol) );
1312 
1313  mastercutcoefs = GCGcolGetMastercuts(gcgcol);
1314 
1315  /* compute coef of the variable in the cuts and add it to the cuts */
1316  for( i = 0; i < nmastercuts; i++ )
1317  {
1318  if( !SCIProwIsInLP(mastercuts[i]) )
1319  continue;
1320 
1321  if( !SCIPisZero(scip_, mastercutcoefs[i]) )
1322  SCIP_CALL( SCIPaddVarToRow(scip_ , mastercuts[i], newvar, mastercutcoefs[i]) );
1323  }
1324 
1325  return SCIP_OKAY;
1326 }
1327 
1328 
1329 /** compute master cut coefficients of column */
1331  GCG_COL* gcgcol /**< GCG column data structure */
1332  )
1333 {
1334  int prob;
1335  int i;
1336 
1337  SCIP_VAR** solvars;
1338  SCIP_Real* solvals;
1339  int nsolvars;
1340  int noldmastercuts;
1341  int nnewmastercuts;
1342  SCIP_Real* newmastercuts;
1343 
1344  assert(scip_ != NULL);
1345  assert(gcgcol != NULL);
1346 
1347  prob = GCGcolGetProbNr(gcgcol);
1348  nsolvars = GCGcolGetNVars(gcgcol);
1349  solvars = GCGcolGetVars(gcgcol);
1350  solvals = GCGcolGetVals(gcgcol);
1351 
1352  noldmastercuts = GCGcolGetNMastercuts(gcgcol);
1353 
1354  SCIP_ROW** mastercuts;
1355  int nmastercuts;
1356  SCIP_ROW** origcuts;
1357 
1358  SCIP_COL** cols;
1359  SCIP_Real conscoef;
1360  SCIP_VAR* var;
1361  SCIP_Real* consvals;
1362 
1363  int j;
1364  int k;
1365 
1366  assert(scip_ != NULL);
1367  assert(solvars != NULL);
1368  assert(solvals != NULL);
1369 
1370  /* get the cuts of the master problem and the corresponding cuts in the original problem */
1371  mastercuts = GCGsepaGetMastercuts(scip_);
1372  nmastercuts = GCGsepaGetNCuts(scip_);
1373  origcuts = GCGsepaGetOrigcuts(scip_);
1374 
1375  assert(mastercuts != NULL);
1376  assert(origcuts != NULL);
1377 
1378  assert(nmastercuts - noldmastercuts >= 0);
1379 
1380  if( nmastercuts - noldmastercuts == 0 )
1381  return SCIP_OKAY;
1382 
1383  SCIP_CALL( SCIPallocBufferArray(origprob, &newmastercuts, nmastercuts - noldmastercuts) );
1384 
1385  nnewmastercuts = 0;
1386 
1387  /* compute coef of the variable in the cuts and add it to the cuts */
1388  for( i = noldmastercuts; i < nmastercuts; i++ )
1389  {
1390  if( !SCIProwIsInLP(mastercuts[i]) )
1391  {
1392  newmastercuts[nnewmastercuts] = 0.0;
1393  ++nnewmastercuts;
1394  continue;
1395  }
1396 
1397  /* get columns of the cut and their coefficients */
1398  cols = SCIProwGetCols(origcuts[i]);
1399  consvals = SCIProwGetVals(origcuts[i]);
1400 
1401  conscoef = 0;
1402 
1403  for( j = 0; j < SCIProwGetNNonz(origcuts[i]); j++ )
1404  {
1405  int blocknr;
1406  var = SCIPcolGetVar(cols[j]);
1407  blocknr = GCGvarGetBlock(var);
1408  assert(GCGvarIsOriginal(var));
1409 
1410  /* if the belongs to the same block and is no linking variable, update the coef */
1411  if( blocknr == prob )
1412  for( k = 0; k < nsolvars; k++ )
1413  if( solvars[k] == GCGoriginalVarGetPricingVar(var) )
1414  {
1415  conscoef += ( consvals[j] * solvals[k] );
1416  break;
1417  }
1418  }
1419 
1420  newmastercuts[nnewmastercuts] = conscoef;
1421  ++nnewmastercuts;
1422  }
1423 
1424  GCGcolUpdateMastercuts(gcgcol, newmastercuts, nnewmastercuts);
1425 
1426  SCIPfreeBufferArray(origprob, &newmastercuts);
1427 
1428  return SCIP_OKAY;
1429 }
1430 
1431 /** adds new variable to the end of the priced variables array */
1432 SCIP_RETCODE ObjPricerGcg::addVariableToPricedvars(
1433  SCIP_VAR* newvar /**< variable to add */
1434  )
1435 {
1436  SCIP_CALL( ensureSizePricedvars(pricerdata->npricedvars + 1) );
1437  pricerdata->pricedvars[pricerdata->npricedvars] = newvar;
1438  GCGmasterVarSetIndex(newvar, pricerdata->npricedvars);
1439  pricerdata->npricedvars++;
1440 
1441  return SCIP_OKAY;
1442 }
1443 
1444 #ifdef SCIP_STATISTIC
1445 /** adds new bounds to the bound arrays as well as some additional information on dual variables and root lp solution */
1446 SCIP_RETCODE ObjPricerGcg::addRootBounds(
1447  SCIP_Real primalbound, /**< new primal bound for the root master LP */
1448  SCIP_Real dualbound /**< new dual bound for the root master LP */
1449  )
1450 {
1451  int nprobvars;
1452  int i;
1453  int j;
1454 
1455  SCIP_SOL* sol;
1456  SCIP_Real* solvals;
1457  SCIP_VAR** vars;
1458  int nvars;
1459 
1460  nvars = SCIPgetNVars(scip_);
1461  vars = SCIPgetVars(scip_);
1462 
1463  SCIP_CALL( ensureSizeRootBounds(pricerdata->nrootbounds + 1) );
1464  pricerdata->rootpbs[pricerdata->nrootbounds] = primalbound;
1465  pricerdata->rootdbs[pricerdata->nrootbounds] = dualbound;
1466  pricerdata->roottimes[pricerdata->nrootbounds] = SCIPgetSolvingTime(scip_) - pricerdata->rootfarkastime;
1467  pricerdata->rootdualdiffs[pricerdata->nrootbounds] = pricerdata->dualdiff;
1468 
1469  SCIPdebugMessage("Add new bounds: \n pb = %f\n db = %f\n", primalbound, dualbound);
1470 
1471  SCIP_CALL( SCIPallocBlockMemoryArray(scip_, &pricerdata->dualvalues[pricerdata->nrootbounds], pricerdata->npricingprobs) );
1472  SCIP_CALL( SCIPallocBlockMemoryArray(scip_, &pricerdata->dualsolconvs[pricerdata->nrootbounds], pricerdata->npricingprobs) );
1473 
1474  for( i = 0; i < pricerdata->npricingprobs; i++ )
1475  {
1476  if( pricerdata->pricingprobs[i] == NULL )
1477  continue;
1478 
1479  nprobvars = SCIPgetNVars(pricerdata->pricingprobs[i]);
1480 
1481  pricerdata->dualsolconvs[pricerdata->nrootbounds][i] = pricerdata->dualsolconv[i];
1482  SCIP_CALL( SCIPallocBlockMemoryArray(scip_, &(pricerdata->dualvalues[pricerdata->nrootbounds][i]), nprobvars) );
1483 
1484  for( j = 0; j < nprobvars; j++ )
1485  pricerdata->dualvalues[pricerdata->nrootbounds][i][j] = pricerdata->realdualvalues[i][j];
1486  }
1487 
1488  pricerdata->nrootbounds++;
1489 
1490  SCIP_CALL( SCIPallocBufferArray(scip_, &solvals, nvars) );
1491 
1492  SCIP_CALL( SCIPgetSolVals(scip_, NULL, nvars, vars, solvals) );
1493 
1494  SCIP_CALL( SCIPcreateSol(scip_, &sol, NULL) );
1495 
1496  SCIP_CALL( SCIPsetSolVals(scip_, sol, nvars, vars, solvals) );
1497 
1498  if( pricerdata->rootlpsol != NULL)
1499  SCIPfreeSol(scip_, &pricerdata->rootlpsol);
1500 
1501  pricerdata->rootlpsol = sol;
1502 
1503  SCIPfreeBufferArray(scip_, &solvals);
1504 
1505  return SCIP_OKAY;
1506 }
1507 #endif
1508 
1509 SCIP_Real ObjPricerGcg::computeRedCost(
1510  PricingType* pricetype, /**< type of pricing */
1511  SCIP_SOL* sol, /**< solution to compute reduced cost for */
1512  SCIP_Bool solisray, /**< is the solution a ray? */
1513  int probnr, /**< number of the pricing problem the solution belongs to */
1514  SCIP_Real* objvalptr /**< pointer to store the computed objective value */
1515  ) const
1516 {
1517  GCG_PRICINGPROB* pricingprob;
1518  SCIP* pricingscip;
1519  SCIP_CONS** branchconss; /* stack of genericbranching constraints */
1520  int nbranchconss; /* number of generic branching constraints */
1521  SCIP_Real* branchduals; /* dual values of branching constraints in the master (sigma) */
1522  int i;
1523 
1524  SCIP_VAR** solvars;
1525  SCIP_Real* solvals = NULL;
1526  int nsolvars;
1527  SCIP_Real objvalue;
1528 
1529  assert(pricerdata != NULL);
1530 
1531  pricingprob = pricingcontroller->getPricingprob(probnr);
1532  assert(pricingprob != NULL);
1533 
1534  objvalue = 0.0;
1535  pricingscip = pricerdata->pricingprobs[probnr];
1536  solvars = SCIPgetOrigVars(pricingscip);
1537  nsolvars = SCIPgetNOrigVars(pricingscip);
1538  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray(scip_, &solvals, nsolvars) );
1539  SCIP_CALL_ABORT( SCIPgetSolVals(pricingscip, sol, nsolvars, solvars, solvals) );
1540 
1541  /* compute the objective function value of the solution */
1542  for( i = 0; i < nsolvars; i++ )
1543  objvalue += solvals[i] * pricerdata->realdualvalues[probnr][SCIPvarGetProbindex(solvars[i])];
1544 
1545  if( objvalptr != NULL )
1546  *objvalptr = objvalue;
1547 
1548  /* get path to the last generic branching node */
1549  GCGpricingprobGetGenericBranchData(pricingprob, &branchconss, &branchduals, &nbranchconss);
1550 
1551  for( i = nbranchconss - 1; i >= 0; --i )
1552  {
1553  SCIP_Bool feasible;
1554  SCIP_CALL_ABORT( checkBranchingBoundChanges(probnr, sol, branchconss[i], &feasible) );
1555  if( feasible )
1556  {
1557  objvalue -= branchduals[i];
1558  }
1559  }
1560  SCIPfreeBlockMemoryArray(scip_, &solvals, nsolvars);
1561 
1562  /* compute reduced cost of variable (i.e. subtract dual solution of convexity constraint, if solution corresponds to a point) */
1563  return (solisray ? objvalue : objvalue - pricerdata->dualsolconv[probnr]);
1564 }
1565 
1567  PricingType* pricetype, /**< type of pricing */
1568  GCG_Col* gcgcol, /**< gcg column to compute reduced cost for */
1569  SCIP_Real* objvalptr /**< pointer to store the computed objective value */
1570  ) const
1571 {
1572  GCG_PRICINGPROB* pricingprob;
1573  SCIP_CONS** branchconss; /* stack of genericbranching constraints */
1574  int nbranchconss; /* number of generic branching constraints */
1575  SCIP_Real* branchduals; /* dual values of branching constraints in the master (sigma) */
1576  int i;
1577  int probnr;
1578 
1579  SCIP_Bool isray;
1580 
1581  SCIP_Real redcost;
1582 
1583  SCIP_VAR** solvars;
1584  SCIP_Real* solvals;
1585  int nsolvars;
1586  SCIP_Real objvalue;
1587 
1588  assert(pricerdata != NULL);
1589 
1590  objvalue = 0.0;
1591  probnr = GCGcolGetProbNr(gcgcol);
1592 
1593  solvars = GCGcolGetVars(gcgcol);
1594  nsolvars = GCGcolGetNVars(gcgcol);
1595  solvals = GCGcolGetVals(gcgcol);
1596  isray = GCGcolIsRay(gcgcol);
1597 
1598  pricingprob = pricingcontroller->getPricingprob(probnr);
1599  assert(pricingprob != NULL);
1600 
1601  /* compute the objective function value of the column */
1602  for( i = 0; i < nsolvars; i++ )
1603  objvalue += solvals[i] * pricerdata->realdualvalues[probnr][SCIPvarGetProbindex(solvars[i])];
1604 
1605  if( objvalptr != NULL )
1606  *objvalptr = objvalue;
1607 
1608  /* get path to the last generic branching node */
1609  GCGpricingprobGetGenericBranchData(pricingprob, &branchconss, &branchduals, &nbranchconss);
1610 
1611  for( i = nbranchconss -1; i >= 0; --i )
1612  {
1613  SCIP_Bool feasible;
1614  SCIP_CALL_ABORT( checkBranchingBoundChangesGcgCol(gcgcol, branchconss[i], &feasible) );
1615  if( feasible )
1616  {
1617  objvalue -= branchduals[i];
1618  }
1619  }
1620 
1621  redcost = (isray ? objvalue : objvalue - pricerdata->dualsolconv[probnr]);
1622 
1623  GCGcolUpdateRedcost(gcgcol, redcost, FALSE);
1624 
1625  return redcost;
1626 }
1627 
1628 /** for given columns, (re-)compute and update their reduced costs */
1630  PricingType* pricetype, /**< type of pricing */
1631  GCG_COL** cols, /**< columns to compute reduced costs for */
1632  int ncols /**< number of columns */
1633  ) const
1634 {
1635  SCIPdebugMessage("Update reduced costs\n");
1636 
1637  for( int i = 0; i < ncols; ++i )
1638  {
1639  SCIP_Real redcost = computeRedCostGcgCol(pricetype, cols[i], NULL);
1640  GCGcolUpdateRedcost(cols[i], redcost, FALSE);
1641 
1642  SCIPdebugMessage(" -> column %d/%d <%p>, reduced cost = %g\n", i+1, ncols, (void*) cols[i], redcost);
1643  }
1644 }
1645 
1646 /** add a new column to the pricing storage */
1648  GCG_COL* col /**< priced col */
1649  )
1650 {
1651  SCIP_RETCODE retcode;
1652 
1653  assert(col != NULL);
1654  assert(pricingtype != NULL);
1655 
1656  SCIP_Real redcost = computeRedCostGcgCol(pricingtype, col, NULL);
1657  GCGcolUpdateRedcost(col, redcost, FALSE);
1658 
1659  SCIPdebugMessage(" -> new column <%p>, reduced cost = %g\n", (void*) col, redcost);
1660 
1661  #pragma omp critical (update)
1662  {
1663  retcode = GCGpricestoreAddCol(scip_, pricestore, col, FALSE);
1664  }
1665  SCIP_CALL( retcode );
1666 
1667  return SCIP_OKAY;
1668 }
1669 
1670 /** for each pricing problem, get the best found column from the pricing storage */
1672  GCG_COL** pricingprobcols /**< array to be filled with best column per pricing problem */
1673  )
1674 {
1675  GCG_COL** cols;
1676  int ncols;
1677 
1678  int i;
1679 
1680  assert(pricingprobcols != NULL);
1681 
1682  cols = GCGpricestoreGetCols(pricestore);
1683  ncols = GCGpricestoreGetNCols(pricestore);
1684 
1685  for( i = 0; i < pricerdata->npricingprobs; ++i )
1686  pricingprobcols[i] = NULL;
1687 
1688  for( i = 0; i < ncols; ++i )
1689  {
1690  int probnr = GCGcolGetProbNr(cols[i]);
1691 
1692  if( pricingprobcols[probnr] == NULL
1693  || SCIPisDualfeasLT(scip_, GCGcolGetRedcost(cols[i]), GCGcolGetRedcost(pricingprobcols[probnr])) )
1694  pricingprobcols[probnr] = cols[i];
1695  }
1696 }
1697 
1698 /** get the sum over the dual values of convexity constraints */
1700  GCG_COL** bestcols /**< best columns found per pricing problem */
1701  )
1702 {
1703  SCIP_Real dualconvsum = 0.0;
1704 
1705  assert(pricingtype != NULL);
1706 
1707  for( int i = 0; i < pricerdata->npricingprobs; ++i )
1708  {
1709  if( GCGisPricingprobRelevant(origprob, i) && (bestcols[i] == NULL || !GCGcolIsRay(bestcols[i])) )
1710  dualconvsum += GCGgetNIdenticalBlocks(origprob, i) * pricingtype->consGetDual(scip_, GCGgetConvCons(origprob, i));
1711  }
1712 
1713  return dualconvsum;
1714 }
1715 
1716 /* computes the objective value of the current (stabilized) dual variables) in the dual program */
1718  PricingType* pricetype, /**< type of pricing */
1719  SCIP_Real* stabdualval, /**< pointer to store stabilized dual objective value */
1720  SCIP_Bool stabilize /**< stabilize? */
1721 )
1722 {
1723  SCIP_VAR** mastervars;
1724  int nmastervars;
1725 
1726  SCIP_CONS** origconss;
1727 
1728  SCIP_ROW** origcuts;
1729  SCIP_COL** cols;
1730  SCIP_Real* consvals;
1731 
1732  SCIP_VAR** consvars = NULL;
1733  int nconsvars;
1734  int j;
1735 
1736  SCIP_Real dualobjval;
1737  SCIP_Real dualsol;
1738  SCIP_Real boundval;
1739 
1740  SCIP_CONS** masterconss;
1741  int nmasterconss;
1742 
1743  int nlinkconss;
1744  SCIP_CONS** linkconss;
1745 
1746  SCIP_ROW** mastercuts;
1747  int nmastercuts;
1748  int i;
1749 
1750  SCIP_Real* stabredcosts;
1751 
1752  assert(stabilization != NULL);
1753  assert(stabdualval != NULL);
1754 
1755  *stabdualval = 0.0;
1756 
1757  /* get the constraints of the master problem and the corresponding constraints in the original problem */
1758  nmasterconss = GCGgetNMasterConss(origprob);
1759  masterconss = GCGgetMasterConss(origprob);
1760  origconss = GCGgetOrigMasterConss(origprob);
1761 
1762  dualobjval = 0.0;
1763 
1764  nlinkconss = GCGgetNVarLinkingconss(origprob);
1765  linkconss = GCGgetVarLinkingconss(origprob);
1766 
1767  /* get the cuts of the master problem */
1768  mastercuts = GCGsepaGetMastercuts(scip_);
1769  nmastercuts = GCGsepaGetNCuts(scip_);
1770 
1771  assert(mastercuts != NULL);
1772 
1773  /* compute lhs/rhs * dual for linking constraints and add it to dualobjval */
1774  for( i = 0; i < nlinkconss; ++i )
1775  {
1776  SCIP_CONS* linkcons = linkconss[i];
1777 #ifndef NDEBUG
1778  SCIP_VAR** linkconsvars;
1779  int block = GCGgetVarLinkingconssBlock(origprob)[i];
1780 
1781  linkconsvars = SCIPgetVarsLinear(scip_, linkcons);
1782 
1783  SCIP_VAR* linkvar = linkconsvars[0];
1784 
1786 #endif
1787 
1788  if( stabilize )
1789  dualsol = stabilization->linkingconsGetDual(i);
1790  else
1791  dualsol = pricetype->consGetDual(scip_, linkcons);
1792 
1793  if( SCIPisFeasPositive(scip_, dualsol) )
1794  boundval = SCIPgetLhsLinear(scip_, linkcons);
1795  else if( SCIPisFeasNegative(scip_, dualsol) )
1796  boundval = SCIPgetRhsLinear(scip_, linkcons);
1797  else
1798  continue;
1799 
1800  assert(SCIPisZero(scip_, boundval));
1801 
1802  if( !SCIPisZero(scip_, boundval) )
1803  dualobjval += boundval * dualsol;
1804  }
1805 
1806 
1807  /* compute lhs/rhs * dual for master constraints and add it to dualobjval */
1808  for( i = 0; i < nmasterconss; i++ )
1809  {
1810  if( stabilize )
1811  SCIP_CALL( stabilization->consGetDual(i, &dualsol) );
1812  else
1813  dualsol = pricetype->consGetDual(scip_, masterconss[i]);
1814 
1815  if( SCIPisFeasPositive(scip_, dualsol) )
1816  boundval = GCGconsGetLhs(scip_, origconss[i]);
1817  else if( SCIPisFeasNegative(scip_, dualsol) )
1818  boundval = GCGconsGetRhs(scip_, origconss[i]);
1819  else
1820  continue;
1821 
1822  if( !SCIPisZero(scip_, boundval) )
1823  dualobjval += boundval * dualsol;
1824  }
1825 
1826  /* compute lhs/rhs * dual for master cuts and add it to dualobjval */
1827  for( i = 0; i < nmastercuts; i++ )
1828  {
1829  if( stabilize )
1830  SCIP_CALL( stabilization->rowGetDual(i, &dualsol) );
1831  else
1832  dualsol = pricetype->rowGetDual(mastercuts[i]);
1833 
1834  if( SCIPisFeasPositive(scip_, dualsol) )
1835  boundval = SCIProwGetLhs(mastercuts[i]);
1836  else if( SCIPisFeasNegative(scip_, dualsol) )
1837  boundval = SCIProwGetRhs(mastercuts[i]);
1838  else
1839  continue;
1840 
1841  if( !SCIPisZero(scip_, boundval) )
1842  dualobjval += boundval * dualsol;
1843  }
1844 
1845  /* get master variables that were directly transferred or that are linking */
1846  mastervars = SCIPgetOrigVars(scip_);
1847  nmastervars = GCGgetNTransvars(origprob) + GCGgetNLinkingvars(origprob);
1848 
1849  assert(nmastervars <= SCIPgetNOrigVars(scip_));
1850 
1851  /* no linking or directly transferred variables exist, set stabdualval pointer and exit */
1852  if( nmastervars == 0 )
1853  {
1854  *stabdualval = dualobjval;
1855 
1856  return SCIP_OKAY;
1857  }
1858 
1859  /* allocate memory for array with (stabilizied) reduced cost coefficients */
1860  SCIP_CALL( SCIPallocBufferArray(scip_, &stabredcosts, nmastervars) );
1861 
1862  /* initialize (stabilized) reduced cost with objective coefficients */
1863  for( i = 0; i < nmastervars; i++ )
1864  {
1865  assert(GCGvarGetBlock(mastervars[i]) == -1);
1866  assert( GCGoriginalVarIsLinking(GCGmasterVarGetOrigvars(mastervars[i])[0]) || GCGoriginalVarIsTransVar(GCGmasterVarGetOrigvars(mastervars[i])[0]) );
1867 
1868  stabredcosts[i] = SCIPvarGetObj(mastervars[i]);
1869  }
1870 
1871  /* compute reduced cost for linking variable constraints and update (stabilized) reduced cost coefficients
1872  * go through constraints, and select correct variable
1873  */
1874  nlinkconss = GCGgetNVarLinkingconss(origprob);
1875  linkconss = GCGgetVarLinkingconss(origprob);
1876 
1877  for( i = 0; i < nlinkconss; ++i )
1878  {
1879  SCIP_VAR** linkconsvars;
1880  SCIP_CONS* linkcons = linkconss[i];
1881  int varindex;
1882 
1883  linkconsvars = SCIPgetVarsLinear(scip_, linkcons);
1884 
1885  SCIP_VAR* linkvar = linkconsvars[0];
1886 
1887  varindex = SCIPvarGetProbindex(linkvar);
1888  assert(varindex < nmastervars);
1889 
1890  if( stabilize )
1891  {
1892  dualsol = stabilization->linkingconsGetDual(i);
1893  }
1894  else
1895  {
1896  dualsol = pricetype->consGetDual(scip_, linkcons);
1897  }
1898 
1899  /* substract dual solution value to the linking variable:
1900  * linking variables get coef 11 in linking constraints --> substract dualsol
1901  */
1902  stabredcosts[varindex] -= dualsol;
1903  }
1904 
1905  /* compute reduced cost for master constraints and update (stabilized) reduced cost coefficients */
1906  for( i = 0; i < nmasterconss; i++ )
1907  {
1908  if( stabilize )
1909  {
1910  SCIP_CALL( stabilization->consGetDual(i, &dualsol) );
1911  }
1912  else
1913  {
1914  dualsol = pricetype->consGetDual(scip_, masterconss[i]);
1915  }
1916 
1917  if( !SCIPisZero(scip_, dualsol) )
1918  {
1919  /* for all variables in the constraint, modify the objective of the corresponding variable in a pricing problem */
1920  nconsvars = GCGconsGetNVars(origprob, origconss[i]);
1921  SCIP_CALL( SCIPallocBufferArray(scip_, &consvars, nconsvars) );
1922  SCIP_CALL( SCIPallocBufferArray(scip_, &consvals, nconsvars) );
1923  GCGconsGetVars(origprob, origconss[i], consvars, nconsvars);
1924  GCGconsGetVals(origprob, origconss[i], consvals, nconsvars);
1925  for( j = 0; j < nconsvars; j++ )
1926  {
1927  SCIP_VAR* mastervar;
1928  int blocknr;
1929 
1930  assert(GCGvarIsOriginal(consvars[j]));
1931 
1932  if( GCGoriginalVarGetNMastervars(consvars[j]) == 0 )
1933  continue;
1934  assert( GCGoriginalVarGetNMastervars(consvars[j]) > 0 );
1935 
1936  mastervar = GCGoriginalVarGetMastervars(consvars[j])[0];
1937  blocknr = GCGvarGetBlock(mastervar);
1938 
1939  /* nothing to be done if variable belongs to redundant block or variable was directly transferred to the master
1940  * or variable is linking variable (which means, the directly transferred copy is part of the master cons)
1941  */
1942  if( blocknr < 0 )
1943  {
1944  int varindex;
1945  varindex = SCIPvarGetProbindex(mastervar);
1946  assert(varindex < nmastervars);
1947 
1948  stabredcosts[varindex] -= dualsol * consvals[j];
1949  }
1950  }
1951  SCIPfreeBufferArray(scip_, &consvals);
1952  SCIPfreeBufferArray(scip_, &consvars);
1953  }
1954  }
1955 
1956  /* get the cuts of the master problem and the corresponding cuts in the original problem */
1957  mastercuts = GCGsepaGetMastercuts(scip_);
1958  nmastercuts = GCGsepaGetNCuts(scip_);
1959  origcuts = GCGsepaGetOrigcuts(scip_);
1960 
1961  assert(mastercuts != NULL);
1962  assert(origcuts != NULL);
1963 
1964  /* compute reduced cost for master cuts and update (stabilized) reduced cost coefficients */
1965  for( i = 0; i < nmastercuts; i++ )
1966  {
1967  if( stabilize )
1968  {
1969  SCIP_CALL( stabilization->rowGetDual(i, &dualsol) );
1970  }
1971  else
1972  {
1973  dualsol = pricetype->rowGetDual(mastercuts[i]);
1974  }
1975 
1976  if( !SCIPisZero(scip_, dualsol) )
1977  {
1978  /* get columns and vals of the cut */
1979  nconsvars = SCIProwGetNNonz(origcuts[i]);
1980  cols = SCIProwGetCols(origcuts[i]);
1981  consvals = SCIProwGetVals(origcuts[i]);
1982 
1983  /* get the variables corresponding to the columns in the cut */
1984  SCIP_CALL( SCIPallocBufferArray(scip_, &consvars, nconsvars) );
1985  for( j = 0; j < nconsvars; j++ )
1986  consvars[j] = SCIPcolGetVar(cols[j]);
1987 
1988  /* for all variables in the cut, modify the objective of the corresponding variable in a pricing problem */
1989  for( j = 0; j < nconsvars; j++ )
1990  {
1991  SCIP_VAR* mastervar;
1992  int blocknr;
1993 
1994  assert(GCGvarIsOriginal(consvars[j]));
1995 
1996  if( GCGoriginalVarGetNMastervars(consvars[j]) == 0 )
1997  continue;
1998  assert( GCGoriginalVarGetNMastervars(consvars[j]) > 0 );
1999 
2000  mastervar = GCGoriginalVarGetMastervars(consvars[j])[0];
2001  blocknr = GCGvarGetBlock(mastervar);
2002 
2003  /* nothing to be done if variable belongs to redundant block or variable was directly transferred to the master
2004  * or variable is linking variable (which means, the directly transferred copy is part of the master cons)
2005  */
2006  if( blocknr < 0 )
2007  {
2008  int varindex;
2009  varindex = SCIPvarGetProbindex(mastervar);
2010  assert(varindex < nmastervars);
2011 
2012  stabredcosts[varindex] -= dualsol * consvals[j];
2013  }
2014  }
2015  SCIPfreeBufferArray(scip_, &consvars);
2016  }
2017  }
2018 
2019  /* add redcost coefficients * lb/ub of linking or directly transferred variables */
2020  for( i = 0; i < nmastervars; ++i )
2021  {
2022  SCIP_Real stabredcost;
2023  SCIP_VAR* mastervar;
2024 
2025  mastervar = mastervars[i];
2026  stabredcost = stabredcosts[i];
2027  if( SCIPisPositive(scip_, stabredcost) )
2028  {
2029  boundval = SCIPvarGetLbLocal(mastervar);
2030  }
2031  else if( SCIPisNegative(scip_, stabredcost) )
2032  {
2033  boundval = SCIPvarGetUbLocal(mastervar);
2034  }
2035  else
2036  continue;
2037 
2038  if( SCIPisPositive(scip_, boundval) )
2039  dualobjval += boundval * stabredcost;
2040 
2041  }
2042 
2043  SCIPfreeBufferArray(scip_, &stabredcosts);
2044 
2045  *stabdualval = dualobjval;
2046 
2047  return SCIP_OKAY;
2048 }
2049 
2050 /** creates a new master variable corresponding to the given solution and problem */
2052  SCIP* scip, /**< SCIP data structure */
2053  PricingType* pricetype, /**< type of pricing */
2054  SCIP_SOL* sol, /**< solution to compute reduced cost for */
2055  SCIP_VAR** solvars, /**< array of variables with non-zero value in the solution of the pricing problem */
2056  SCIP_Real* solvals, /**< array of values in the solution of the pricing problem for variables in array solvars*/
2057  int nsolvars, /**< number of variables in array solvars */
2058  SCIP_Bool solisray, /**< is the solution a ray? */
2059  int prob, /**< number of the pricing problem the solution belongs to */
2060  SCIP_Bool force, /**< should the given variable be added also if it has non-negative reduced cost? */
2061  SCIP_Bool* added, /**< pointer to store whether the variable was successfully added */
2062  SCIP_VAR** addedvar /**< pointer to store the created variable */
2063  )
2064 {
2065  char varname[SCIP_MAXSTRLEN];
2066 
2067  SCIP_Real objcoeff;
2068  SCIP_VAR* newvar;
2069 
2070  SCIP_Real objvalue;
2071  SCIP_Real redcost;
2072  int i;
2073 
2074  assert(scip != NULL);
2075  assert(solvars != NULL || nsolvars == 0);
2076  assert(solvals != NULL || nsolvars == 0);
2077  assert(nsolvars >= 0);
2078  assert(pricerdata != NULL);
2079  assert((pricetype == NULL) == (force));
2080  assert((pricetype == NULL) == (sol == NULL));
2081  if( addedvar != NULL )
2082  *addedvar = NULL;
2083 
2084  objvalue = 0.0;
2085  redcost = 0.0;
2086 
2087  if( !force )
2088  {
2089  /* compute the objective function value of the solution */
2090  redcost = computeRedCost(pricetype, sol, solisray, prob, &objvalue);
2091 
2092  if( !SCIPisDualfeasNegative(scip, redcost) )
2093  {
2094  SCIPdebugMessage("var with redcost %g (objvalue=%g, dualsol=%g, ray=%u) was not added\n", redcost, objvalue, pricerdata->dualsolconv[prob], solisray);
2095  *added = FALSE;
2096 
2097  return SCIP_OKAY;
2098  }
2099  SCIPdebugMessage("found var with redcost %g (objvalue=%g, dualsol=%g, ray=%u)\n", redcost, objvalue, pricerdata->dualsolconv[prob], solisray);
2100  }
2101  else
2102  {
2103  SCIPdebugMessage("force var (objvalue=%g, dualsol=%g, ray=%u)\n", objvalue, pricerdata->dualsolconv[prob], solisray);
2104  }
2105 
2106  *added = TRUE;
2107 
2108  /* compute objective coefficient of the variable */
2109  objcoeff = 0;
2110  for( i = 0; i < nsolvars; i++ )
2111  {
2112  SCIP_Real solval;
2113  solval = solvals[i];
2114 
2115  if( !SCIPisZero(scip, solval) )
2116  {
2117  SCIP_VAR* origvar;
2118 
2119  assert(GCGvarIsPricing(solvars[i]));
2120  origvar = GCGpricingVarGetOrigvars(solvars[i])[0];
2121 
2122  if( SCIPisZero(scip, SCIPvarGetObj(origvar)) )
2123  continue;
2124 
2125  /* original variable is linking variable --> directly transferred master variable got the full obj,
2126  * priced-in variables get no objective value for this origvar */
2127  if( GCGoriginalVarIsLinking(origvar) )
2128  continue;
2129 
2130  /* round solval if possible to avoid numerical troubles */
2131  if( SCIPvarIsIntegral(solvars[i]) && SCIPisFeasIntegral(scip, solval) )
2132  solval = SCIPround(scip, solval);
2133 
2134  /* add quota of original variable's objcoef to the master variable's coef */
2135  objcoeff += solval * SCIPvarGetObj(origvar);
2136  }
2137  }
2138 
2139  if( SCIPisInfinity(scip, objcoeff) )
2140  {
2141  SCIPwarningMessage(scip, "variable with infinite objective value found in pricing, change objective to SCIPinfinity()/2\n");
2142  objcoeff = SCIPinfinity(scip) / 2;
2143  }
2144 
2145  if( solisray )
2146  {
2147  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "r_%d_%d", prob, pricerdata->nraysprob[prob]);
2148  pricerdata->nraysprob[prob]++;
2149  }
2150  else
2151  {
2152  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "p_%d_%d", prob, pricerdata->npointsprob[prob]);
2153  pricerdata->npointsprob[prob]++;
2154  }
2155 
2156  SCIP_CALL( GCGcreateMasterVar(scip, origprob, pricerdata->pricingprobs[prob], &newvar, varname, objcoeff,
2157  pricerdata->vartype, solisray, prob, nsolvars, solvals, solvars, FALSE));
2158 
2159  SCIPvarMarkDeletable(newvar);
2160 
2161  SCIP_CALL( SCIPcatchVarEvent(scip, newvar, SCIP_EVENTTYPE_VARDELETED,
2162  pricerdata->eventhdlr, NULL, NULL) );
2163 
2164 
2165  /* add variable */
2166  if( !force )
2167  {
2168  SCIP_CALL( SCIPaddPricedVar(scip, newvar, pricerdata->dualsolconv[prob] - objvalue) );
2169  }
2170  else
2171  {
2172  SCIP_CALL( SCIPaddVar(scip, newvar) );
2173  }
2174 
2175  SCIP_CALL( addVariableToPricedvars(newvar) );
2176  SCIP_CALL( addVariableToMasterconstraints(newvar, prob, solvars, solvals, nsolvars) );
2177  SCIP_CALL( addVariableToMastercuts(newvar, prob, solvars, solvals, nsolvars) );
2178 
2179  /* add variable to convexity constraint */
2180  if( !solisray )
2181  {
2182  SCIP_CALL( SCIPaddCoefLinear(scip, GCGgetConvCons(origprob, prob), newvar, 1.0) );
2183  }
2184 
2185  if( addedvar != NULL )
2186  {
2187  *addedvar = newvar;
2188  }
2189 
2190  GCGupdateVarStatistics(scip, origprob, newvar, redcost);
2191 
2192 #ifdef SCIP_STATISTIC
2193  if( SCIPgetCurrentNode(scip) == SCIPgetRootNode(scip) && pricetype != NULL && pricetype->getType() == GCG_PRICETYPE_REDCOST )
2194  GCGsetRootRedcostCall(newvar, pricerdata->nrootbounds );
2195 #else
2196  GCGsetRootRedcostCall(newvar, -1LL);
2197 #endif
2198 
2199  SCIPdebugMessage("Added variable <%s>\n", varname);
2200 
2201  return SCIP_OKAY;
2202 }
2203 
2204 /** creates a new master variable corresponding to the given gcg column */
2206  SCIP* scip, /**< SCIP data structure */
2207  PricingType* pricetype, /**< type of pricing */
2208  GCG_COL* gcgcol, /**< GCG column data structure */
2209  SCIP_Bool force, /**< should the given variable be added also if it has non-negative reduced cost? */
2210  SCIP_Bool* added, /**< pointer to store whether the variable was successfully added */
2211  SCIP_VAR** addedvar, /**< pointer to store the created variable */
2212  SCIP_Real score /**< score of column (or -1.0 if not specified) */
2213  )
2214 {
2215  char varname[SCIP_MAXSTRLEN];
2216 
2217  SCIP_Real objcoeff;
2218  SCIP_VAR* newvar;
2219 
2220  SCIP_Real redcost;
2221  SCIP_Bool isray;
2222  int prob;
2223  int i;
2224 
2225  SCIP_VAR** solvars;
2226  SCIP_Real* solvals;
2227  int nsolvars;
2228 
2229  assert(scip != NULL);
2230  assert(pricerdata != NULL);
2231  assert(gcgcol != NULL);
2232  assert((pricetype == NULL) == (force));
2233 
2234  if( addedvar != NULL )
2235  *addedvar = NULL;
2236 
2237  redcost = 0.0;
2238 
2239  prob = GCGcolGetProbNr(gcgcol);
2240  isray = GCGcolIsRay(gcgcol);
2241  nsolvars = GCGcolGetNVars(gcgcol);
2242  solvars = GCGcolGetVars(gcgcol);
2243  solvals = GCGcolGetVals(gcgcol);
2244 
2245  if( !force )
2246  {
2247  /* compute the objective function value of the solution */
2248  redcost = GCGcolGetRedcost(gcgcol);
2249 
2250  if( !SCIPisDualfeasNegative(scip, redcost) )
2251  {
2252  SCIPdebugMessage(" var with redcost %g (dualsol=%g, ray=%u) was not added\n", redcost, pricerdata->dualsolconv[prob], isray);
2253  *added = FALSE;
2254 
2255  return SCIP_OKAY;
2256  }
2257  SCIPdebugMessage(" found var with redcost %g (dualsol=%g, ray=%u)\n", redcost, pricerdata->dualsolconv[prob], isray);
2258  }
2259  else
2260  {
2261  SCIPdebugMessage(" force var (dualsol=%g, ray=%u)\n", pricerdata->dualsolconv[prob], isray);
2262  }
2263 
2264  *added = TRUE;
2265 
2266  /* compute objective coefficient of the variable */
2267  objcoeff = 0.0;
2268  for( i = 0; i < nsolvars; i++ )
2269  {
2270  SCIP_Real solval;
2271  solval = solvals[i];
2272 
2273  if( !SCIPisZero(scip, solvals[i]) )
2274  {
2275  SCIP_VAR* origvar;
2276 
2277  assert(GCGvarIsPricing(solvars[i]));
2278  origvar = GCGpricingVarGetOrigvars(solvars[i])[0];
2279  solval = solvals[i];
2280 
2281  if( SCIPisZero(scip, SCIPvarGetObj(origvar)) )
2282  continue;
2283 
2284  /* original variable is linking variable --> directly transferred master variable got the full obj,
2285  * priced-in variables get no objective value for this origvar */
2286  if( GCGoriginalVarIsLinking(origvar) )
2287  continue;
2288 
2289  /* add quota of original variable's objcoef to the master variable's coef */
2290  objcoeff += solval * SCIPvarGetObj(origvar);
2291  }
2292  }
2293 
2294  if( SCIPisInfinity(scip, objcoeff) )
2295  {
2296  SCIPwarningMessage(scip, "variable with infinite objective value found in pricing, change objective to SCIPinfinity()/2\n");
2297  objcoeff = SCIPinfinity(scip) / 2;
2298  }
2299 
2300  if( isray )
2301  {
2302  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "r_%d_%d", prob, pricerdata->nraysprob[prob]);
2303  pricerdata->nraysprob[prob]++;
2304  }
2305  else
2306  {
2307  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "p_%d_%d", prob, pricerdata->npointsprob[prob]);
2308  pricerdata->npointsprob[prob]++;
2309  }
2310 
2311  SCIP_CALL( GCGcreateMasterVar(scip, GCGmasterGetOrigprob(scip), pricerdata->pricingprobs[prob], &newvar, varname, objcoeff,
2312  pricerdata->vartype, isray, prob, nsolvars, solvals, solvars, FALSE));
2313 
2314  SCIPvarMarkDeletable(newvar);
2315 
2316  SCIP_CALL( SCIPcatchVarEvent(scip, newvar, SCIP_EVENTTYPE_VARDELETED,
2317  pricerdata->eventhdlr, NULL, NULL) );
2318 
2319  if( SCIPisNegative(scip, score) )
2320  score = pricerdata->dualsolconv[prob] - objcoeff;
2321 
2322  /* add variable */
2323  if( !force )
2324  {
2325  SCIP_CALL( SCIPaddPricedVar(scip, newvar, score /* pricerdata->dualsolconv[prob] - objvalue */ ) );
2326  }
2327  else
2328  {
2329  SCIP_CALL( SCIPaddVar(scip, newvar) );
2330  }
2331 
2332  SCIP_CALL( addVariableToPricedvars(newvar) );
2333  SCIP_CALL( addVariableToMasterconstraintsFromGCGCol(newvar, gcgcol) );
2334  SCIP_CALL( addVariableToMastercutsFromGCGCol(newvar, gcgcol) );
2335 
2336  /* add variable to convexity constraint */
2337  if( !isray )
2338  {
2339  SCIP_CALL( SCIPaddCoefLinear(scip, GCGgetConvCons(origprob, prob), newvar, 1.0) );
2340  }
2341 
2342  if( addedvar != NULL )
2343  {
2344  *addedvar = newvar;
2345  }
2346 
2347  GCGupdateVarStatistics(scip, origprob, newvar, redcost);
2348 
2349 #ifdef SCIP_STATISTIC
2350  if( SCIPgetCurrentNode(scip) == SCIPgetRootNode(scip) && pricetype->getType() == GCG_PRICETYPE_REDCOST )
2351  GCGsetRootRedcostCall(newvar, pricerdata->nrootbounds );
2352 #else
2353  GCGsetRootRedcostCall(newvar, -1LL);
2354 #endif
2355 
2356  SCIPdebugMessage(" added variable <%s>\n", varname);
2357 
2358  return SCIP_OKAY;
2359 }
2360 
2361 /**
2362  * check whether pricing can be aborted:
2363  * if objective value is always integral and the current node's current
2364  * lowerbound rounded up equals the current lp objective value rounded
2365  * up we don't need to continue pricing since the best possible feasible
2366  * solution must have at least this value
2367  */
2368 SCIP_Bool ObjPricerGcg::canPricingBeAborted() const
2369 {
2370  SCIP_Bool canabort = FALSE;
2371 
2372  assert(pricerdata != NULL);
2373 
2374  if( pricerdata->abortpricingint && SCIPisObjIntegral(scip_)
2375  && SCIPisEQ(scip_, SCIPceil(scip_, SCIPgetNodeLowerbound(scip_, SCIPgetCurrentNode(scip_))), SCIPceil(scip_, SCIPgetLPObjval(scip_))) /* && SCIPgetNNodes(scip) > 1 ??????*/)
2376  {
2377  GCGpricerPrintInfo(scip_, pricerdata, "pricing aborted due to integral objective: node LB = %g, LP obj = %g\n",
2378  SCIPgetNodeLowerbound(scip_, SCIPgetCurrentNode(scip_)), SCIPgetLPObjval(scip_));
2379 
2380  canabort = TRUE;
2381  }
2382 
2383  if( !canabort && pricerdata->abortpricinggap > 0.0 )
2384  {
2385  SCIP_Real gap;
2386  gap = (SCIPgetLPObjval(scip_) - SCIPgetNodeLowerbound(scip_, SCIPgetCurrentNode(scip_)))/SCIPgetNodeLowerbound(scip_, SCIPgetCurrentNode(scip_));
2387  gap = ABS(gap);
2388 
2389  if( gap < pricerdata->abortpricinggap )
2390  {
2391  GCGpricerPrintInfo(scip_, pricerdata, "pricing aborted due to small gap: node LB = %g, LP obj = %g, gap = %g\n",
2392  SCIPgetNodeLowerbound(scip_, SCIPgetCurrentNode(scip_)), SCIPgetLPObjval(scip_), gap);
2393 
2394  canabort = TRUE;
2395  }
2396  }
2397 
2398  return canabort;
2399 }
2400 
2401 
2402 /** free pricing problems */
2403 SCIP_RETCODE ObjPricerGcg::freePricingProblems()
2404 {
2405  int j;
2406  assert(pricerdata != NULL);
2407  assert(pricerdata->pricingprobs != NULL);
2408 
2409  for( j = 0; j < pricerdata->npricingprobs; j++ )
2410  if( pricerdata->pricingprobs[j] != NULL
2411  && SCIPgetStage(pricerdata->pricingprobs[j]) > SCIP_STAGE_PROBLEM)
2412  {
2413  SCIP_CALL( SCIPstartClock(scip_, pricerdata->freeclock) );
2414  SCIP_CALL( SCIPfreeTransform(pricerdata->pricingprobs[j]) );
2415  SCIP_CALL( SCIPstopClock(scip_, pricerdata->freeclock) );
2416  }
2417 
2418  return SCIP_OKAY;
2419 }
2420 
2421 /** add bounds change from constraint from the pricing problem at this node
2422  * @note This method has to be threadsafe!
2423  */
2424 SCIP_RETCODE ObjPricerGcg::addBranchingBoundChangesToPricing(
2425  int prob, /**< index of pricing problem */
2426  SCIP_CONS* branchcons /**< branching constraints from which bound should applied */
2427 ) const
2428 {
2429  GCG_BRANCHDATA* branchdata = GCGconsMasterbranchGetBranchdata(branchcons);
2430  GCG_COMPSEQUENCE* components = GCGbranchGenericBranchdataGetConsS(branchdata);
2431  int ncomponents = GCGbranchGenericBranchdataGetConsSsize(branchdata);
2432  int i;
2433 
2434  assert(pricerdata != NULL);
2435 
2436  for( i = 0; i < ncomponents; ++i)
2437  {
2438  SCIP_Real bound = components[i].bound;
2439  SCIP_VAR* var = GCGoriginalVarGetPricingVar(components[i].component);
2440  SCIP_Bool infeasible = FALSE;
2441  SCIP_Bool tightened = TRUE;
2442 
2443  if( components[i].sense == GCG_COMPSENSE_GE )
2444  {
2445  SCIP_CALL( SCIPtightenVarLb(pricerdata->pricingprobs[prob], var, bound, TRUE, &infeasible, &tightened));
2446  SCIPdebugMessage("Added <%s> >= %.2f\n", SCIPvarGetName(var), bound);
2447  assert(infeasible || tightened || SCIPisGE(pricerdata->pricingprobs[prob], SCIPvarGetLbGlobal(var), bound));
2448  }
2449  else
2450  {
2451  SCIP_CALL( SCIPtightenVarUb(pricerdata->pricingprobs[prob], var, bound-1, TRUE, &infeasible, &tightened));
2452  SCIPdebugMessage("Added <%s> <= %.2f\n", SCIPvarGetName(var), bound-1);
2453  assert(infeasible || tightened || SCIPisLE(pricerdata->pricingprobs[prob], SCIPvarGetUbGlobal(var), bound-1));
2454  }
2455  }
2456 
2457  return SCIP_OKAY;
2458 }
2459 
2460 /** check bounds change from constraint from the pricing problem at this node
2461  * @note This method has to be threadsafe!
2462  */
2463 SCIP_RETCODE ObjPricerGcg::checkBranchingBoundChanges(
2464  int prob, /**< index of pricing problem */
2465  SCIP_SOL* sol, /**< solution to check */
2466  SCIP_CONS* branchcons, /**< branching constraints from which bound should applied */
2467  SCIP_Bool* feasible /**< check whether the solution is feasible */
2468 ) const
2469 {
2470  GCG_BRANCHDATA* branchdata = GCGconsMasterbranchGetBranchdata(branchcons);
2471  GCG_COMPSEQUENCE* components = GCGbranchGenericBranchdataGetConsS(branchdata);
2472  int ncomponents = GCGbranchGenericBranchdataGetConsSsize(branchdata);
2473  int i;
2474 
2475  assert(pricerdata != NULL);
2476 
2477  for( i = 0; i < ncomponents; ++i)
2478  {
2479  SCIP_VAR* pricingvar = GCGoriginalVarGetPricingVar(components[i].component);
2480  SCIP_Real val = SCIPgetSolVal(pricerdata->pricingprobs[prob], sol, pricingvar);
2481 
2482  if( components[i].sense == GCG_COMPSENSE_GE )
2483  {
2484  *feasible = SCIPisFeasGE(pricerdata->pricingprobs[prob], val, components[i].bound);
2485  SCIPdebugMessage("<%s> %.4f >= %.4f\n", SCIPvarGetName(pricingvar), val, components[i].bound);
2486  }
2487  else
2488  {
2489  *feasible = SCIPisFeasLT(pricerdata->pricingprobs[prob], val, components[i].bound);
2490  SCIPdebugMessage("<%s> %.4f < %.4f\n", SCIPvarGetName(pricingvar), val, components[i].bound);
2491  }
2492  if( !*feasible )
2493  break;
2494  }
2495 
2496  return SCIP_OKAY;
2497 }
2498 
2499 
2500 /** check bounds change from constraint from the pricing problem at this node
2501  * @note This method has to be threadsafe!
2502  */
2503 SCIP_RETCODE ObjPricerGcg::checkBranchingBoundChangesGcgCol(
2504  GCG_COL* gcgcol, /**< gcg column to check */
2505  SCIP_CONS* branchcons, /**< branching constraints from which bound should applied */
2506  SCIP_Bool* feasible /**< check whether the solution is feasible */
2507 ) const
2508 {
2509  int prob = GCGcolGetProbNr(gcgcol);
2510  GCG_BRANCHDATA* branchdata = GCGconsMasterbranchGetBranchdata(branchcons);
2511  GCG_COMPSEQUENCE* components = GCGbranchGenericBranchdataGetConsS(branchdata);
2512  int ncomponents = GCGbranchGenericBranchdataGetConsSsize(branchdata);
2513  int i;
2514 
2515  assert(pricerdata != NULL);
2516 
2517  for( i = 0; i < ncomponents; ++i)
2518  {
2519  SCIP_VAR* pricingvar = GCGoriginalVarGetPricingVar(components[i].component);
2520 
2521  SCIP_Real val = GCGcolGetSolVal(pricerdata->pricingprobs[prob], gcgcol, pricingvar);
2522 
2523  if( components[i].sense == GCG_COMPSENSE_GE )
2524  {
2525  *feasible = SCIPisFeasGE(pricerdata->pricingprobs[prob], val, components[i].bound);
2526 /* SCIPdebugMessage("<%s> %.4f >= %.4f\n", SCIPvarGetName(pricingvar), val, components[i].bound); */
2527  }
2528  else
2529  {
2530  *feasible = SCIPisFeasLT(pricerdata->pricingprobs[prob], val, components[i].bound);
2531 /* SCIPdebugMessage("<%s> %.4f < %.4f\n", SCIPvarGetName(pricingvar), val, components[i].bound); */
2532  }
2533  if( !*feasible )
2534  break;
2535  }
2536 
2537  return SCIP_OKAY;
2538 }
2539 
2540 
2541 /** perform a pricing job, i.e. apply the corresponding solver to the pricing problem
2542  * @note This method has to be threadsafe!
2543  */
2544 SCIP_RETCODE ObjPricerGcg::performPricingjob(
2545  GCG_PRICINGJOB* pricingjob, /**< pricing job */
2546  PricingType* pricetype, /**< type of pricing: reduced cost or Farkas */
2547  GCG_PRICINGSTATUS* status, /**< pointer to store pricing status */
2548  SCIP_Real* lowerbound /**< pointer to store the obtained lower bound */
2549  )
2550 {
2551  GCG_PRICINGPROB* pricingprob;
2552  SCIP* pricingscip;
2553  int probnr;
2554  GCG_SOLVER* solver;
2555  SCIP_Bool heuristic;
2556  SCIP_Bool solved;
2557  SCIP_RETCODE retcode;
2558 
2559  pricingprob = GCGpricingjobGetPricingprob(pricingjob);
2560  assert(pricingprob != NULL);
2561 
2562  probnr = GCGpricingprobGetProbnr(pricingprob);
2563 
2564  pricingscip = GCGpricingprobGetPricingscip(pricingprob);
2565  assert(pricingscip != NULL);
2566 
2567  solver = GCGpricingjobGetSolver(pricingjob);
2568  assert(solver != NULL);
2569 
2570  heuristic = GCGpricingjobIsHeuristic(pricingjob);
2571 
2572  // @todo: this should be done by the pricing solvers
2573  #pragma omp critical (limits)
2574  {
2575  retcode = setPricingProblemMemorylimit(pricingscip);
2576  }
2577  SCIP_CALL( retcode );
2578 
2579  /* add the next generic branching constraint if necessary */
2580  if( !GCGpricingprobBranchconsIsAdded(pricingprob) )
2581  {
2582  SCIP_CONS** branchconss;
2583  int nbranchconss;
2584  int branchconsidx;
2585 
2586  int i;
2587 
2588  GCGpricingprobGetGenericBranchData(pricingprob, &branchconss, NULL, &nbranchconss);
2589  branchconsidx = GCGpricingprobGetBranchconsIdx(pricingprob);
2590  assert(branchconsidx >= 0);
2591  assert(branchconsidx < nbranchconss);
2592 
2593  SCIP_CALL( SCIPfreeTransform(pricingscip) );
2594 
2595  SCIPdebugMessage("*** Apply generic branching bound change of depth %d\n", -branchconsidx);
2596  SCIP_CALL( SCIPtransformProb(pricingscip) );
2597  SCIP_CALL( addBranchingBoundChangesToPricing(probnr, branchconss[branchconsidx]) );
2598 
2599  for( i = 0; i < pricerdata->nsolvers; ++i )
2600  {
2601  SCIP_CALL( GCGsolverUpdate(pricingscip, pricerdata->solvers[i], probnr, FALSE, TRUE, FALSE) );
2602  }
2603 
2604  GCGpricingprobMarkBranchconsAdded(pricingprob);
2605  }
2606 
2607  SCIP_CALL( GCGsolverSolve(scip_, pricingscip, solver, pricetype->getType() == GCG_PRICETYPE_REDCOST,
2608  heuristic, probnr, pricerdata->dualsolconv[probnr], lowerbound, status, &solved) );
2609 
2610  if( !solved )
2611  return SCIP_OKAY;
2612 
2613  if( !heuristic )
2614  {
2615  #pragma omp atomic
2616  pricerdata->solvedsubmipsoptimal++;
2617  }
2618  else
2619  {
2620  #pragma omp atomic
2621  pricerdata->solvedsubmipsheur++;
2622  }
2623 
2624 #ifdef SCIP_STATISTIC
2625  #pragma omp critical (collectstats)
2626  GCGpricerCollectStatistic(pricerdata, pricetype->getType(), probnr,
2627  SCIPgetSolvingTime(pricingscip));
2628 #endif
2629  /* @todo: This should actually be a MIP solver specific statistic */
2630  if( SCIPgetStage(pricingscip) > SCIP_STAGE_SOLVING )
2631  {
2632  #pragma omp atomic
2633  pricerdata->pricingiters += SCIPgetNLPIterations(pricingscip);
2634  }
2635 
2636  return SCIP_OKAY;
2637 }
2638 
2639 
2640 /* Compute difference of two dual solutions */
2642  SCIP_Real** dualvals1, /**< array of dual values for each pricing problem */
2643  SCIP_Real* dualconv1, /**< array of dual solutions for the convexity constraints */
2644  SCIP_Real** dualvals2, /**< array of dual values for each pricing problem */
2645  SCIP_Real* dualconv2, /**< array of dual solutions for the convexity constraints */
2646  SCIP_Real* dualdiff /**< pointer to store difference of duals solutions */
2647  )
2648 {
2649  int i;
2650  int j;
2651  int nprobvars;
2652 
2653  *dualdiff = 0.0;
2654  for( i = 0; i < pricerdata->npricingprobs; i++ )
2655  {
2656  if( pricerdata->pricingprobs[i] == NULL )
2657  continue;
2658 
2659  nprobvars = SCIPgetNVars(pricerdata->pricingprobs[i]);
2660 
2661  for( j = 0; j < nprobvars; j++ )
2662  {
2663  *dualdiff += SQR(dualvals1[i][j] - dualvals2[i][j]);
2664  }
2665 
2666  *dualdiff += SQR(dualconv1[i] - dualconv2[i]);
2667 
2668  }
2669  *dualdiff = SQRT(ABS(*dualdiff));
2670 
2671  return SCIP_OKAY;
2672 }
2673 
2674 /** the pricing loop: solve the pricing problems */
2676  PricingType* pricetype, /**< type of pricing */
2677  SCIP_RESULT* result, /**< result pointer */
2678  int* pnfoundvars, /**< pointer to store number of found variables */
2679  SCIP_Real* lowerbound, /**< pointer to store lowerbound obtained due to lagrange bound */
2680  SCIP_Bool* bestredcostvalid /**< pointer to store if bestredcost are valid (pp solvedoptimal) */
2681  )
2682 {
2683  GCG_PRICINGJOB* pricingjob = NULL;
2684  GCG_COL** bestcols;
2685  SCIP_LPI* lpi;
2686  SCIP_Real* bestobjvals = NULL;
2687  SCIP_Real bestredcost;
2688  SCIP_Real beststabobj;
2689  SCIP_RETCODE retcode;
2690  SCIP_Bool infeasible;
2691  SCIP_Bool nextchunk;
2692  SCIP_Bool stabilized;
2693  SCIP_Bool colpoolupdated;
2694  SCIP_Bool enableppcuts;
2695  SCIP_Bool enablestab;
2696  int nsuccessfulprobs;
2697  int maxniters;
2698  int niters;
2699  int i;
2700  int j;
2701  int nfoundvars;
2702  SCIP_Bool optimal;
2703  bool probingnode;
2704 
2705 #ifdef SCIP_STATISTIC
2706  SCIP_Real** olddualvalues;
2707  SCIP_Real* olddualconv;
2708 
2709  int nprobvars;
2710  int nstabrounds;
2711  SCIP_Real pricingtime;
2712 #endif
2713 
2714  assert(pricerdata != NULL);
2715  assert(stabilization != NULL);
2716  assert(farkaspricing != NULL);
2717  assert(reducedcostpricing != NULL);
2718 
2719  assert(result != NULL);
2720  assert(pnfoundvars != NULL);
2721 
2722  /* initializations */
2723  retcode = SCIP_OKAY;
2724  *pnfoundvars = 0;
2725  nfoundvars = 0;
2726  infeasible = FALSE;
2727  stabilized = FALSE;
2728  optimal = FALSE;
2729  if( lowerbound != NULL )
2730  *lowerbound = -SCIPinfinity(scip_);
2731 
2732  maxniters = pricingcontroller->getMaxNIters();
2733 
2734  // disable colpool while probing mode is active (can be removed after a feasibility check (#586) is implemented)
2735  probingnode = (SCIPnodeGetType(SCIPgetCurrentNode(scip_)) == SCIP_NODETYPE_PROBINGNODE);
2736 
2737  SCIP_CALL( SCIPgetLPI(scip_, &lpi) );
2738 
2739  /* check preliminary conditions for stabilization */
2740  enablestab = pricerdata->stabilization
2741  && (SCIPgetCurrentNode(scip_) == SCIPgetRootNode(scip_) || pricerdata->stabilizationtree)
2742  && (pricerdata->stabilization && pricetype->getType() == GCG_PRICETYPE_REDCOST)
2744 
2745  /* allocate memory */
2746  SCIP_CALL( SCIPallocBlockMemoryArray(scip_, &bestcols, pricerdata->npricingprobs) );
2747  SCIP_CALL( SCIPallocBlockMemoryArray(scip_, &bestobjvals, pricerdata->npricingprobs) );
2748 
2749  enableppcuts = FALSE;
2750  SCIP_CALL( SCIPgetBoolParam(GCGmasterGetOrigprob(scip_), "sepa/basis/enableppcuts", &enableppcuts) );
2751  /* set parameters for adding pool cuts to separation basis */
2752  if( enableppcuts && SCIPgetCurrentNode(scip_) != SCIPgetRootNode(scip_) )
2753  {
2754  for( i = 0; i < pricerdata->npricingprobs; i++ )
2755  {
2756  if( GCGisPricingprobRelevant(origprob, i) )
2757  {
2758  SCIP_CALL( SCIPsetIntParam(pricerdata->pricingprobs[i], "branching/pscost/priority", 2000) );
2759  SCIP_CALL( SCIPsetIntParam(pricerdata->pricingprobs[i], "propagating/maxroundsroot", 1000) );
2760  SCIP_CALL( SCIPsetPresolving(pricerdata->pricingprobs[i], SCIP_PARAMSETTING_DEFAULT, TRUE) );
2761  }
2762  }
2763  }
2764 
2765 #ifdef _OPENMP
2766  if( threads > 0 )
2767  omp_set_num_threads(MIN(threads, GCGgetNRelPricingprobs(origprob)));
2768  else
2769  omp_set_num_threads(GCGgetNRelPricingprobs(origprob));
2770 #endif
2771 
2772  /* todo: We avoid checking for feasibility of the columns using this hack */
2773  if( pricerdata->usecolpool && !probingnode )
2774  SCIP_CALL( GCGcolpoolUpdateNode(colpool) );
2775 
2776  colpoolupdated = FALSE;
2777 
2778 #ifdef SCIP_STATISTIC
2779  if( pricerdata->nroundsredcost > 0 && pricetype->getType() == GCG_PRICETYPE_REDCOST )
2780  {
2781  SCIP_CALL( SCIPallocBufferArray(scip_, &olddualvalues, pricerdata->npricingprobs) );
2782  SCIP_CALL( SCIPallocBufferArray(scip_, &olddualconv, pricerdata->npricingprobs) );
2783 
2784  for( i = 0; i < pricerdata->npricingprobs; i++ )
2785  {
2786  if( pricerdata->pricingprobs[i] == NULL )
2787  continue;
2788 
2789  nprobvars = SCIPgetNVars(pricerdata->pricingprobs[i]);
2790 
2791  olddualconv[i] = pricerdata->dualsolconv[i];
2792  SCIP_CALL( SCIPallocBufferArray(scip_, &(olddualvalues[i]), nprobvars) );
2793 
2794  for( j = 0; j < nprobvars; j++ )
2795  olddualvalues[i][j] = pricerdata->realdualvalues[i][j];
2796  }
2797  }
2798 #endif
2799 
2800 #ifdef SCIP_STATISTIC
2801  SCIPstatisticMessage("New pr, node %" SCIP_LONGINT_FORMAT "\n", SCIPgetNNodes(scip_));
2802  SCIPstatisticMessage("MLP t: %g\n", SCIPgetClockTime(scip_, scip_->stat->primallptime) + SCIPgetClockTime(scip_, scip_->stat->duallptime));
2803  nstabrounds = 0;
2804 #endif
2805 
2806  SCIPdebugMessage("***** New pricing round at node %" SCIP_LONGINT_FORMAT " (depth = %d), maxniters = %d\n",
2807  SCIPgetNNodes(scip_), SCIPnodeGetDepth(SCIPgetCurrentNode(scip_)), maxniters);
2808 
2809  /* stabilization loop */
2810  do
2811  {
2812  optimal = FALSE;
2813 #ifndef NDEBUG
2814  if( nextchunk )
2815  {
2816  SCIPdebugMessage("*** get next chunk of pricing problems\n");
2817  }
2818 #endif
2819 
2820  nsuccessfulprobs = 0;
2821  *bestredcostvalid = isMasterLPOptimal() && !GCGisBranchruleGeneric(GCGconsMasterbranchGetBranchrule(GCGconsMasterbranchGetActiveCons(scip_)));
2822  nextchunk = FALSE;
2823 
2824  if( stabilized )
2825  {
2826  SCIPdebugMessage("****************************** Mispricing iteration ******************************\n");
2827 #ifdef SCIP_STATISTIC
2828  ++nstabrounds;
2829  SCIPstatisticMessage("Sr %d\n", nstabrounds);
2830 #endif
2831  }
2832 
2833  /* initialize stabilization parameters if we are at a new node */
2834  if( enablestab )
2835  {
2836  stabilization->updateNode();
2837  SCIP_CALL( stabilization->updateHybrid() );
2838  }
2839 
2840  stabilized = enablestab && stabilization->isStabilized();
2841 
2842  /* set the objective function */
2843  SCIP_CALL( freePricingProblems() );
2844  SCIP_CALL( setPricingObjs(pricetype, stabilized) );
2845 
2846  /* call update method of pricing solvers to update objectives;
2847  * also, let them update their bounds since the transformed pricing problems
2848  * might have contained generic branching bounds before freeing
2849  */
2850  for( i = 0; i < pricerdata->nsolvers; ++i )
2851  {
2852  for( j = 0; j < pricerdata->npricingprobs; ++j )
2853  {
2854  if( pricerdata->pricingprobs[j] != NULL )
2855  {
2856  SCIP_CALL( GCGsolverUpdate(pricerdata->pricingprobs[j], pricerdata->solvers[i], j, TRUE, TRUE, FALSE) );
2857  }
2858  }
2859  }
2860 
2861  /* todo: do this inside the updateRedcostColumnPool */
2862  if( !colpoolupdated && pricerdata->usecolpool && !probingnode )
2863  {
2864  /* update reduced cost of cols in colpool */
2865  SCIP_CALL( GCGcolpoolUpdateRedcost(colpool) );
2866 
2867  colpoolupdated = TRUE;
2868  }
2869 
2870  /* check if colpool already contains columns with negative reduced cost */
2871  if( pricerdata->usecolpool && !probingnode )
2872  {
2873  SCIP_Bool foundvarscolpool;
2874  int oldnfoundcols;
2875 
2876  foundvarscolpool = FALSE;
2877  oldnfoundcols = GCGpricestoreGetNCols(pricestore);
2878 
2879  SCIP_CALL( GCGcolpoolPrice(scip_, colpool, pricestore, NULL, &foundvarscolpool) );
2880  SCIPstatisticMessage("cp: %d impr c\n", GCGpricestoreGetNCols(pricestore) - oldnfoundcols);
2881 
2882  if( foundvarscolpool )
2883  {
2884  SCIPdebugMessage("*** Found column(s) with negative reduced cost in column pool\n");
2885  assert(GCGpricestoreGetNCols(pricestore) > 0);
2886  break;
2887  }
2888  }
2889 
2890  pricingcontroller->setupPriorityQueue(pricerdata->dualsolconv);
2891 
2892  /* actual pricing loop: perform the pricing jobs until none are left or an abortion criterion is met */
2893  #pragma omp parallel for ordered firstprivate(pricingjob) shared(retcode, pricetype, nfoundvars, nsuccessfulprobs) schedule(static,1)
2894  for( niters = 0; niters < maxniters; ++niters )
2895  {
2896  GCG_PRICINGPROB* pricingprob;
2897  GCG_PRICINGSTATUS status;
2898  SCIP_Real problowerbound;
2899  SCIP_RETCODE private_retcode;
2900 
2901  int oldnimpcols = GCGpricestoreGetNEfficaciousCols(pricestore);
2902 
2903  #pragma omp flush(retcode)
2904  if( retcode != SCIP_OKAY )
2905  continue;
2906 
2907  /* retrieve the next pricing job from the queue */
2908  #pragma omp critical (update)
2909  {
2910  pricingjob = pricingcontroller->getNextPricingjob();
2911  }
2912  if( pricingjob == NULL )
2913  continue;
2914 
2915  #pragma omp flush(nfoundvars, nsuccessfulprobs)
2916  if( (pricingcontroller->canPricingloopBeAborted(pricetype, nfoundvars, nsuccessfulprobs) || infeasible) && !stabilized )
2917  {
2918  SCIPdebugMessage("*** Abort pricing loop, infeasible = %u, stabilized = %u\n", infeasible, stabilized);
2919  continue;
2920  }
2921 
2922  /* initializations */
2923  pricingprob = GCGpricingjobGetPricingprob(pricingjob);
2924  status = GCG_PRICINGSTATUS_UNKNOWN;
2925  problowerbound = -SCIPinfinity(scip_);
2926 
2927  SCIPdebugMessage("*** Solve pricing problem %d, solver <%s>, stabilized = %u, %s\n",
2928  GCGpricingprobGetProbnr(pricingprob), GCGsolverGetName(GCGpricingjobGetSolver(pricingjob)), stabilized,
2929  GCGpricingjobIsHeuristic(pricingjob) ? "heuristic" : "exact");
2930 
2931  /* @todo: this should be done by the pricing solvers */
2932  #pragma omp critical (limits)
2933  SCIP_CALL_ABORT( pricingcontroller->setPricingjobTimelimit(pricingjob) );
2934 
2935 #ifdef SCIP_STATISTIC
2936  /* @todo: this can interfere with parallelization */
2937  pricingtime = pricetype->getClockTime();
2938 #endif
2939 
2940  /* solve the pricing problem */
2941  private_retcode = performPricingjob(pricingjob, pricetype, &status, &problowerbound);
2942 
2943 #ifdef SCIP_STATISTIC
2944  pricingtime = pricetype->getClockTime() - pricingtime;
2945 #endif
2946 
2947  SCIPdebugMessage(" -> status: %d\n", status);
2948  SCIPdebugMessage(" -> problowerbound: %.4g\n", problowerbound);
2949 
2950  /* update pricing problem results, store columns */
2951  #pragma omp critical (update)
2952  {
2953  pricingcontroller->updatePricingprob(pricingprob, status, problowerbound, GCGpricestoreGetNEfficaciousCols(pricestore) - oldnimpcols);
2954  }
2955 
2956  /* update solving statistics, needed for checking the abortion criterion */
2957  #pragma omp ordered
2958  {
2959  #pragma omp critical (retcode)
2960  retcode = private_retcode; // @todo: handle return code correctly
2961 
2962  #pragma omp atomic
2963  nfoundvars += GCGpricestoreGetNEfficaciousCols(pricestore) - oldnimpcols;
2964 
2965  if( oldnimpcols == 0 && GCGpricingprobGetNImpCols(pricingprob) > 0 )
2966  {
2967  #pragma omp atomic
2968  ++nsuccessfulprobs;
2969  }
2970 
2971 #ifdef SCIP_STATISTIC
2972  if( status != GCG_PRICINGSTATUS_NOTAPPLICABLE )
2973  {
2974  SCIPstatisticMessage("P p %d : %d in %g\n",
2975  GCGpricingprobGetProbnr(pricingprob), GCGpricestoreGetNEfficaciousCols(pricestore) - oldnimpcols, pricingtime);
2976  }
2977 #endif
2978  }
2979 
2980  #pragma omp critical (update)
2981  {
2982  pricingcontroller->evaluatePricingjob(pricingjob, status);
2983  }
2984  }
2985 
2986  SCIP_CALL( retcode );
2987 
2988  /* collect results from all performed pricing jobs */
2989  getBestCols(bestcols);
2990  pricingcontroller->collectResults(bestcols, &infeasible, &optimal, bestobjvals, &beststabobj, &bestredcost, bestredcostvalid);
2991 
2992  if( infeasible )
2993  break;
2994 
2995  SCIPdebugMessage("optimal = %u, bestredcostvalid = %u, stabilized = %u\n", optimal, *bestredcostvalid, stabilized);
2996 
2997  /* update stabilization information and lower bound */
2998  if( pricetype->getType() == GCG_PRICETYPE_REDCOST )
2999  {
3000  SCIP_Real lowerboundcandidate;
3001  SCIP_Real stabdualval = 0.0;
3002 
3003  assert(lowerbound != NULL);
3004 
3005  SCIP_CALL( getStabilizedDualObjectiveValue(pricetype, &stabdualval, stabilized) );
3006 
3007  lowerboundcandidate = stabdualval + beststabobj;
3008 
3009  SCIPdebugMessage("lpobjval = %.8g, bestredcost = %.8g, stabdualval = %.8g, beststabobj = %.8g\n",
3010  SCIPgetLPObjval(scip_), bestredcost, stabdualval, beststabobj);
3011  SCIPdebugMessage("lowerboundcandidate = %.8g\n", lowerboundcandidate);
3012 
3013  assert(!optimal || !*bestredcostvalid || stabilized || SCIPisDualfeasEQ(scip_, SCIPgetLPObjval(scip_) + bestredcost, lowerboundcandidate));
3014 
3015  if( enablestab )
3016  {
3017  SCIP_Real beststabredcost = beststabobj - getDualconvsum(bestcols);
3018 
3019  SCIPdebugMessage("beststabredcost = %.8g\n", beststabredcost);
3020 
3021  /* If all pricing problems have been solved to optimality, update subgradient product and stability center */
3022  if( optimal )
3023  {
3024  SCIPdebugMessage("update subgradient product and stability center\n");
3025 
3026  /* update subgradient product before a potential change of the stability center */
3027  SCIP_CALL( stabilization->updateSubgradientProduct(bestcols) );
3028  SCIP_CALL( stabilization->updateStabilityCenter(lowerboundcandidate, bestobjvals, bestcols) );
3029  }
3030 
3031  /* activate or deactivate mispricing schedule, depending on whether improving columns have been found */
3032  if( nfoundvars == 0 )
3033  {
3034  if( stabilized )
3035  {
3036  SCIPdebugMessage("enabling mispricing schedule\n");
3037  stabilization->activateMispricingSchedule();
3038  stabilization->updateAlphaMisprice();
3039  }
3040  else
3041  stabilization->disablingMispricingSchedule();
3042  }
3043  else if( *bestredcostvalid && SCIPisDualfeasNegative(scip_, beststabredcost) )
3044  {
3045  if( stabilization->isInMispricingSchedule() )
3046  stabilization->disablingMispricingSchedule();
3047  stabilization->updateAlpha();
3048  }
3049  }
3050 
3051  if( *bestredcostvalid )
3052  {
3053  SCIP_Bool enableppobjcg;
3054 
3055  *lowerbound = MAX(*lowerbound, lowerboundcandidate);
3056 
3057  /* add cuts based on the latest pricing problem objective to the original problem */
3058  SCIP_CALL( SCIPgetBoolParam(GCGmasterGetOrigprob(scip_), "sepa/basis/enableppobjcg", &enableppobjcg) );
3059  if( enableppobjcg && SCIPgetCurrentNode(scip_) == SCIPgetRootNode(scip_) )
3060  {
3061  for( i = 0; i < pricerdata->npricingprobs; ++i )
3062  {
3064  continue;
3065 
3066  SCIP_CALL( SCIPsepaBasisAddPPObjConss(scip_, i, bestobjvals[i], TRUE) );
3067  }
3068  }
3069  }
3070  }
3071 
3072  /* if no column has negative reduced cost, consider the next chunk of pricing problems */
3073  if( nfoundvars == 0 && !stabilized )
3074  nextchunk = pricingcontroller->checkNextChunk();
3075 
3076  /** @todo perhaps solve remaining pricing problems, if only few left? */
3077  /** @todo solve all pricing problems all k iterations? */
3078  }
3079  while( nextchunk || (stabilized && nfoundvars == 0) );
3080 
3081  SCIPdebugMessage("*** Pricing loop finished, found %d improving columns.\n", nfoundvars);
3082 
3083  /* Add new columns as variables to the master problem or move them to the column pool */
3084  SCIP_CALL( GCGpricestoreApplyCols(pricestore, colpool, (pricerdata->usecolpool && !probingnode), &nfoundvars) );
3085 
3086  SCIPdebugMessage("Added %d new variables.\n", nfoundvars);
3087 
3088  SCIPfreeBlockMemoryArray(scip_, &bestobjvals, pricerdata->npricingprobs);
3089  SCIPfreeBlockMemoryArray(scip_, &bestcols, pricerdata->npricingprobs);
3090 
3091  enableppcuts = FALSE;
3092  SCIP_CALL( SCIPgetBoolParam(GCGmasterGetOrigprob(scip_), "sepa/basis/enableppcuts", &enableppcuts) );
3093 
3094  /* add pool cuts to sepa basis */
3095  if( enableppcuts && SCIPgetCurrentNode(scip_) == SCIPgetRootNode(scip_) )
3096  {
3097  for( j = 0; j < pricerdata->npricingprobs; j++ )
3098  {
3099  if( pricerdata->pricingprobs[j] != NULL
3100  && SCIPgetStage(pricerdata->pricingprobs[j]) >= SCIP_STAGE_SOLVING )
3101  {
3102  SCIP_CUT** cuts;
3103  int ncuts;
3104 
3105  ncuts = SCIPgetNPoolCuts(pricerdata->pricingprobs[j]);
3106  cuts = SCIPgetPoolCuts(pricerdata->pricingprobs[j]);
3107 
3108  for( i = 0; i < ncuts; ++i )
3109  {
3110  SCIP_ROW* row;
3111  row = SCIPcutGetRow(cuts[i]);
3112 
3113  if( !SCIProwIsLocal(row) && SCIProwGetRank(row) >= 1 && nfoundvars == 0 )
3114  SCIP_CALL( GCGsepaBasisAddPricingCut(scip_, j, row) );
3115  }
3116  }
3117  }
3118  }
3119 
3120 #ifdef SCIP_STATISTIC
3121  SCIPstatisticMessage("MLP t: %g\n", SCIPgetClockTime(scip_, scip_->stat->primallptime) + SCIPgetClockTime(scip_, scip_->stat->duallptime));
3122 #endif
3123 
3124  /* free the pricingproblems if they exist and need to be freed */
3125  // @todo: actually, only the transformed problems are freed
3126  SCIP_CALL( freePricingProblems() );
3127  *pnfoundvars = nfoundvars;
3128 
3129  if( infeasible )
3130  *result = SCIP_SUCCESS;
3131  else if( *pnfoundvars > 0 || optimal )
3132  *result = SCIP_SUCCESS;
3133  else
3134  *result = SCIP_DIDNOTRUN;
3135 
3136 #ifdef SCIP_STATISTIC
3137  if( pricerdata->nroundsredcost > 0 && pricetype->getType() == GCG_PRICETYPE_REDCOST )
3138  {
3139  if( pricerdata->nrootbounds != pricerdata->dualdiffround )
3140  {
3141  SCIP_Real dualdiff;
3142  SCIP_CALL( computeDualDiff(olddualvalues, olddualconv, pricerdata->realdualvalues, pricerdata->dualsolconv, &dualdiff) );
3143  pricerdata->dualdiffround = pricerdata->nrootbounds;
3144  pricerdata->dualdiff = dualdiff;
3145  }
3146 
3147  for( i = pricerdata->npricingprobs - 1; i >= 0; i-- )
3148  {
3149  if( pricerdata->pricingprobs[i] == NULL )
3150  continue;
3151  SCIPfreeBufferArray(scip_, &(olddualvalues[i]));
3152  }
3153  SCIPfreeBufferArray(scip_, &olddualconv);
3154  SCIPfreeBufferArray(scip_, &olddualvalues);
3155 
3156  }
3157  else if( pricerdata->nrootbounds != pricerdata->dualdiffround )
3158  {
3159  pricerdata->dualdiff = 0.0;
3160  }
3161 #endif
3162 
3163  return SCIP_OKAY;
3164 }
3165 
3166 /** set pricing objectives */
3167 extern "C"
3168 SCIP_RETCODE GCGsetPricingObjs(
3169  SCIP* scip, /**< SCIP data structure */
3170  SCIP_Real* dualsolconv /**< array of dual solutions corresponding to convexity constraints */
3171 )
3172 {
3173  ObjPricerGcg* pricer;
3174  SCIP_Bool stabilizationtmp;
3175  int i;
3176  int j;
3177 
3178  assert(scip != NULL);
3179 
3180  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
3181  assert(pricer != NULL);
3182 
3183  stabilizationtmp = pricer->pricerdata->stabilization;
3184 
3185  pricer->pricerdata->stabilization = FALSE;
3186 
3187  SCIP_CALL( pricer->setPricingObjs(pricer->getReducedCostPricingNonConst(), FALSE) );
3188 
3189  /* notify the pricing solvers that the objective values have changed */
3190  for( i = 0; i < pricer->pricerdata->nsolvers; ++i )
3191  {
3192  for( j = 0; j < pricer->pricerdata->npricingprobs; ++j )
3193  {
3194  if( pricer->pricerdata->pricingprobs[j] != NULL )
3195  {
3196  SCIP_CALL( GCGsolverUpdate(pricer->pricerdata->pricingprobs[j], pricer->pricerdata->solvers[i], j, TRUE, FALSE, FALSE) );
3197  }
3198  }
3199  }
3200 
3201  if(dualsolconv != NULL)
3202  {
3203  for(i = 0; i < pricer->pricerdata->npricingprobs; ++i)
3204  {
3205  dualsolconv[i] = pricer->pricerdata->dualsolconv[i];
3206  }
3207  }
3208  pricer->pricerdata->stabilization = stabilizationtmp;
3209 
3210  return SCIP_OKAY;
3211 }
3212 
3213 /** creates a new master variable corresponding to the given gcg column */
3214 extern "C"
3216  SCIP* scip, /**< SCIP data structure */
3217  SCIP_Bool infarkas, /**< in Farkas pricing? */
3218  GCG_COL* gcgcol, /**< GCG column data structure */
3219  SCIP_Bool force, /**< should the given variable be added also if it has non-negative reduced cost? */
3220  SCIP_Bool* added, /**< pointer to store whether the variable was successfully added */
3221  SCIP_VAR** addedvar, /**< pointer to store the created variable */
3222  SCIP_Real score /**< score of column (or -1.0 if not specified) */
3223 )
3224 {
3225  ObjPricerGcg* pricer;
3226  PricingType* pricetype;
3227 
3228  assert(scip != NULL);
3229 
3230  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
3231  assert(pricer != NULL);
3232 
3233  if( infarkas )
3234  pricetype = pricer->getFarkasPricingNonConst();
3235  else
3236  pricetype = pricer->getReducedCostPricingNonConst();
3237 
3238 
3239  SCIP_CALL( pricer->createNewMasterVarFromGcgCol(scip, pricetype, gcgcol, force, added, addedvar, score) );
3240 
3241  return SCIP_OKAY;
3242 }
3243 
3244 /** compute master and cut coefficients of column */
3245 extern "C"
3247  SCIP* scip, /**< SCIP data structure */
3248  GCG_COL* gcgcol /**< GCG column data structure */
3249  )
3250 {
3251  ObjPricerGcg* pricer;
3252 
3253  assert(scip != NULL);
3254 
3255  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
3256  assert(pricer != NULL);
3257 
3258  pricer->computeColMastercoefs(gcgcol);
3259  pricer->computeColMastercuts(gcgcol);
3260 
3261  return SCIP_OKAY;
3262 
3263 }
3264 /** computes the reduced cost of a column */
3265 extern "C"
3267  SCIP* scip, /**< SCIP data structure */
3268  SCIP_Bool infarkas, /**< in Farkas pricing? */
3269  GCG_COL* gcgcol, /**< gcg column to compute reduced cost for */
3270  SCIP_Real* objvalptr /**< pointer to store the computed objective value */
3271  )
3272 {
3273  ObjPricerGcg* pricer;
3274  PricingType* pricetype;
3275  SCIP_Real redcost;
3276 
3277  assert(scip != NULL);
3278 
3279  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
3280  assert(pricer != NULL);
3281 
3282  if( infarkas )
3283  pricetype = pricer->getFarkasPricingNonConst();
3284  else
3285  pricetype = pricer->getReducedCostPricingNonConst();
3286 
3287  redcost = pricer->computeRedCostGcgCol(pricetype, gcgcol, objvalptr);
3288 
3289  return redcost;
3290 }
3291 
3292 /** performs the pricing routine, gets the type of pricing that should be done: farkas or redcost pricing */
3294  PricingType* pricetype, /**< type of the pricing */
3295  SCIP_RESULT* result, /**< result pointer */
3296  SCIP_Real* lowerbound /**< lowerbound pointer */
3297  )
3298 {
3299  int nfoundvars;
3300  SCIP_Bool bestredcostvalid;
3301 
3302  assert(result != NULL);
3303  assert(lowerbound != NULL || pricetype->getType() == GCG_PRICETYPE_FARKAS);
3304  assert(pricerdata != NULL);
3305 
3306  if( lowerbound != NULL )
3307  *lowerbound = -SCIPinfinity(scip_);
3308 
3309  GCGpricerPrintInfo(scip_, pricerdata, "nvars = %d, current LP objval = %g, time = %f, node = %lld\n",
3310  SCIPgetNVars(scip_), SCIPgetLPObjval(scip_), SCIPgetSolvingTime(scip_), SCIPgetNNodes(scip_));
3311 
3312  if( pricetype->getType() == GCG_PRICETYPE_REDCOST )
3313  {
3314  assert(result != NULL);
3315 
3316  /* terminate early, if applicable */
3317  if( canPricingBeAborted() )
3318  {
3319  *result = SCIP_DIDNOTRUN;
3320  return SCIP_OKAY;
3321  }
3322  }
3323 
3324  *result = SCIP_SUCCESS;
3325 
3326  pricingtype = pricetype;
3327  pricetype->incCalls();
3328 
3329  pricerdata->calls++;
3330  nfoundvars = 0;
3331 
3332  bestredcostvalid = TRUE;
3333 
3334  /* If pricing is performed for the first time at this node, update variable bounds and pricing constraints */
3335  if( pricerdata->newnode )
3336  {
3337  int i;
3338  int j;
3339 
3340  for( i = 0; i < pricerdata->nsolvers; ++i )
3341  {
3342  for( j = 0; j < pricerdata->npricingprobs; ++j )
3343  {
3344  if( pricerdata->pricingprobs[j] != NULL )
3345  {
3346  SCIP_CALL( GCGsolverUpdate(pricerdata->pricingprobs[j], pricerdata->solvers[i], j, FALSE, TRUE, TRUE) );
3347  }
3348  }
3349  }
3350  }
3351 
3352  pricingcontroller->initPricing(pricetype);
3353 
3354  SCIP_CALL( pricingLoop(pricetype, result, &nfoundvars, lowerbound, &bestredcostvalid) );
3355 
3356  if( pricetype->getType() == GCG_PRICETYPE_REDCOST && bestredcostvalid )
3357  {
3358  assert(lowerbound != NULL);
3359  GCGpricerPrintInfo(scip_, pricerdata, "lower bound = %g\n", *lowerbound);
3360 
3361  pricingcontroller->resetEagerage();
3362  }
3363 
3364 
3365  SCIPdebugMessage("%s pricing: found %d new vars\n", (pricetype->getType() == GCG_PRICETYPE_REDCOST ? "Redcost" : "Farkas"), nfoundvars);
3366 
3367  if( GCGisRootNode(scip_) && pricetype->getType() == GCG_PRICETYPE_REDCOST && pricetype->getCalls() > 0 )
3368  {
3369  double degeneracy = 0.0;
3370 
3371  /* only compute degeneracy if current solution is basic */
3372  if( SCIPisLPSolBasic(scip_) )
3373  SCIP_CALL( computeCurrentDegeneracy(&degeneracy) );
3374 
3375  pricerdata->rootnodedegeneracy = degeneracy;
3376 
3377  /* Complicated calculation for numerical stability:
3378  * E[\sum_{i=1}^n x_i] = (E[\sum_{i=1}^{n-1} x_i]*(n-1) + x_n)/n
3379  * E[\sum_{i=1}^n x_i] = E[\sum_{i=1}^{n-1} x_i]*(n-1)/n + x_n/n
3380  * <=> E[\sum_{i=1}^n x_i] = E[\sum_{i=1}^{n-1} x_i]-E[\sum_{i=1}^{n-1} x_i]/n + x_n/n
3381  * <=> E_n = E_{n-1} - E_{n-1}/n + x_n/n
3382  * <=> E -= E/n - x_n/n
3383  */
3384  ++pricerdata->ndegeneracycalcs;
3385  pricerdata->avgrootnodedegeneracy -= (pricerdata->avgrootnodedegeneracy/(pricerdata->ndegeneracycalcs) - degeneracy/(pricerdata->ndegeneracycalcs));
3386  }
3387 
3388  pricingcontroller->exitPricing();
3389 
3390  pricingtype = NULL;
3391 
3392  return SCIP_OKAY;
3393 }
3394 
3395 /*
3396  * Callback methods of variable pricer
3397  */
3398 
3400  SCIP* scip, /**< SCIP data structure */
3401  SCIP* origscip, /**< SCIP data structure of original problem */
3402  const char* name, /**< name of variable pricer */
3403  const char* desc, /**< description of variable pricer */
3404  int priority, /**< priority of the variable pricer */
3405  SCIP_Bool delay,
3406  SCIP_PRICERDATA* p_pricerdata
3407  ) : ObjPricer(scip, name, desc, priority, delay), colpool(NULL), pricestore(NULL), reducedcostpricing(NULL), farkaspricing(NULL), pricingcontroller(NULL), stabilization(NULL)
3408  {
3409 
3410  assert(origscip!= NULL);
3411  pricerdata = p_pricerdata;
3412  origprob = origscip;
3413  }
3414 
3415 /** destructor of variable pricer to free user data (called when SCIP is exiting) */
3416 SCIP_DECL_PRICERFREE(ObjPricerGcg::scip_free)
3417 {
3418  assert(scip == scip_);
3419  SCIP_CALL( solversFree() );
3420 
3421  SCIPfreeMemoryArray(scip, &pricerdata->solvers);
3422 
3423  /* free memory for pricerdata*/
3424  if( pricerdata != NULL )
3425  {
3426  SCIPfreeMemory(scip, &pricerdata);
3427  }
3428 
3429  delete pricingcontroller;
3430 
3431  if( reducedcostpricing != NULL )
3432  delete reducedcostpricing;
3433 
3434  if( farkaspricing != NULL )
3435  delete farkaspricing;
3436 
3437  SCIPpricerSetData(pricer, NULL);
3438  return SCIP_OKAY;
3439 }
3440 
3441 
3442 /** initialization method of variable pricer (called after problem was transformed) */
3443 SCIP_DECL_PRICERINIT(ObjPricerGcg::scip_init)
3444 { /*lint --e{715}*/
3445  assert(scip == scip_);
3446  assert(reducedcostpricing != NULL);
3447  assert(farkaspricing != NULL);
3448 
3449  SCIP_CALL( solversInit() );
3450 
3451  SCIP_CALL( reducedcostpricing->resetCalls() );
3452  SCIP_CALL( farkaspricing->resetCalls() );
3453 
3454  return SCIP_OKAY;
3455 }
3456 
3457 
3458 /** deinitialization method of variable pricer (called before transformed problem is freed) */
3459 SCIP_DECL_PRICEREXIT(ObjPricerGcg::scip_exit)
3460 { /*lint --e{715}*/
3461  assert(scip == scip_);
3462  SCIP_CALL( solversExit() );
3463 
3464  return SCIP_OKAY;
3465 }
3466 
3467 
3468 /** solving process initialization method of variable pricer (called when branch and bound process is about to begin) */
3469 SCIP_DECL_PRICERINITSOL(ObjPricerGcg::scip_initsol)
3470 {
3471  int i;
3472  int norigvars;
3473  SCIP_Bool discretization;
3474  SCIP_CONS** masterconss;
3475  int nmasterconss;
3476  int origverblevel;
3477  int size;
3478 
3479  assert(scip == scip_);
3480  assert(pricer != NULL);
3481  assert(pricerdata != NULL);
3482 
3483  /* at the beginning, the output of the master problem gets the same verbosity level
3484  * as the output of the original problem */
3485  SCIP_CALL( SCIPgetIntParam(origprob, "display/verblevel", &origverblevel) );
3486  SCIP_CALL( SCIPsetIntParam(scip, "display/verblevel", origverblevel) );
3487 
3488  pricerdata->currnodenr = -1;
3489  pricerdata->newnode = TRUE;
3490  pricerdata->artificialused = FALSE;
3491 
3492  nmasterconss = GCGgetNMasterConss(origprob);
3493  masterconss = GCGgetMasterConss(origprob);
3494 
3495  pricerdata->artificialvars = NULL;
3496  pricerdata->nartificialvars = 0;
3497  pricerdata->maxartificialvars = 0;
3498 
3499  /* init array containing all pricing problems */
3500  pricerdata->npricingprobs = GCGgetNPricingprobs(origprob);
3501  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->pricingprobs), pricerdata->npricingprobs) );
3502  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->npointsprob), pricerdata->npricingprobs) );
3503  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->nraysprob), pricerdata->npricingprobs) );
3504 
3505  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->farkascallsdist), pricerdata->npricingprobs) );
3506  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->farkasfoundvars), pricerdata->npricingprobs) );
3507  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->farkasnodetimedist), pricerdata->npricingprobs) );
3508 
3509  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->redcostcallsdist), pricerdata->npricingprobs) );
3510  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->redcostfoundvars), pricerdata->npricingprobs) );
3511  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->redcostnodetimedist), pricerdata->npricingprobs) );
3512 
3513  size = SCIPcalcMemGrowSize(scip, pricerdata->npricingprobs);
3514  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->realdualvalues), size) );
3515  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->maxrealdualvalues), size) );
3516  pricerdata->maxrealdualvaluescapacity = size;
3517 
3518  pricerdata->oldvars = 0;
3519 
3520  pricerdata->npricingprobsnotnull = 0;
3521 
3522  for( i = 0; i < pricerdata->npricingprobs; i++ )
3523  {
3524 
3525  pricerdata->farkascallsdist[i] = 0;
3526  pricerdata->farkasfoundvars[i] = 0;
3527  pricerdata->farkasnodetimedist[i] = 0;
3528  pricerdata->redcostcallsdist[i] = 0;
3529  pricerdata->redcostfoundvars[i] = 0;
3530  pricerdata->redcostnodetimedist[i]= 0;
3531 
3532 
3533  if( GCGisPricingprobRelevant(origprob, i) )
3534  {
3535  pricerdata->pricingprobs[i] = GCGgetPricingprob(origprob, i);
3536  pricerdata->npricingprobsnotnull++;
3537  pricerdata->maxrealdualvalues[i] = SCIPcalcMemGrowSize(scip, SCIPgetNVars(pricerdata->pricingprobs[i]));
3538  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->realdualvalues[i]), pricerdata->maxrealdualvalues[i]) ); /*lint !e666 !e866*/
3539  }
3540  else
3541  {
3542  pricerdata->realdualvalues[i] = NULL;
3543  pricerdata->pricingprobs[i] = NULL;
3544  }
3545  pricerdata->npointsprob[i] = 0;
3546  pricerdata->nraysprob[i] = 0;
3547  }
3548 
3549  /* alloc memory for arrays of reduced cost */
3550  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->dualsolconv), pricerdata->npricingprobs) );
3551 
3552  /* alloc memory for solution values of variables in pricing problems */
3553  norigvars = SCIPgetNOrigVars(origprob);
3554  pricerdata->maxsolvals = SCIPcalcMemGrowSize(scip, norigvars);
3555  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(pricerdata->solvals), pricerdata->maxsolvals) );
3556 
3557  SCIP_CALL( SCIPcreateCPUClock(scip, &(pricerdata->freeclock)) );
3558  SCIP_CALL( SCIPcreateCPUClock(scip, &(pricerdata->transformclock)) );
3559 
3560  pricerdata->solvedsubmipsoptimal = 0;
3561  pricerdata->solvedsubmipsheur = 0;
3562  pricerdata->calls = 0;
3563  pricerdata->pricingiters = 0;
3564 
3565  /* set variable type for master variables */
3566  SCIP_CALL( SCIPgetBoolParam(origprob, "relaxing/gcg/discretization", &discretization) );
3567  if( discretization && SCIPgetNContVars(origprob) == 0 )
3568  {
3569  pricerdata->vartype = SCIP_VARTYPE_INTEGER;
3570  }
3571  else
3572  {
3573  pricerdata->vartype = SCIP_VARTYPE_CONTINUOUS;
3574  }
3575 
3576  SCIP_CALL( SCIPhashmapCreate(&(pricerdata->mapcons2idx), SCIPblkmem(scip), 10 * nmasterconss +1) );
3577  for( i = 0; i < nmasterconss; i++ )
3578  {
3579  SCIP_CALL( SCIPhashmapInsert(pricerdata->mapcons2idx, masterconss[i], (void*)(size_t)i) );
3580  assert((int)(size_t)SCIPhashmapGetImage(pricerdata->mapcons2idx, masterconss[i]) == i); /*lint !e507*/
3581  }
3582 
3583  pricerdata->npricedvars = 0;
3584  pricerdata->maxpricedvars = SCIPcalcMemGrowSize(scip, 50);
3585  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pricerdata->pricedvars, pricerdata->maxpricedvars) );
3586 
3587  pricerdata->nroundsredcost = 0;
3588 #ifdef SCIP_STATISTIC
3589  pricerdata->rootlpsol = NULL;
3590  pricerdata->rootfarkastime = 0.0;
3591  pricerdata->dualdiff = 0.0;
3592  pricerdata->dualdiffround = -1;
3593  pricerdata->nrootbounds = 0;
3594  pricerdata->maxrootbounds = 50;
3595  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pricerdata->rootpbs, pricerdata->maxrootbounds) );
3596  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pricerdata->rootdbs, pricerdata->maxrootbounds) );
3597  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pricerdata->roottimes, pricerdata->maxrootbounds) );
3598  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pricerdata->rootdualdiffs, pricerdata->maxrootbounds) );
3599  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pricerdata->dualvalues, pricerdata->maxrootbounds) );
3600  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pricerdata->dualsolconvs, pricerdata->maxrootbounds) );
3601  SCIP_CALL( SCIPallocMemoryArray(scip, &(pricerdata->nodetimehist), PRICER_STAT_ARRAYLEN_TIME) ); /*lint !e506*/
3602  SCIP_CALL( SCIPallocMemoryArray(scip, &(pricerdata->foundvarshist), PRICER_STAT_ARRAYLEN_VARS) ); /*lint !e506*/
3603 
3604  BMSclearMemoryArray(pricerdata->nodetimehist, PRICER_STAT_ARRAYLEN_TIME);
3605  BMSclearMemoryArray(pricerdata->foundvarshist, PRICER_STAT_ARRAYLEN_VARS);
3606 #endif
3607 
3608  pricerdata->rootnodedegeneracy = 0.0;
3609  pricerdata->avgrootnodedegeneracy = 0.0;
3610  pricerdata->ndegeneracycalcs = 0;
3611 
3612  /* sort solvers by priority */
3613  SCIPsortPtr((void**)pricerdata->solvers, GCGsolverComp, pricerdata->nsolvers);
3614 
3615  SCIP_CALL( pricingcontroller->initSol() );
3616 
3617  SCIP_CALL( solversInitsol() );
3618 
3619  /* if maxobj should be used, compute it */
3620  if( pricerdata->usemaxobj )
3621  {
3622  SCIP_Bool reliable;
3623  pricerdata->maxobj = 0.0;
3624  reliable = TRUE;
3625  for( i = 0; i < SCIPgetNVars(origprob); ++i )
3626  {
3627  SCIP_VAR* var;
3628  SCIP_Real obj;
3629  SCIP_Real ub;
3630  SCIP_Real lb;
3631 
3632  var = SCIPgetVars(origprob)[i];
3633  obj = SCIPvarGetObj(var);
3634  ub = SCIPvarGetUbGlobal(var);
3635  lb = SCIPvarGetLbGlobal(var);
3636 
3637  /* check if influence of variable on objective is bounded */
3638  if( (SCIPisInfinity(origprob, ub) && SCIPisPositive(origprob, obj))
3639  || (SCIPisInfinity(origprob, -lb) && SCIPisNegative(origprob, obj)) )
3640  {
3641  /* if it is not bounded, maxobj is not reliable; use large, heuristic value */
3642  pricerdata->maxobj += pricerdata->factorunreliable* ABS(obj);
3643  reliable = FALSE;
3644  }
3645  else
3646  /* if it is bounded, add maximum difference to maxobj */
3647  pricerdata->maxobj += MAX(ub * obj, lb * obj) - MIN(ub * obj, lb * obj);
3648  }
3649  if( !reliable && pricerdata->onlyreliablebigm )
3650  {
3651  pricerdata->useartificialvars = FALSE;
3652  pricerdata->maxobj = SCIPinfinity(origprob);
3653  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Big M to be used for artificial variables not reliable; use regular Farkas pricing instead.\n");
3654  }
3655  else if( !reliable && !pricerdata->onlyreliablebigm )
3656  SCIPwarningMessage(scip, "Big M used for artificial variables not reliable. This might lead to wrong solutions.\n");
3657  }
3658  else
3659  pricerdata->maxobj = SCIPinfinity(origprob);
3660 
3661  createStabilization();
3662  SCIP_CALL( stabilization->setNLinkingconsvals(GCGgetNVarLinkingconss(origprob)) );
3663  SCIP_CALL( stabilization->setNConvconsvals(GCGgetNPricingprobs(origprob)) );
3664 
3665  if( pricerdata->usecolpool )
3666  SCIP_CALL( createColpool() );
3667 
3668  SCIP_CALL( createPricestore() );
3669 
3670  SCIP_CALL( SCIPactivateEventHdlrDisplay(scip_) );
3671 
3672  return SCIP_OKAY;
3673 }
3674 
3675 
3676 /** solving process deinitialization method of variable pricer (called before branch and bound process data is freed) */
3677 SCIP_DECL_PRICEREXITSOL(ObjPricerGcg::scip_exitsol)
3678 {
3679  int i;
3680 
3681  assert(scip == scip_);
3682  assert(pricer != NULL);
3683  assert(pricerdata != NULL);
3684 
3685  SCIP_CALL( solversExitsol() );
3686 
3687  SCIP_CALL( pricingcontroller->exitSol() );
3688 
3689  if( stabilization != NULL )
3690  delete stabilization;
3691 
3692  stabilization = NULL;
3693 
3694  if( pricerdata->usecolpool )
3695  SCIP_CALL( GCGcolpoolFree(scip_, &colpool) );
3696 
3697  SCIP_CALL( GCGpricestoreFree(scip_, &pricestore) );
3698 
3699  SCIPhashmapFree(&(pricerdata->mapcons2idx));
3700 
3701  SCIPfreeBlockMemoryArray(scip, &(pricerdata->pricingprobs), pricerdata->npricingprobs);
3702  SCIPfreeBlockMemoryArray(scip, &(pricerdata->npointsprob), pricerdata->npricingprobs);
3703  SCIPfreeBlockMemoryArray(scip, &(pricerdata->nraysprob), pricerdata->npricingprobs);
3704 
3705  SCIPfreeBlockMemoryArray(scip, &(pricerdata->farkascallsdist), pricerdata->npricingprobs);
3706  SCIPfreeBlockMemoryArray(scip, &(pricerdata->farkasfoundvars), pricerdata->npricingprobs);
3707  SCIPfreeBlockMemoryArray(scip, &(pricerdata->farkasnodetimedist), pricerdata->npricingprobs);
3708 
3709  SCIPfreeBlockMemoryArray(scip, &(pricerdata->redcostcallsdist), pricerdata->npricingprobs);
3710  SCIPfreeBlockMemoryArray(scip, &(pricerdata->redcostfoundvars), pricerdata->npricingprobs);
3711  SCIPfreeBlockMemoryArray(scip, &(pricerdata->redcostnodetimedist), pricerdata->npricingprobs);
3712 
3713 
3714  SCIPfreeBlockMemoryArray(scip, &(pricerdata->dualsolconv), pricerdata->npricingprobs);
3715 
3716  SCIPfreeBlockMemoryArray(scip, &(pricerdata->solvals), pricerdata->maxsolvals);
3717 
3718  for( i = 0; i < pricerdata->nartificialvars; i++ )
3719  {
3720 // SCIP_CALL( SCIPdropVarEvent(scip, pricerdata->artificialvars[i], SCIP_EVENTTYPE_VARDELETED,
3721 // pricerdata->eventhdlr, NULL, -1) );
3722 
3723  SCIP_CALL( SCIPreleaseVar(scip, &pricerdata->artificialvars[i]) );
3724  }
3725  SCIPfreeBlockMemoryArrayNull(scip, &(pricerdata->artificialvars), pricerdata->maxartificialvars);
3726  pricerdata->nartificialvars = 0;
3727 
3728  for( i = 0; i < pricerdata->npricedvars; i++ )
3729  {
3730  SCIP_CALL( SCIPdropVarEvent(scip, pricerdata->pricedvars[i], SCIP_EVENTTYPE_VARDELETED,
3731  pricerdata->eventhdlr, NULL, -1) );
3732 
3733  SCIP_CALL( SCIPreleaseVar(scip, &pricerdata->pricedvars[i]) );
3734  }
3735  SCIPfreeBlockMemoryArray(scip, &pricerdata->pricedvars, pricerdata->maxpricedvars);
3736  pricerdata->maxpricedvars = 0;
3737  pricerdata->npricedvars = 0;
3738 
3739 #ifdef SCIP_STATISTIC
3740  SCIPfreeBlockMemoryArray(scip, &pricerdata->rootpbs, pricerdata->maxrootbounds);
3741  SCIPfreeBlockMemoryArray(scip, &pricerdata->rootdbs, pricerdata->maxrootbounds);
3742  SCIPfreeBlockMemoryArray(scip, &pricerdata->roottimes, pricerdata->maxrootbounds);
3743  SCIPfreeBlockMemoryArray(scip, &pricerdata->rootdualdiffs, pricerdata->maxrootbounds);
3744  SCIPfreeBlockMemoryArray(scip, &pricerdata->dualvalues, pricerdata->maxrootbounds);
3745  SCIPfreeBlockMemoryArray(scip, &pricerdata->dualsolconvs, pricerdata->maxrootbounds);
3746  SCIPfreeSol(scip, &pricerdata->rootlpsol);
3747  pricerdata->rootlpsol = NULL;
3748  pricerdata->maxrootbounds = 0;
3749  pricerdata->nrootbounds = 0;
3750  pricerdata->rootfarkastime = 0.0;
3751  pricerdata->dualdiff = 0.0;
3752  SCIPfreeMemoryArrayNull(scip, &(pricerdata->nodetimehist));
3753  SCIPfreeMemoryArrayNull(scip, &(pricerdata->foundvarshist));
3754 
3755  pricerdata->nodetimehist = NULL;
3756  pricerdata->foundvarshist = NULL;
3757 #endif
3758 
3759  SCIP_CALL( SCIPfreeClock(scip, &(pricerdata->freeclock)) );
3760  SCIP_CALL( SCIPfreeClock(scip, &(pricerdata->transformclock)) );
3761 
3762  for( i = 0; i < pricerdata->npricingprobs; ++i )
3763  {
3764  SCIPfreeBlockMemoryArrayNull(scip, &(pricerdata->realdualvalues[i]), pricerdata->maxrealdualvalues[i]);
3765  }
3766  SCIPfreeBlockMemoryArray(scip, &(pricerdata->realdualvalues), pricerdata->maxrealdualvaluescapacity);
3767  SCIPfreeBlockMemoryArray(scip, &(pricerdata->maxrealdualvalues), pricerdata->maxrealdualvaluescapacity);
3768 
3769  return SCIP_OKAY;
3770 }
3771 
3772 
3773 /** reduced cost pricing method of variable pricer for feasible LPs */
3774 SCIP_DECL_PRICERREDCOST(ObjPricerGcg::scip_redcost)
3775 { /*lint -esym(715, stopearly)*/
3776  SCIP_RETCODE retcode;
3777 
3778  assert(scip == scip_);
3779  assert(pricer != NULL);
3780  assert(pricerdata != NULL);
3781  assert(reducedcostpricing != NULL);
3782  assert(farkaspricing != NULL);
3783 
3784  *result = SCIP_DIDNOTRUN;
3785 
3786  if( reducedcostpricing->getCalls() == 0 )
3787  {
3788  /** @todo This is just a workaround around SCIP stages! */
3789  if( farkaspricing->getCalls() == 0 )
3790  {
3791  SCIP_CALL( GCGconsMasterbranchAddRootCons(scip) );
3792  }
3793  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Starting reduced cost pricing...\n");
3794  }
3795 
3796  if( SCIPisStopped(scip_) )
3797  {
3798  return SCIP_OKAY;
3799  }
3800 
3801  if( SCIPgetCurrentNode(scip) == SCIPgetRootNode(scip) && GCGsepaGetNCuts(scip) == 0 && reducedcostpricing->getCalls() > 0
3802  && GCGmasterIsCurrentSolValid(scip) && pricerdata->artificialused )
3803  {
3804  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Starting reduced cost pricing without artificial variables...\n");
3805  }
3806 
3807  if( !GCGmasterIsCurrentSolValid(scip) )
3808  pricerdata->artificialused = TRUE;
3809  else
3810  pricerdata->artificialused = FALSE;
3811 
3812 
3813  /* update number of reduced cost pricing rounds at the current node */
3814  if( SCIPgetNNodes(scip) == pricerdata->currnodenr )
3815  {
3816  pricerdata->nroundsredcost++;
3817  }
3818  else
3819  {
3820  pricerdata->currnodenr = SCIPgetNNodes(scip);
3821  pricerdata->newnode = TRUE;
3822  pricerdata->nroundsredcost = 0;
3823  }
3824 
3825  /* if the number of reduced cost pricing rounds at the current node exceeds the limit (and we are not at the root), stop pricing;
3826  * we always stop pricing, if the maximum number of reduced cost rounds is set to 0
3827  */
3828  if( reducedcostpricing->getMaxrounds() == 0 || (pricerdata->nroundsredcost >= reducedcostpricing->getMaxrounds() && pricerdata->currnodenr != 1) )
3829  {
3830  SCIPdebugMessage("pricing aborted at node %lld\n", pricerdata->currnodenr);
3831  return SCIP_OKAY;
3832  }
3833 
3834  *result = SCIP_SUCCESS;
3835 
3836  /* perform pricing */
3837 
3838  pricingcontroller->increaseEagerage();
3839 
3840  GCGpricestoreEndFarkas(pricestore);
3841  if( pricerdata->usecolpool )
3842  GCGcolpoolEndFarkas(colpool);
3843 
3844  SCIP_CALL( reducedcostpricing->startClock() );
3845  retcode = priceNewVariables(reducedcostpricing, result, lowerbound);
3846  SCIP_CALL( reducedcostpricing->stopClock() );
3847 
3848 #ifdef SCIP_STATISTIC
3849  if( SCIPgetCurrentNode(scip_) == SCIPgetRootNode(scip_) && GCGsepaGetNCuts(scip_) == 0 )
3850  {
3851  SCIP_CALL( addRootBounds(SCIPgetLPObjval(scip_), *lowerbound) );
3852  SCIPdebugMessage("Add bounds, %f\n", *lowerbound);
3853  }
3854 #endif
3855  return retcode;
3856 }
3857 
3858 SCIP_RETCODE ObjPricerGcg::ensureSizeArtificialvars(
3859  int size /**< needed size */
3860 )
3861 {
3862  assert(pricerdata != NULL);
3863  assert(pricerdata->artificialvars != NULL);
3864 
3865  if( pricerdata->maxartificialvars < size )
3866  {
3867  int oldsize = pricerdata->maxartificialvars;
3868  pricerdata->maxartificialvars = SCIPcalcMemGrowSize(scip_, size);
3869  SCIP_CALL( SCIPreallocBlockMemoryArray(scip_, &(pricerdata->artificialvars), oldsize, pricerdata->maxartificialvars) );
3870  }
3871  assert(pricerdata->maxartificialvars >= size);
3872 
3873  return SCIP_OKAY;
3874 }
3875 
3876 /** add artificial vars */
3878  )
3879 {
3880  SCIP_CONS** masterconss;
3881  int nmasterconss;
3882  int nconvconss;
3883  char varname[SCIP_MAXSTRLEN];
3884  int i;
3885  SCIP_Real bigm;
3886 
3887  assert(pricerdata != NULL);
3888  assert(pricerdata->pricedvars != NULL);
3889 
3890  masterconss = GCGgetMasterConss(origprob);
3891  nmasterconss = GCGgetNMasterConss(origprob);
3892 
3893  nconvconss = GCGgetNPricingprobs(origprob);
3894 
3895  /* if bigmartificial is negative, use maxobj */
3896  if( pricerdata->usemaxobj )
3897  bigm = pricerdata->maxobj;
3898  else
3899  bigm = pricerdata->bigmartificial;
3900 
3901  for( i = 0; i < nmasterconss; ++i )
3902  {
3903  if( !SCIPisInfinity(scip_, -1.0*GCGconsGetLhs(scip_, masterconss[i]) ))
3904  {
3905  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "art_lhs_%s", SCIPconsGetName(masterconss[i]));
3906  ensureSizeArtificialvars(pricerdata->nartificialvars + 1);
3907  SCIP_CALL( GCGcreateArtificialVar(scip_, &(pricerdata->artificialvars[pricerdata->nartificialvars]), varname, bigm) );
3908  SCIP_CALL( SCIPaddCoefLinear(scip_, masterconss[i], pricerdata->artificialvars[pricerdata->nartificialvars], 1.0) );
3909  SCIP_CALL( SCIPaddVar(scip_, pricerdata->artificialvars[pricerdata->nartificialvars]) );
3910  ++(pricerdata->nartificialvars);
3911  }
3912 
3913  if( !SCIPisInfinity(scip_, GCGconsGetRhs(scip_, masterconss[i]) ))
3914  {
3915  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "art_rhs_%s", SCIPconsGetName(masterconss[i]));
3916  ensureSizeArtificialvars(pricerdata->nartificialvars + 1);
3917  SCIP_CALL( GCGcreateArtificialVar(scip_, &(pricerdata->artificialvars[pricerdata->nartificialvars]), varname, bigm) );
3918  SCIP_CALL( SCIPaddCoefLinear(scip_, masterconss[i], pricerdata->artificialvars[pricerdata->nartificialvars], -1.0) );
3919  SCIP_CALL( SCIPaddVar(scip_, pricerdata->artificialvars[pricerdata->nartificialvars]) );
3920  ++(pricerdata->nartificialvars);
3921  }
3922  }
3923 
3924  for( i = 0; i < nconvconss; ++i )
3925  {
3926  SCIP_CONS* convcons;
3927 
3929  continue;
3930 
3931  convcons = GCGgetConvCons(origprob, i);
3932 
3933  if( !SCIPisInfinity(scip_, -1.0*GCGconsGetLhs(scip_, convcons) ))
3934  {
3935  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "art_lhs_%s", SCIPconsGetName(convcons));
3936  ensureSizeArtificialvars(pricerdata->nartificialvars + 1);
3937  SCIP_CALL( GCGcreateArtificialVar(scip_, &(pricerdata->artificialvars[pricerdata->nartificialvars]), varname, bigm) );
3938  SCIP_CALL( SCIPaddCoefLinear(scip_, convcons, pricerdata->artificialvars[pricerdata->nartificialvars], 1.0) );
3939  SCIP_CALL( SCIPaddVar(scip_, pricerdata->artificialvars[pricerdata->nartificialvars]) );
3940  ++(pricerdata->nartificialvars);
3941  }
3942 
3943  if( !SCIPisInfinity(scip_, GCGconsGetRhs(scip_, convcons) ))
3944  {
3945  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "art_rhs_%s", SCIPconsGetName(convcons));
3946  ensureSizeArtificialvars(pricerdata->nartificialvars + 1);
3947  SCIP_CALL( GCGcreateArtificialVar(scip_, &(pricerdata->artificialvars[pricerdata->nartificialvars]), varname, bigm) );
3948  SCIP_CALL( SCIPaddCoefLinear(scip_, convcons, pricerdata->artificialvars[pricerdata->nartificialvars], -1.0) );
3949  SCIP_CALL( SCIPaddVar(scip_, pricerdata->artificialvars[pricerdata->nartificialvars]) );
3950  ++(pricerdata->nartificialvars);
3951  }
3952 
3953  }
3954 
3955  pricerdata->artificialused = TRUE;
3956 
3957  return SCIP_OKAY;
3958 }
3959 
3960 /** farcas pricing method of variable pricer for infeasible LPs */
3961 SCIP_DECL_PRICERFARKAS(ObjPricerGcg::scip_farkas)
3962 {
3963  SCIP_RETCODE retcode;
3964  SCIP_SOL** origsols;
3965  int norigsols;
3966  int nstoredsols;
3967 
3968  assert(scip == scip_);
3969  assert(pricer != NULL);
3970  assert(pricerdata != NULL);
3971  assert(reducedcostpricing != NULL);
3972  assert(farkaspricing != NULL);
3973 
3974  *result = SCIP_DIDNOTRUN;
3975 
3976  /** @todo This is just a workaround around SCIP stages! */
3977  if( reducedcostpricing->getCalls() == 0 && farkaspricing->getCalls() == 0 )
3978  {
3979  SCIP_CALL( GCGconsMasterbranchAddRootCons(scip) );
3980  }
3981 
3982  /* get solutions from the original problem */
3983  origsols = SCIPgetSols(origprob);
3984  norigsols = SCIPgetNSols(origprob);
3985  assert(norigsols >= 0);
3986 
3987  /* update current node */
3988  if( SCIPgetNNodes(scip) != pricerdata->currnodenr )
3989  {
3990  pricerdata->currnodenr = SCIPgetNNodes(scip);
3991  pricerdata->newnode = TRUE;
3992  }
3993 
3994  *result = SCIP_SUCCESS;
3995 
3996  /* Add already known solutions for the original problem to the master variable space */
3997  /** @todo This is just a workaround around SCIP stages! */
3998  nstoredsols = 0;
3999  if( farkaspricing->getCalls() == 0 )
4000  {
4001  int i;
4002 
4003  for( i = 0; i < norigsols; ++i )
4004  {
4005  SCIP_Bool stored;
4006  assert(origsols[i] != NULL);
4007  SCIPdebugMessage("Transferring original feasible solution found by <%s> to master problem\n",
4008  SCIPsolGetHeur(origsols[i]) == NULL ? "relaxation" : SCIPheurGetName(SCIPsolGetHeur(origsols[i])));
4009  SCIP_CALL( GCGmasterTransOrigSolToMasterVars(scip, origsols[i], &stored) );
4010  if( stored )
4011  {
4012  ++nstoredsols;
4013  }
4014  }
4015  SCIPdebugMessage("GCGmasterTransOrigSolToMasterVars() transferred %d original feasible solutions\n",
4016  nstoredsols);
4017  /* return if we transferred solutions as the master should be feasible */
4018  if( nstoredsols > 0 )
4019  {
4020  farkaspricing->incCalls();
4021 #ifdef SCIP_STATISTIC
4022  pricerdata->rootfarkastime = SCIPgetSolvingTime(scip_);
4023 #endif
4024  return SCIP_OKAY;
4025  }
4026  }
4027 
4028  if( pricerdata->useartificialvars && farkaspricing->getCalls() == 0 )
4029  {
4030  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Add artificial variables ensuring the restricted master problem is feasible.\n");
4031  SCIP_CALL( addArtificialVars() );
4032  farkaspricing->incCalls();
4033  return SCIP_OKAY;
4034  }
4035 
4036  GCGpricestoreStartFarkas(pricestore);
4037  if( pricerdata->usecolpool )
4038  GCGcolpoolStartFarkas(colpool);
4039 
4040  SCIP_CALL( farkaspricing->startClock() );
4041  retcode = priceNewVariables(farkaspricing, result, NULL);
4042  SCIP_CALL( farkaspricing->stopClock() );
4043 
4044 #ifdef SCIP_STATISTIC
4045  pricerdata->rootfarkastime = SCIPgetSolvingTime(scip_);
4046 #endif
4047 
4048  return retcode;
4049 }
4050 
4051 /** create the pointers for the pricing types */
4053 {
4054  farkaspricing = new FarkasPricing(scip_);
4055  SCIP_CALL( farkaspricing->addParameters() );
4056 
4057  reducedcostpricing = new ReducedCostPricing(scip_);
4058  SCIP_CALL( reducedcostpricing->addParameters() );
4059 
4060  pricingtype = NULL;
4061 
4062  return SCIP_OKAY;
4063 }
4064 
4065 /** create the pricing controller */
4067 {
4068  pricingcontroller = new Pricingcontroller(scip_);
4069  SCIP_CALL( pricingcontroller->addParameters() );
4070 
4071  return SCIP_OKAY;
4072 }
4073 
4074 /** create the pointers for the stabilization */
4076 {
4077  SCIP_Bool usehybridascent;
4078 
4079  usehybridascent = pricerdata->hybridascent ||
4081 
4082 
4083  stabilization = new Stabilization(scip_, reducedcostpricing, usehybridascent);
4084 }
4085 
4087 {
4088  assert(farkaspricing != NULL);
4089  assert(reducedcostpricing != NULL);
4090  assert(pricerdata != NULL);
4091 
4092  SCIP_CALL( GCGcolpoolCreate(scip_, &colpool, pricerdata->colpoolagelimit) );
4093 
4094  return SCIP_OKAY;
4095 }
4096 
4098 {
4099  SCIP_CALL( GCGpricestoreCreate(scip_, &pricestore,
4100  pricerdata->redcostfac, pricerdata->objparalfac, pricerdata->orthofac,
4101  pricerdata->mincolorth,
4102  pricerdata->efficiacychoice) );
4103 
4104  return SCIP_OKAY;
4105 }
4106 /*
4107  * variable pricer specific interface methods
4108  */
4109 
4110 /** creates the GCG variable pricer and includes it in SCIP */
4111 extern "C"
4113  SCIP* scip, /**< SCIP data structure */
4114  SCIP* origprob /**< SCIP data structure of the original problem */
4115  )
4116 { /*lint -esym(429,pricer) */
4117  ObjPricerGcg* pricer;
4118  SCIP_PRICERDATA* pricerdata = NULL;
4119 
4120  SCIP_CALL( SCIPallocMemory(scip, &pricerdata) );
4121 
4122  /* initialize solvers array */
4123  pricerdata->solvers = NULL;
4124  pricerdata->nsolvers = 0;
4125  pricerdata->realdualvalues = NULL;
4126 
4127 #ifdef SCIP_STATISTIC
4128  pricerdata->nodetimehist = NULL;
4129  pricerdata->foundvarshist = NULL;
4130 #endif
4131 
4132  pricer = new ObjPricerGcg(scip, origprob, PRICER_NAME, PRICER_DESC, PRICER_PRIORITY, PRICER_DELAY, pricerdata);
4133  /* include variable pricer */
4134  SCIP_CALL( SCIPincludeObjPricer(scip, pricer, TRUE) );
4135 
4136  SCIP_CALL( pricer->createPricingTypes() );
4137  SCIP_CALL( pricer->createPricingcontroller() );
4138 
4139  /* include event handler into master SCIP */
4140  SCIP_CALL( SCIPincludeEventhdlr(scip, EVENTHDLR_NAME, EVENTHDLR_DESC,
4143  NULL) );
4144 
4145  pricerdata->eventhdlr = SCIPfindEventhdlr(scip, EVENTHDLR_NAME);
4146 
4147  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/abortpricingint",
4148  "should pricing be aborted due to integral objective function?",
4149  &pricerdata->abortpricingint, TRUE, DEFAULT_ABORTPRICINGINT, NULL, NULL) );
4150 
4151  SCIP_CALL( SCIPaddRealParam(origprob, "pricing/masterpricer/abortpricinggap",
4152  "gap between dual bound and RMP objective at which pricing is aborted",
4153  &pricerdata->abortpricinggap, TRUE, DEFAULT_ABORTPRICINGGAP, 0.0, 1.0, NULL, NULL) );
4154 
4155  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/dispinfos",
4156  "should additional informations concerning the pricing process be displayed?",
4157  &pricerdata->dispinfos, FALSE, DEFAULT_DISPINFOS, NULL, NULL) );
4158 
4159  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/threads",
4160  "how many threads should be used to concurrently solve the pricing problem (0 to guess threads by OpenMP)",
4161  &ObjPricerGcg::threads, FALSE, DEFAULT_THREADS, 0, 4096, NULL, NULL) );
4162 
4163  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/stabilization",
4164  "should stabilization be performed?",
4165  &pricerdata->stabilization, FALSE, DEFAULT_STABILIZATION, NULL, NULL) );
4166 
4167  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/stabilizationtree",
4168  "should stabilization be performed in the tree (in nodes other than the root node)?",
4169  &pricerdata->stabilizationtree, FALSE, DEFAULT_STABILIZATIONTREE, NULL, NULL) );
4170 
4171  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/usecolpool",
4172  "should the colpool be checked for negative redcost cols before solving the pricing problems?",
4173  &pricerdata->usecolpool, FALSE, DEFAULT_USECOLPOOL, NULL, NULL) );
4174 
4175  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/stabilization/hybridascent",
4176  "should hybridization of smoothing with an ascent method be enabled?",
4177  &pricerdata->hybridascent, FALSE, DEFAULT_HYBRIDASCENT, NULL, NULL) );
4178 
4179  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/stabilization/hybridascentnoagg",
4180  "should hybridization of smoothing with an ascent method be enabled if pricing problems cannot be aggregation?",
4181  &pricerdata->hybridascentnoagg, FALSE, DEFAULT_HYBRIDASCENT_NOAGG, NULL, NULL) );
4182 
4183  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/useartificialvars",
4184  "should artificial variables be used to make the RMP feasible (instead of applying Farkas pricing)?",
4185  &pricerdata->useartificialvars, FALSE, DEFAULT_USEARTIFICIALVARS, NULL, NULL) );
4186 
4187  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/usemaxobj",
4188  "use maxobj for big M objective of artificial variables",
4189  &pricerdata->usemaxobj, FALSE, DEFAULT_USEMAXOBJ, NULL, NULL) );
4190 
4191  SCIP_CALL( SCIPaddBoolParam(origprob, "pricing/masterpricer/onlyreliablebigm",
4192  "only use maxobj for big M objective of artificial variables if it is reliable",
4193  &pricerdata->onlyreliablebigm, FALSE, DEFAULT_ONLYRELIABLEBIGM, NULL, NULL) );
4194 
4195  SCIP_CALL( SCIPaddRealParam(origprob, "pricing/masterpricer/factorunreliable",
4196  "factor to use for objective of unbounded variables",
4197  &pricerdata->factorunreliable, FALSE, DEFAULT_FACTORUNRELIABLE, 0.0, SCIPinfinity(origprob), NULL, NULL) );
4198 
4199  SCIP_CALL( SCIPaddRealParam(origprob, "pricing/masterpricer/bigmartificial",
4200  "value for for big M objective of artificial variables (negative if max obj should be used)",
4201  &pricerdata->bigmartificial, FALSE, DEFAULT_BIGMARTIFICIAL, 0.0, SCIPinfinity(origprob), NULL, NULL) );
4202 
4203  SCIP_CALL( SCIPsetIntParam(scip, "lp/disablecutoff", DEFAULT_DISABLECUTOFF) );
4204 
4205  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/disablecutoff",
4206  "should the cutoffbound be applied in master LP solving (0: on, 1:off, 2:auto)?",
4207  &pricerdata->disablecutoff, FALSE, DEFAULT_DISABLECUTOFF, 0, 2, paramChgdDisablecutoff, NULL) );
4208 
4209  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/colpool/agelimit",
4210  "age limit for columns in column pool? (-1 for no limit)",
4211  &pricerdata->colpoolagelimit, FALSE, DEFAULT_COLPOOL_AGELIMIT, -1, INT_MAX, NULL, NULL) );
4212 
4213  SCIP_CALL( SCIPaddRealParam(origprob, "pricing/masterpricer/pricestore/redcostfac",
4214  "factor of -redcost/norm in score function",
4215  &pricerdata->redcostfac, FALSE, DEFAULT_PRICE_REDCOSTFAC, 0.0, 10.0, NULL, NULL) );
4216 
4217  SCIP_CALL( SCIPaddRealParam(origprob, "pricing/masterpricer/pricestore/objparalfac",
4218  "factor of objective parallelism in score function",
4219  &pricerdata->objparalfac, FALSE, DEFAULT_PRICE_OBJPARALFAC, 0.0, 10.0, NULL, NULL) );
4220 
4221  SCIP_CALL( SCIPaddRealParam(origprob, "pricing/masterpricer/pricestore/orthofac",
4222  "factor of orthogonalities in score function",
4223  &pricerdata->orthofac, FALSE, DEFAULT_PRICE_ORTHOFAC, 0.0, 10.0, NULL, NULL) );
4224 
4225  SCIP_CALL( SCIPaddRealParam(origprob, "pricing/masterpricer/pricestore/mincolorth",
4226  "minimal orthogonality of columns to add",
4227  &pricerdata->mincolorth, FALSE, DEFAULT_PRICE_MINCOLORTH, 0.0, 1.0, NULL, NULL) );
4228 
4229  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/pricestore/efficiacychoice",
4230  "choice to base efficiacy on",
4231  (int*)&pricerdata->efficiacychoice, FALSE, DEFAULT_PRICE_EFFICIACYCHOICE, 0, 2, NULL, NULL) );
4232 
4233 
4234  return SCIP_OKAY;
4235 }
4236 
4237 /** returns the pointer to the scip instance representing the original problem */
4238 extern "C"
4240  SCIP* scip /**< SCIP data structure */
4241  )
4242 {
4243  ObjPricerGcg* pricer;
4244 
4245  assert(scip != NULL);
4246 
4247  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4248  assert(pricer != NULL);
4249 
4250  return pricer->getOrigprob();
4251 }
4252 
4253 /** returns the array of variables that were priced in during the solving process */
4254 extern "C"
4256  SCIP* scip /**< SCIP data structure */
4257  )
4258 {
4259  ObjPricerGcg* pricer;
4260  SCIP_PRICERDATA* pricerdata;
4261 
4262  assert(scip != NULL);
4263 
4264  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4265  assert(pricer != NULL);
4266 
4267  pricerdata = pricer->getPricerdata();
4268  assert(pricerdata != NULL);
4269 
4270  return pricerdata->pricedvars;
4271 }
4272 
4273 /** returns the number of variables that were priced in during the solving process */
4274 extern "C"
4276  SCIP* scip /**< SCIP data structure */
4277  )
4278 {
4279  ObjPricerGcg* pricer;
4280  SCIP_PRICERDATA* pricerdata;
4281 
4282  assert(scip != NULL);
4283 
4284  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4285  assert(pricer != NULL);
4286 
4287  pricerdata = pricer->getPricerdata();
4288  assert(pricerdata != NULL);
4289 
4290  return pricerdata->npricedvars;
4291 }
4292 
4293 
4294 /** adds the given constraint and the given position to the hashmap of the pricer */
4295 extern "C"
4297  SCIP* scip, /**< SCIP data structure */
4298  SCIP_CONS* cons, /**< the constraint that should be added */
4299  int pos /**< the position of the constraint in the relaxator's masterconss array */
4300  )
4301 {
4302  ObjPricerGcg* pricer;
4303  SCIP_PRICERDATA* pricerdata;
4304 
4305  assert(scip != NULL);
4306  assert(cons != NULL);
4307  assert(pos >= 0);
4308 
4309  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4310  assert(pricer != NULL);
4311 
4312  pricerdata = pricer->getPricerdata();
4313  assert(pricerdata != NULL);
4314 
4315  SCIP_CALL( SCIPhashmapInsert(pricerdata->mapcons2idx, cons, (void*)(size_t)pos) );
4316  assert((int)(size_t)SCIPhashmapGetImage(pricerdata->mapcons2idx, cons) == pos); /*lint !e507*/
4317 
4318  SCIPdebugMessage("Added cons %s (%p) to hashmap with index %d\n", SCIPconsGetName(cons), (void*) cons, pos);
4319 
4320  return SCIP_OKAY;
4321 }
4322 
4323 #ifdef SCIP_STATISTIC
4324 /** sets the optimal LP solution in the pricerdata */
4325 extern "C"
4326 SCIP_RETCODE GCGmasterSetRootLPSol(
4327  SCIP* scip, /**< SCIP data structure */
4328  SCIP_SOL** sol /**< pointer to optimal solution to root LP */
4329  )
4330 {
4331  ObjPricerGcg* pricer;
4332  SCIP_PRICERDATA* pricerdata;
4333 
4334  assert(scip != NULL);
4335 
4336  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4337  assert(pricer != NULL);
4338 
4339  pricerdata = pricer->getPricerdata();
4340  assert(pricerdata != NULL);
4341 
4342  pricerdata->rootlpsol = *sol;
4343 
4344  return SCIP_OKAY;
4345 }
4346 
4347 /** gets the optimal LP solution in the pricerdata */
4348 extern "C"
4349 SCIP_SOL* GCGmasterGetRootLPSol(
4350  SCIP* scip /**< SCIP data structure */
4351  )
4352 {
4353  ObjPricerGcg* pricer;
4354  SCIP_PRICERDATA* pricerdata;
4355 
4356  assert(scip != NULL);
4357 
4358  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4359  assert(pricer != NULL);
4360 
4361  pricerdata = pricer->getPricerdata();
4362  assert(pricerdata != NULL);
4363 
4364  return pricerdata->rootlpsol;
4365 }
4366 #endif
4367 
4368 /** includes a solver into the pricer data */
4369 extern "C"
4371  SCIP* scip, /**< SCIP data structure */
4372  const char* name, /**< name of solver */
4373  const char* desc, /**< description of solver */
4374  int priority, /**< priority of solver */
4375  SCIP_Bool heurenabled, /**< flag to indicate whether heuristic solving method of the solver is enabled */
4376  SCIP_Bool exactenabled, /**< flag to indicate whether exact solving method of the solver is enabled */
4377  GCG_DECL_SOLVERUPDATE((*solverupdate)), /**< update method for solver */
4378  GCG_DECL_SOLVERSOLVE ((*solversolve)), /**< solving method for solver */
4379  GCG_DECL_SOLVERSOLVEHEUR((*solversolveheur)), /**< heuristic solving method for solver */
4380  GCG_DECL_SOLVERFREE ((*solverfree)), /**< free method of solver */
4381  GCG_DECL_SOLVERINIT ((*solverinit)), /**< init method of solver */
4382  GCG_DECL_SOLVEREXIT ((*solverexit)), /**< exit method of solver */
4383  GCG_DECL_SOLVERINITSOL((*solverinitsol)), /**< initsol method of solver */
4384  GCG_DECL_SOLVEREXITSOL((*solverexitsol)), /**< exitsol method of solver */
4385  GCG_SOLVERDATA* solverdata /**< pricing solver data */
4386  )
4387 {
4388  GCG_SOLVER* solver;
4389  ObjPricerGcg* pricer;
4390  SCIP_PRICERDATA* pricerdata;
4391 
4392  assert(scip != NULL);
4393 
4394  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4395  assert(pricer != NULL);
4396 
4397  pricerdata = pricer->getPricerdata();
4398  assert(pricerdata != NULL);
4399 
4400  /* create pricing solver */
4401  solver = NULL;
4402  SCIP_CALL( GCGsolverCreate(scip, &solver, name, desc, priority, heurenabled, exactenabled,
4403  solverupdate, solversolve, solversolveheur, solverfree, solverinit, solverexit, solverinitsol, solverexitsol,
4404  solverdata) );
4405  assert(solver != NULL);
4406 
4407  /* add solver to pricer data */
4408  if( pricerdata->nsolvers == 0 )
4409  {
4410  SCIP_CALL( SCIPallocMemoryArray(scip_, &(pricerdata->solvers), 1) ); /*lint !e506*/
4411  }
4412  else
4413  {
4414  SCIP_CALL( SCIPreallocMemoryArray(scip_, &(pricerdata->solvers), (size_t)pricerdata->nsolvers+1) );
4415  }
4416  pricerdata->solvers[pricerdata->nsolvers] = solver;
4417  ++pricerdata->nsolvers;
4418 
4419  return SCIP_OKAY;
4420 }
4421 
4422 /** returns the available pricing solvers */
4423 extern "C"
4425  SCIP* scip /**< SCIP data structure */
4426  )
4427 {
4428  ObjPricerGcg* pricer;
4429  SCIP_PRICERDATA* pricerdata;
4430 
4431  assert(scip != NULL);
4432 
4433  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4434  assert(pricer != NULL);
4435 
4436  pricerdata = pricer->getPricerdata();
4437  assert(pricerdata != NULL);
4438 
4439  return pricerdata->solvers;
4440 }
4441 
4442 /** returns the number of available pricing solvers */
4443 extern "C"
4445  SCIP* scip /**< SCIP data structure */
4446  )
4447 {
4448  ObjPricerGcg* pricer;
4449  SCIP_PRICERDATA* pricerdata;
4450 
4451  assert(scip != NULL);
4452 
4453  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4454  assert(pricer != NULL);
4455 
4456  pricerdata = pricer->getPricerdata();
4457  assert(pricerdata != NULL);
4458 
4459  return pricerdata->nsolvers;
4460 }
4461 
4462 /** writes out a list of all pricing problem solvers */
4463 extern "C"
4465  SCIP* scip /**< SCIP data structure */
4466  )
4467 {
4468  ObjPricerGcg* pricer;
4469  SCIP_PRICERDATA* pricerdata;
4470  int nsolvers;
4471  int i;
4472 
4473  assert(scip != NULL);
4474 
4475  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4476  assert(pricer != NULL);
4477 
4478  pricerdata = pricer->getPricerdata();
4479  assert(pricerdata != NULL);
4480 
4481  assert((pricerdata->solvers == NULL) == (pricerdata->nsolvers == 0));
4482 
4483  nsolvers = pricerdata->nsolvers;
4484 
4485  SCIPdialogMessage(scip, NULL, " solver priority heur exact description\n");
4486  SCIPdialogMessage(scip, NULL, " -------------- -------- ----- ----- -----------\n");
4487 
4488  for( i = 0; i < nsolvers; ++i )
4489  {
4490  SCIPdialogMessage(scip, NULL, " %-20s", GCGsolverGetName(pricerdata->solvers[i]));
4491  SCIPdialogMessage(scip, NULL, " %8d", GCGsolverGetPriority(pricerdata->solvers[i]));
4492  SCIPdialogMessage(scip, NULL, " %5s", GCGsolverIsHeurEnabled(pricerdata->solvers[i]) ? "TRUE" : "FALSE");
4493  SCIPdialogMessage(scip, NULL, " %5s", GCGsolverIsExactEnabled(pricerdata->solvers[i]) ? "TRUE" : "FALSE");
4494  SCIPdialogMessage(scip, NULL, " %s\n", GCGsolverGetDesc(pricerdata->solvers[i]));
4495  }
4496 }
4497 
4498 /** prints pricing solver statistics */
4499 extern "C"
4501  SCIP* scip, /**< SCIP data structure */
4502  FILE* file /**< output file */
4503 )
4504 {
4505  ObjPricerGcg* pricer;
4506  SCIP_PRICERDATA* pricerdata;
4507 
4508  assert(scip != NULL);
4509 
4510  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4511  assert(pricer != NULL);
4512 
4513  pricerdata = pricer->getPricerdata();
4514  assert(pricerdata != NULL);
4515 
4516  /**@todo add constraint statistics: how many constraints (instead of cuts) have been added? */
4517  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file,
4518  "Pricing Solver : #HeurFarkas #OptFarkas #HeurRedcost #OptRedcost Time: HeurFarkas OptFarkas HeurRedcost OptRedcost\n");
4519  for( int i = 0; i < pricerdata->nsolvers; ++i )
4520  {
4521  GCG_SOLVER* solver;
4522  solver = pricerdata->solvers[i];
4523  assert(solver != NULL);
4524 
4525  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " %-17.17s:",
4526  GCGsolverGetName(solver));
4527  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file,
4528  " %11d %11d %11d %11d %10.2f %10.2f %10.2f %10.2f \n",
4531  GCGsolverGetHeurFarkasTime(scip, solver),
4532  GCGsolverGetOptFarkasTime(scip, solver),
4533  GCGsolverGetHeurRedcostTime(scip, solver),
4534  GCGsolverGetOptRedcostTime(scip, solver));
4535  }
4536 }
4537 
4538 /** prints pricer statistics */
4539 extern "C"
4541  SCIP* scip, /**< SCIP data structure */
4542  FILE* file /**< output file */
4543  )
4544 {
4545  ObjPricerGcg* pricer;
4546  SCIP_PRICERDATA* pricerdata;
4547  const PricingType* farkas;
4548  const PricingType* redcost;
4549  int i;
4550 #ifdef SCIP_STATISTIC
4551  double start;
4552  double end;
4553 #endif
4554 
4555  assert(scip != NULL);
4556 
4557  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4558  assert(pricer != NULL);
4559 
4560  pricerdata = pricer->getPricerdata();
4561  assert(pricerdata != NULL);
4562 
4563  /**@todo add constraint statistics: how many constraints (instead of cuts) have been added? */
4564 
4565  /* print of Pricing Statistics */
4566 
4567  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Farkas pricing Statistic:\nno.\t#Calls\t\t#Vars\t\ttime(s)\n");
4568 
4569  for( i = 0; i < pricerdata->npricingprobs; i++ )
4570  {
4571  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "%d \t %d \t\t %d \t\t %.2f \n", i, pricerdata->farkascallsdist[i],
4572  pricerdata->farkasfoundvars[i], pricerdata->farkasnodetimedist[i]);
4573 
4574  }
4575 
4576  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Reduced Cost pricing Statistic:\nno.\t#Calls\t\t#Vars\t\ttime(s)\n");
4577 
4578  for( i = 0; i < pricerdata->npricingprobs; i++ )
4579  {
4580  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "%d \t %d \t\t %d \t\t %.2f \n", i, pricerdata->redcostcallsdist[i],
4581  pricerdata->redcostfoundvars[i], pricerdata->redcostnodetimedist[i]);
4582 
4583  }
4584 
4585 #ifdef SCIP_STATISTIC
4586  /* print of Histogram Buckets !=0 */
4587 
4588  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Histogram Time\n");
4589  for( i = 0; i < PRICER_STAT_ARRAYLEN_TIME; i++ )
4590  {
4591  start = (1.0 * i * PRICER_STAT_BUCKETSIZE_TIME)/1000.0;
4592  end = start + PRICER_STAT_BUCKETSIZE_TIME/1000.0;
4593 
4594  if( pricerdata->nodetimehist[i] != 0 )
4595  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "From\t%.4f\t-\t%.4f\ts:\t\t%d \n", start, end, pricerdata->nodetimehist[i]);
4596  }
4597 
4598  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Histogram Found Vars\n");
4599 
4600  for( i = 0; i < PRICER_STAT_ARRAYLEN_VARS; i++ )
4601  {
4602  start = i * PRICER_STAT_BUCKETSIZE_VARS;
4603  end = start + PRICER_STAT_BUCKETSIZE_VARS;
4604 
4605  if( pricerdata->foundvarshist[i] != 0 )
4606  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "From\t%.0f\t-\t%.0f\tvars:\t\t%d \n", start, end, pricerdata->foundvarshist[i]);
4607  }
4608 
4609  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Root bounds \n");
4610  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " iter pb db time dualdiff dualoptdiff\n");
4611 
4612  for( i = 0; i < pricerdata->nrootbounds; i++ )
4613  {
4614  SCIP_Real pb;
4615  SCIP_Real db;
4616  SCIP_Real time;
4617  SCIP_Real dualdiff;
4618  SCIP_Real dualoptdiff;
4619 
4620  pb = pricerdata->rootpbs[i];
4621  db = pricerdata->rootdbs[i];
4622  time = pricerdata->roottimes[i];
4623  dualdiff = pricerdata->rootdualdiffs[i];
4624  pricer->computeDualDiff(pricerdata->dualvalues[i], pricerdata->dualsolconvs[i], pricerdata->dualvalues[pricerdata->nrootbounds - 1], pricerdata->dualsolconvs[pricerdata->nrootbounds - 1], &dualoptdiff);
4625 
4626  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "%5d %13.6e %13.6e %15.5f %15.5f %15.5f\n", i, pb, db, time, dualdiff, dualoptdiff);
4627  }
4628 #endif
4629 
4630  redcost = pricer->getReducedCostPricing();
4631  assert( redcost != NULL );
4632  farkas = pricer->getFarkasPricing();
4633  assert( farkas != NULL );
4634 
4635  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Pricing Summary:\n");
4636  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Calls : %d\n", pricerdata->calls);
4637  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Farkas Pricing Calls : %d\n", farkas->getCalls());
4638  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Farkas Pricing Time : %f\n", farkas->getClockTime());
4639  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Reduced Cost Pricing Calls : %d\n", redcost->getCalls());
4640  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Reduced Cost Pricing Time : %f\n", redcost->getClockTime());
4641  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Solved subMIPs Heuristic Pricing : %d\n", pricerdata->solvedsubmipsheur);
4642  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Solved subMIPs Optimal Pricing : %d\n", pricerdata->solvedsubmipsoptimal);
4643  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Time for transformation : %f\n", SCIPgetClockTime(scip, pricerdata->transformclock));
4644  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Time for freeing subMIPs : %f\n", SCIPgetClockTime(scip, pricerdata->freeclock));
4645 
4646 }
4647 
4648 /** method to get existence of rays */
4649 extern "C"
4650 SCIP_RETCODE GCGpricerExistRays(
4651  SCIP* scip, /**< master SCIP data structure */
4652  SCIP_Bool* exist /**< pointer to store if there exists any ray */
4653  )
4654 {
4655  int prob;
4656 
4657  ObjPricerGcg* pricer;
4658  SCIP_PRICERDATA* pricerdata;
4659 
4660  assert(scip != NULL);
4661 
4662  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4663  assert(pricer != NULL);
4664 
4665  pricerdata = pricer->getPricerdata();
4666  assert(pricerdata != NULL);
4667 
4668  *exist = FALSE;
4669 
4670  for( prob = 0; prob < pricerdata->npricingprobs; ++prob )
4671  {
4672  if( pricerdata->nraysprob[prob] > 0 )
4673  {
4674  *exist = TRUE;
4675  break;
4676  }
4677  }
4678 
4679  return SCIP_OKAY;
4680 }
4681 
4682 /** get the number of extreme points that a pricing problem has generated so far */
4683 extern "C"
4685  SCIP* scip, /**< master SCIP data structure */
4686  int probnr /**< index of pricing problem */
4687  )
4688 {
4689  ObjPricerGcg* pricer;
4690  SCIP_PRICERDATA* pricerdata;
4691 
4692  assert(scip != NULL);
4693 
4694  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4695  assert(pricer != NULL);
4696 
4697  pricerdata = pricer->getPricerdata();
4698  assert(pricerdata != NULL);
4699 
4700  if( !GCGisPricingprobRelevant(GCGmasterGetOrigprob(scip), probnr) )
4701  return 0;
4702  else
4703  return pricerdata->npointsprob[probnr];
4704 }
4705 
4706 /** get the number of extreme rays that a pricing problem has generated so far */
4707 extern "C"
4709  SCIP* scip, /**< master SCIP data structure */
4710  int probnr /**< index of pricing problem */
4711  )
4712 {
4713  ObjPricerGcg* pricer;
4714  SCIP_PRICERDATA* pricerdata;
4715 
4716  assert(scip != NULL);
4717 
4718  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4719  assert(pricer != NULL);
4720 
4721  pricerdata = pricer->getPricerdata();
4722  assert(pricerdata != NULL);
4723 
4724  if( !GCGisPricingprobRelevant(GCGmasterGetOrigprob(scip), probnr) )
4725  return 0;
4726  else
4727  return pricerdata->nraysprob[probnr];
4728 }
4729 
4730 /** get the number of columns to be added to the master LP in the current pricing round */
4731 extern "C"
4733  SCIP* scip /**< master SCIP data structure */
4734  )
4735 {
4736  ObjPricerGcg* pricer;
4737 
4738  assert(scip != NULL);
4739 
4740  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4741  assert(pricer != NULL);
4742 
4743  return pricer->getMaxColsRound();
4744 }
4745 
4746 /** get the number of columns per pricing problem to be added to the master LP in the current pricing round */
4747 extern "C"
4749  SCIP* scip /**< master SCIP data structure */
4750  )
4751 {
4752  ObjPricerGcg* pricer;
4753 
4754  assert(scip != NULL);
4755 
4756  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4757  assert(pricer != NULL);
4758 
4759  return pricer->getMaxColsProb();
4760 }
4761 
4762 /** add a new column to the pricing storage */
4763 extern "C"
4764 SCIP_RETCODE GCGpricerAddCol(
4765  SCIP* scip, /**< SCIP data structure */
4766  GCG_COL* col /**< priced col */
4767  )
4768 {
4769  ObjPricerGcg* pricer;
4770 
4771  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4772  assert(pricer != NULL);
4773 
4774  SCIP_CALL( pricer->addColToPricestore(col) );
4775 
4776  return SCIP_OKAY;
4777 }
4778 
4779 /** transfers a primal solution of the original problem into the master variable space,
4780  * i.e. creates one master variable for each block and adds the solution to the master problem */
4781 extern "C"
4783  SCIP* scip, /**< SCIP data structure */
4784  SCIP_SOL* origsol, /**< the solution that should be transferred */
4785  SCIP_Bool* stored /**< pointer to store if transferred solution is feasible (or NULL) */
4786  )
4787 {
4788  ObjPricerGcg* pricer;
4789  SCIP_PRICERDATA* pricerdata;
4790  SCIP_SOL* mastersol;
4791  SCIP_VAR* newvar;
4792  SCIP* origprob;
4793  SCIP_Bool added;
4794  int prob;
4795  int i;
4796  int j;
4797 
4798  SCIP_VAR** origvars;
4799  SCIP_Real* origsolvals;
4800  int norigvars;
4801 
4802  SCIP_VAR*** pricingvars;
4803  SCIP_Real** pricingvals;
4804  int* npricingvars;
4805 
4806  assert(scip != NULL);
4807 
4808  origprob = GCGgetOriginalprob(scip);
4809  assert(origprob != NULL);
4810 
4811  /*
4812  * Due to global domain changes, it might happen that the solution is not feasible for the
4813  * transformed original problem anymore; in that case, do not tranfer it to the master
4814  */
4815  SCIP_CALL( SCIPcheckSol(origprob, origsol, FALSE, FALSE, TRUE, TRUE, TRUE, &added) );
4816  if( !added )
4817  {
4818  if( stored != NULL)
4819  *stored = FALSE;
4820  return SCIP_OKAY;
4821  }
4822 
4823  pricerdata = NULL; /* the pricerdata is set to NULL when the Benders' decomposition mode is used. */
4825  {
4826  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
4827  assert(pricer != NULL);
4828 
4829  pricerdata = pricer->getPricerdata();
4830  assert(pricerdata != NULL);
4831  }
4832 
4833  /* now compute coefficients of the master variables in the master constraint */
4834  origvars = SCIPgetVars(origprob);
4835  norigvars = SCIPgetNVars(origprob);
4836 
4837  /* allocate memory for storing variables and solution values from the solution */
4838  SCIP_CALL( SCIPallocBufferArray(scip, &origsolvals, norigvars) ); /*lint !e530*/
4839 
4840  if( pricerdata != NULL )
4841  {
4842  SCIP_CALL( SCIPallocBufferArray(scip, &pricingvars, pricerdata->npricingprobs) ); /*lint !e530*/
4843  SCIP_CALL( SCIPallocBufferArray(scip, &pricingvals, pricerdata->npricingprobs) ); /*lint !e530*/
4844  SCIP_CALL( SCIPallocBufferArray(scip, &npricingvars, pricerdata->npricingprobs) ); /*lint !e530*/
4845 
4846  for( i = 0; i < pricerdata->npricingprobs; i++ )
4847  {
4848  int representative;
4849  representative = GCGgetBlockRepresentative(origprob, i);
4850  npricingvars[i] = 0;
4851 
4852  SCIP_CALL( SCIPallocBufferArray(scip, &(pricingvars[i]), SCIPgetNVars(pricerdata->pricingprobs[representative])) ); /*lint !e866*/
4853  SCIP_CALL( SCIPallocBufferArray(scip, &(pricingvals[i]), SCIPgetNVars(pricerdata->pricingprobs[representative])) ); /*lint !e866*/
4854  }
4855  }
4856 
4857  /* get solution values */
4858  SCIP_CALL( SCIPgetSolVals(scip, origsol, norigvars, origvars, origsolvals) );
4859  SCIP_CALL( SCIPcreateSol(scip, &mastersol, NULL) );
4860 
4861  /* store variables and solutions into arrays */
4862  for( i = 0; i < norigvars; i++ )
4863  {
4864  int blocknr;
4865  assert(GCGvarIsOriginal(origvars[i]));
4866  blocknr = GCGvarGetBlock(origvars[i]);
4867  assert(blocknr < 0 || GCGoriginalVarGetPricingVar(origvars[i]) != NULL);
4868 
4869  if( blocknr >= 0 )
4870  {
4871  if( pricerdata != NULL && !SCIPisZero(scip, origsolvals[i]) )
4872  {
4873  pricingvars[blocknr][npricingvars[blocknr]] = GCGoriginalVarGetPricingVar(origvars[i]);
4874  pricingvals[blocknr][npricingvars[blocknr]] = origsolvals[i];
4875  npricingvars[blocknr]++;
4876  }
4877  }
4878  else
4879  {
4880  SCIP_VAR* mastervar;
4881 
4882  assert((GCGoriginalVarGetNMastervars(origvars[i]) == 1) || (GCGoriginalVarIsLinking(origvars[i])));
4883  assert(GCGoriginalVarGetMastervars(origvars[i])[0] != NULL);
4884 
4885  mastervar = GCGoriginalVarGetMastervars(origvars[i])[0];
4886 
4887  if( SCIPisEQ(scip, SCIPvarGetUbGlobal(mastervar), SCIPvarGetLbGlobal(mastervar)) )
4888  {
4889  SCIP_CALL( SCIPsetSolVal(scip, mastersol, mastervar, SCIPvarGetUbGlobal(mastervar)) );
4890  }
4891  else
4892  {
4893  SCIP_CALL( SCIPsetSolVal(scip, mastersol, mastervar, origsolvals[i]) );
4894  }
4895 
4896  if( GCGoriginalVarIsLinking(origvars[i]) )
4897  {
4898  if( pricerdata != NULL )
4899  {
4900  if( !SCIPisZero(scip, origsolvals[i]) )
4901  {
4902  int* blocks;
4903  int nblocks = GCGlinkingVarGetNBlocks(origvars[i]);
4904  SCIP_CALL( SCIPallocBufferArray(scip, &blocks, nblocks) ); /*lint !e530*/
4905  SCIP_CALL( GCGlinkingVarGetBlocks(origvars[i], nblocks, blocks) );
4906  for ( j = 0; j < nblocks; ++j)
4907  {
4908  prob = blocks[j];
4909 
4910  pricingvars[prob][npricingvars[prob]] = GCGlinkingVarGetPricingVars(origvars[i])[prob];
4911  pricingvals[prob][npricingvars[prob]] = origsolvals[i];
4912  npricingvars[prob]++;
4913  }
4914  SCIPfreeBufferArray(scip, &blocks);
4915 
4916  }
4917  }
4918  else
4919  {
4920  if( SCIPisEQ(scip, SCIPvarGetUbGlobal(mastervar), SCIPvarGetLbGlobal(mastervar)) )
4921  {
4922  SCIP_CALL( SCIPsetSolVal(scip, mastersol, mastervar, SCIPvarGetUbGlobal(mastervar)) );
4923  }
4924  else
4925  {
4926  SCIP_CALL( SCIPsetSolVal(scip, mastersol, mastervar, origsolvals[i]) );
4927  }
4928  }
4929  }
4930  }
4931  }
4932 
4933  /* create variables in the master problem */
4934  if( pricerdata != NULL )
4935  {
4936  for( prob = 0; prob < pricerdata->npricingprobs; prob++ )
4937  {
4938  int representative;
4939 
4940  representative = GCGgetBlockRepresentative(origprob, prob);
4941 
4942  SCIP_CALL( pricer->createNewMasterVar(scip, NULL, NULL, pricingvars[prob], pricingvals[prob], npricingvars[prob], FALSE, representative, TRUE, &added, &newvar) );
4943  assert(added);
4944 
4945  SCIP_CALL( SCIPsetSolVal(scip, mastersol, newvar, 1.0) );
4946  }
4947  }
4948 
4949 #ifdef SCIP_DEBUG
4950  SCIP_CALL( SCIPtrySolFree(scip, &mastersol, TRUE, TRUE, TRUE, TRUE, TRUE, &added) );
4951 #else
4952  SCIP_CALL( SCIPtrySolFree(scip, &mastersol, FALSE, FALSE, TRUE, TRUE, TRUE, &added) );
4953 #endif
4954 
4955  /* set external pointer if it is not NULL */
4956  if( stored != NULL )
4957  *stored = added;
4958 
4959  /* free memory for storing variables and solution values from the solution */
4960  if( pricerdata != NULL )
4961  {
4962  for( i = pricerdata->npricingprobs - 1; i>= 0; i-- )
4963  {
4964  SCIPfreeBufferArray(scip, &(pricingvals[i]));
4965  SCIPfreeBufferArray(scip, &(pricingvars[i]));
4966  }
4967 
4968  SCIPfreeBufferArray(scip, &npricingvars);
4969  SCIPfreeBufferArray(scip, &pricingvals);
4970  SCIPfreeBufferArray(scip, &pricingvars);
4971  }
4972  SCIPfreeBufferArray(scip, &origsolvals);
4973 
4974  return SCIP_OKAY;
4975 }
4976 
4977 
4978 /** create initial master variables */
4979 extern "C"
4981  SCIP* scip /**< master SCIP data structure */
4982  )
4983 {
4984  SCIP* origprob;
4985  int i;
4986  SCIP_VAR** vars;
4987  int nvars;
4988  int npricingprobs;
4989  int v;
4990 
4991  assert(scip != NULL);
4992 
4993  origprob = GCGgetOriginalprob(scip);
4994  assert(origprob != NULL);
4995 
4996  npricingprobs = GCGgetNPricingprobs(origprob);
4997  assert(npricingprobs >= 0);
4998 
4999  /* for variables in the original problem that do not belong to any block,
5000  * create the corresponding variable in the master problem
5001  */
5002  vars = SCIPgetVars(origprob);
5003  nvars = SCIPgetNVars(origprob);
5004  for( v = 0; v < nvars; v++ )
5005  {
5006  SCIP_Real* coefs;
5007  int blocknr;
5008  int ncoefs;
5009  SCIP_VAR* var;
5010 
5011  /* var = SCIPvarGetProbvar(vars[v]); */
5012  var = vars[v];
5013  blocknr = GCGvarGetBlock(var);
5014  coefs = GCGoriginalVarGetCoefs(var);
5015  ncoefs = GCGoriginalVarGetNCoefs(var);
5016 
5017  assert(GCGvarIsOriginal(var));
5018  if( blocknr < 0 )
5019  {
5020  SCIP_CONS** linkconss;
5021  SCIP_VAR* newvar;
5022 
5023  SCIP_CALL( GCGcreateInitialMasterVar(scip, var, &newvar) );
5024  SCIP_CALL( SCIPaddVar(scip, newvar) );
5025 
5026  SCIP_CALL( GCGoriginalVarAddMasterVar(origprob, var, newvar, 1.0) );
5027 
5028  linkconss = GCGoriginalVarGetMasterconss(var);
5029 
5030  /* add variable in the master to the master constraints it belongs to */
5031  for( i = 0; i < ncoefs; i++ )
5032  {
5033  assert(!SCIPisZero(scip, coefs[i]));
5034 
5035  SCIP_CALL( SCIPaddCoefLinear(scip, linkconss[i], newvar, coefs[i]) );
5036  }
5037 
5038  /* we copied a linking variable into the master, add it to the linkcons */
5039  if( GCGoriginalVarIsLinking(var) )
5040  {
5041  SCIP_CONS** linkingconss;
5042  linkingconss = GCGlinkingVarGetLinkingConss(var);
5043 
5044  /* the linking constraints could be NULL if the Benders' decomposition is used. */
5045  if( linkingconss != NULL )
5046  {
5047  for( i = 0; i < npricingprobs; i++ )
5048  {
5049  if( linkingconss[i] != NULL )
5050  {
5051  SCIP_CALL( SCIPaddCoefLinear(scip, linkingconss[i], newvar, 1.0) );
5052  }
5053  }
5054  }
5055  }
5056 
5057  SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
5058  }
5059  }
5060  return SCIP_OKAY;
5061 }
5062 
5063 /** get root node degeneracy */
5064 extern "C"
5066  SCIP* scip /**< SCIP data structure */
5067  )
5068 {
5069  ObjPricerGcg* pricer;
5070  SCIP_PRICERDATA* pricerdata;
5071 
5072  assert(scip != NULL);
5073 
5074  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
5075  assert(pricer != NULL);
5076 
5077  pricerdata = pricer->getPricerdata();
5078  assert(pricerdata != NULL);
5079 
5080  if( SCIPgetStage(scip) >= SCIP_STAGE_INITPRESOLVE && SCIPgetStage(scip) <= SCIP_STAGE_SOLVING && GCGisRootNode(scip) )
5081  {
5082  return pricerdata->avgrootnodedegeneracy;
5083  }
5084  else
5085  return SCIPinfinity(scip);
5086 }
5087 
5088 /** check if current sol is valid */
5089 extern "C"
5091  SCIP* scip /**< SCIP data structure */
5092  )
5093 {
5094  ObjPricerGcg* pricer;
5095  SCIP_PRICERDATA* pricerdata;
5096  SCIP_SOL* sol;
5097  int i;
5098 
5099  assert(scip != NULL);
5100 
5101  /* checking the decomposition mode. If Benders' is used, then the solution is assumed to be valid. */
5103  return TRUE;
5104 
5105  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
5106  assert(pricer != NULL);
5107 
5108  pricerdata = pricer->getPricerdata();
5109  assert(pricerdata != NULL);
5110 
5111  if( pricerdata->nartificialvars == 0 )
5112  return TRUE;
5113 
5114  if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
5115  sol = NULL;
5116  else if( SCIPgetStatus(scip) == SCIP_STATUS_OPTIMAL )
5117  sol = SCIPgetBestSol(scip);
5118  else
5119  return TRUE;
5120 
5121  for( i = 0; i < pricerdata->nartificialvars; ++i )
5122  {
5123  SCIP_Real solval;
5124  solval = SCIPgetSolVal(scip, sol, pricerdata->artificialvars[i]);
5125 
5126  if( SCIPisPositive(scip, solval) )
5127  return FALSE;
5128  }
5129 
5130  return TRUE;
5131 }
5132 
5133 extern "C"
5135  SCIP* scip /**< SCIP data structure */
5136  )
5137 {
5138  ObjPricerGcg* pricer;
5139  SCIP_PRICERDATA* pricerdata;
5140  SCIP_SOL* sol;
5141  int i;
5142 
5143  assert(scip != NULL);
5144 
5145  /* checking the decomposition mode. If Benders' is used, then the solution is assumed to be valid. */
5147  return TRUE;
5148 
5149  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
5150  assert(pricer != NULL);
5151 
5152  pricerdata = pricer->getPricerdata();
5153  assert(pricerdata != NULL);
5154 
5155  sol = SCIPgetBestSol(scip);
5156 
5157  if( sol == NULL )
5158  return TRUE;
5159 
5160  for( i = 0; i < pricerdata->nartificialvars; ++i )
5161  {
5162  SCIP_Real solval;
5163  solval = SCIPgetSolVal(scip, sol, pricerdata->artificialvars[i]);
5164 
5165  if( SCIPisPositive(scip, solval) )
5166  return FALSE;
5167  }
5168 
5169  return TRUE;
5170 }
5171 
5172 extern "C"
5174  SCIP* scip, /**< SCIP data structure */
5175  SCIP_SOL* mastersol /**< solution of the master problem, or NULL for current LP solution */
5176  )
5177 {
5178  ObjPricerGcg* pricer;
5179  SCIP_PRICERDATA* pricerdata;
5180  int i;
5181 
5182  assert(scip != NULL);
5183 
5184  /* checking the decomposition mode. If Benders' is used, then the solution is assumed to be valid. */
5186  return TRUE;
5187 
5188  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
5189  assert(pricer != NULL);
5190 
5191  pricerdata = pricer->getPricerdata();
5192  assert(pricerdata != NULL);
5193 
5194  for( i = 0; i < pricerdata->nartificialvars; ++i )
5195  {
5196  SCIP_Real solval;
5197  solval = SCIPgetSolVal(scip, mastersol, pricerdata->artificialvars[i]);
5198 
5199  if( SCIPisPositive(scip, solval) )
5200  return FALSE;
5201  }
5202 
5203  return TRUE;
5204 }
5205 
5206 
5207 /* get number of iterations in pricing problems */
5208 extern "C"
5210  SCIP* scip /**< SCIP data structure */
5211  )
5212 {
5213  ObjPricerGcg* pricer;
5214  SCIP_PRICERDATA* pricerdata;
5215 
5216  assert(scip != NULL);
5217 
5218  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
5219  assert(pricer != NULL);
5220 
5221  pricerdata = pricer->getPricerdata();
5222  assert(pricerdata != NULL);
5223 
5224  return pricerdata->pricingiters;
5225 }
5226 
5227 /** print simplex iteration statistics */
5228 extern "C"
5230  SCIP* scip, /**< SCIP data structure */
5231  FILE* file /**< output file */
5232  )
5233 {
5234  ObjPricerGcg* pricer;
5235  SCIP_PRICERDATA* pricerdata;
5236 
5237  assert(scip != NULL);
5238 
5239  pricer = static_cast<ObjPricerGcg*>(SCIPfindObjPricer(scip, PRICER_NAME));
5240  assert(pricer != NULL);
5241 
5242  pricerdata = pricer->getPricerdata();
5243  assert(pricerdata != NULL);
5244 
5245  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, "Simplex iterations : iter\n");
5246  if( SCIPgetStage(scip) >= SCIP_STAGE_SOLVING )
5247  {
5248  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " Master LP : %10lld\n", SCIPgetNLPIterations(scip));
5249  }
5250  else
5251  {
5252  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " Master LP : %10lld\n", 0LL);
5253  }
5254  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " Pricing LP : %10lld\n", pricerdata->pricingiters);
5255 
5256  if( SCIPgetStage(pricer->getOrigprob()) >= SCIP_STAGE_SOLVING )
5257  {
5258  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " Original LP : %10lld\n", SCIPgetNLPIterations(pricer->getOrigprob()));
5259  }
5260  else
5261  {
5262  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(scip), file, " Original LP : %10lld\n", 0LL);
5263  }
5264 
5265  return SCIP_OKAY;
5266 }
#define GCGpricerPrintInfo(scip, pricerdata,...)
Definition: pricer_gcg.cpp:127
SCIP_VARTYPE vartype
Definition: pricer_gcg.cpp:188
SCIP_EXPORT SCIP_Real GCGsolverGetHeurRedcostTime(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:524
int GCGgetBlockRepresentative(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4023
enum GCG_Efficiacychoice GCG_EFFICIACYCHOICE
SCIP_Bool abortpricingint
Definition: pricer_gcg.cpp:190
SCIP_CLOCK * freeclock
Definition: pricer_gcg.cpp:173
SCIP_RETCODE GCGsolverCreate(SCIP *scip, GCG_SOLVER **solver, const char *name, const char *desc, int priority, SCIP_Bool heurenabled, SCIP_Bool exactenabled, GCG_DECL_SOLVERUPDATE((*solverupdate)), GCG_DECL_SOLVERSOLVE((*solversolve)), GCG_DECL_SOLVERSOLVEHEUR((*solveheur)), GCG_DECL_SOLVERFREE((*solverfree)), GCG_DECL_SOLVERINIT((*solverinit)), GCG_DECL_SOLVEREXIT((*solverexit)), GCG_DECL_SOLVERINITSOL((*solverinitsol)), GCG_DECL_SOLVEREXITSOL((*solverexitsol)), GCG_SOLVERDATA *solverdata)
Definition: solver.c:59
#define PRICER_NAME
Definition: pricer_gcg.cpp:92
SCIP_RETCODE priceNewVariables(PricingType *pricetype, SCIP_RESULT *result, double *lowerbound)
public methods for GCG pricing solvers
SCIP_Real * dualsolconv
Definition: pricer_gcg.cpp:149
SCIP * GCGgetOriginalprob(SCIP *masterprob)
Definition: relax_gcg.c:3883
int getMaxColsProb() const
Definition: pricer_gcg.cpp:375
public methods for working with pricing problems
SCIP_EVENTHDLR * eventhdlr
Definition: pricer_gcg.cpp:185
#define DEFAULT_USEMAXOBJ
Definition: pricer_gcg.cpp:118
SCIP_Real GCGconsGetRhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:108
#define DEFAULT_USEARTIFICIALVARS
Definition: pricer_gcg.cpp:117
class with functions for dual variable smoothing
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:886
int GCGgetNMasterConss(SCIP *scip)
Definition: relax_gcg.c:4079
#define GCG_DECL_SOLVERSOLVEHEUR(x)
Definition: type_solver.h:133
GCG interface methods.
SCIP_RETCODE pricingLoop(PricingType *pricetype, SCIP_RESULT *result, int *nfoundvars, SCIP_Real *lowerbound, SCIP_Bool *bestredcostvalid)
void GCGpricestoreStartFarkas(GCG_PRICESTORE *pricestore)
SCIP_RETCODE computeDualDiff(SCIP_Real **dualvals1, SCIP_Real *dualconv1, SCIP_Real **dualvals2, SCIP_Real *dualconv2, SCIP_Real *dualdiff)
SCIP_EXPORT int GCGsolverGetHeurRedcostCalls(GCG_SOLVER *solver)
Definition: solver.c:478
SCIP_Bool GCGvarIsMaster(SCIP_VAR *var)
Definition: gcgvar.c:150
SCIP_VAR ** pricedvars
Definition: pricer_gcg.cpp:159
SCIP_Bool GCGcolIsRay(GCG_COL *gcgcol)
Definition: gcgcol.c:351
SCIP_Real maxpricecolsfarkas
Definition: pricer_gcg.cpp:215
SCIP_EXPORT int GCGsolverGetOptFarkasCalls(GCG_SOLVER *solver)
Definition: solver.c:448
int GCGoriginalVarGetNCoefs(SCIP_VAR *var)
Definition: gcgvar.c:641
int GCGpricerGetMaxColsProb(SCIP *scip)
int GCGgetNVarLinkingconss(SCIP *scip)
Definition: relax_gcg.c:5043
void GCGcolUpdateRedcost(GCG_COL *gcgcol, SCIP_Real redcost, SCIP_Bool growold)
Definition: gcgcol.c:375
void GCGpricingprobMarkBranchconsAdded(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:252
int GCGpricingprobGetBranchconsIdx(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:236
SCIP_Bool hybridascent
Definition: pricer_gcg.cpp:203
SCIP_Longint GCGmasterGetPricingSimplexIters(SCIP *scip)
int getCalls() const
int * redcostfoundvars
Definition: pricer_gcg.cpp:225
SCIP_Real GCGconsGetLhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:206
#define EVENTHDLR_NAME
Definition: pricer_gcg.cpp:123
int GCGpricestoreGetNCols(GCG_PRICESTORE *pricestore)
int GCGoriginalVarGetNMastervars(SCIP_VAR *var)
Definition: gcgvar.c:569
SCIP_Real getConvconsDualsol(PricingType *pricetype, int probnr)
Definition: pricer_gcg.cpp:690
#define DEFAULT_ABORTPRICINGINT
Definition: pricer_gcg.cpp:97
SCIP_RETCODE createNewMasterVar(SCIP *scip, PricingType *pricetype, SCIP_SOL *sol, SCIP_VAR **solvars, double *solvals, int nsolvars, unsigned int solisray, int prob, unsigned int force, unsigned int *added, SCIP_VAR **addedvar)
GCG_BRANCHDATA * GCGconsMasterbranchGetBranchdata(SCIP_CONS *cons)
SCIP_VAR ** GCGoriginalVarGetMastervars(SCIP_VAR *var)
Definition: gcgvar.c:587
SCIP_Bool GCGmasterIsSolValid(SCIP *scip, SCIP_SOL *mastersol)
#define DEFAULT_USECOLPOOL
Definition: pricer_gcg.cpp:108
#define eventInitsolVardeleted
Definition: pricer_gcg.cpp:282
int GCGcolGetNMastercuts(GCG_COL *gcgcol)
Definition: gcgcol.c:568
eventhdlr to disable the master display after the root node
#define DEFAULT_BIGMARTIFICIAL
Definition: pricer_gcg.cpp:121
SCIP_RETCODE GCGsolverSolve(SCIP *scip, SCIP *pricingprob, GCG_SOLVER *solver, SCIP_Bool redcost, SCIP_Bool heuristic, int probnr, SCIP_Real dualsolconv, SCIP_Real *lowerbound, GCG_PRICINGSTATUS *status, SCIP_Bool *solved)
Definition: solver.c:280
int GCGbranchGenericBranchdataGetConsSsize(GCG_BRANCHDATA *branchdata)
SCIP_PRICERDATA * getPricerdata()
Definition: objpricer_gcg.h:94
SCIP_Real GCGcolGetSolVal(SCIP *scip, GCG_COL *gcgcol, SCIP_VAR *var)
Definition: gcgcol.c:613
double * farkasnodetimedist
Definition: pricer_gcg.cpp:222
SCIP_RETCODE createPricingcontroller()
SCIP_EXPORT SCIP_Real GCGsolverGetOptFarkasTime(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:488
int * maxrealdualvalues
Definition: pricer_gcg.cpp:169
public methods for working with pricing jobs
SCIP_Real GCGcolGetRedcost(GCG_COL *gcgcol)
Definition: gcgcol.c:359
SCIP_CONS ** GCGgetVarLinkingconss(SCIP *scip)
Definition: relax_gcg.c:5005
SCIP_RETCODE addArtificialVars()
SCIP_DECL_PRICERINITSOL(ObjPricerGcg::scip_initsol)
SCIP_DECL_PRICERINIT(ObjPricerGcg::scip_init)
SCIP_EXPORT SCIP_Real GCGsolverGetHeurFarkasTime(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:512
int GCGcolGetNLinkvars(GCG_COL *gcgcol)
Definition: gcgcol.c:528
SCIP_RETCODE GCGconsMasterbranchAddRootCons(SCIP *scip)
SCIP_HASHMAP * mapcons2idx
Definition: pricer_gcg.cpp:156
GCG_SOLVER * GCGpricingjobGetSolver(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:133
#define DEFAULT_PRICE_REDCOSTFAC
Definition: pricer_gcg.cpp:113
SCIP_VAR ** GCGmasterVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:908
SCIP_RETCODE GCGsolverInit(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:172
SCIP_Real * GCGcolGetMastercoefs(GCG_COL *gcgcol)
Definition: gcgcol.c:393
SCIP_VAR ** artificialvars
Definition: pricer_gcg.cpp:163
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:1033
SCIP_PRICERDATA * pricerdata
Definition: objpricer_gcg.h:61
int GCGlinkingVarGetNBlocks(SCIP_VAR *var)
Definition: gcgvar.c:493
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:490
int GCGpricerGetNPointsProb(SCIP *scip, int probnr)
SCIP_RETCODE GCGmasterSetRootLPSol(SCIP *scip, SCIP_SOL **sol)
SCIP_RETCODE createNewMasterVarFromGcgCol(SCIP *scip, PricingType *pricetype, GCG_COL *gcgcol, SCIP_Bool force, SCIP_Bool *added, SCIP_VAR **addedvar, SCIP_Real score)
SCIP_EXPORT int GCGsolverGetOptRedcostCalls(GCG_SOLVER *solver)
Definition: solver.c:458
void GCGcolpoolEndFarkas(GCG_COLPOOL *colpool)
Definition: colpool.c:489
public methods for working with gcg columns
virtual SCIP_Real rowGetDual(SCIP_ROW *row) const =0
#define DEFAULT_STABILIZATIONTREE
Definition: pricer_gcg.cpp:103
SCIP_Bool GCGvarIsPricing(SCIP_VAR *var)
Definition: gcgvar.c:134
#define DEFAULT_PRICE_MINCOLORTH
Definition: pricer_gcg.cpp:114
SCIP_RETCODE GCGcolpoolUpdateRedcost(GCG_COLPOOL *colpool)
Definition: colpool.c:451
SCIP_Real ** realdualvalues
Definition: pricer_gcg.cpp:168
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3939
SCIP_Real GCGmasterGetDegeneracy(SCIP *scip)
GCG_SOLVER ** GCGpricerGetSolvers(SCIP *scip)
FarkasPricing * getFarkasPricingNonConst()
SCIP_Real bigmartificial
Definition: pricer_gcg.cpp:202
void GCGpricerPrintListOfSolvers(SCIP *scip)
SCIP_RETCODE GCGpricestoreFree(SCIP *scip, GCG_PRICESTORE **pricestore)
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:216
#define eventInitVardeleted
Definition: pricer_gcg.cpp:276
#define DEFAULT_DISPINFOS
Definition: pricer_gcg.cpp:99
SCIP_Bool stabilization
Definition: pricer_gcg.cpp:194
void updateRedcosts(PricingType *pricetype, GCG_COL **cols, int ncols, int *nimpcols)
double avgrootnodedegeneracy
Definition: pricer_gcg.cpp:228
SCIP_Bool GCGcolGetInitializedCoefs(GCG_COL *gcgcol)
Definition: gcgcol.c:512
SCIP_EXPORT int GCGsolverGetHeurFarkasCalls(GCG_SOLVER *solver)
Definition: solver.c:468
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3979
#define PRICER_DESC
Definition: pricer_gcg.cpp:93
SCIP_RETCODE GCGcreateArtificialVar(SCIP *scip, SCIP_VAR **newvar, const char *name, SCIP_Real objcoef)
Definition: gcgvar.c:1522
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:166
GCG variable pricer.
SCIP_Bool newnode
Definition: pricer_gcg.cpp:155
GCG variable pricer.
enum GCG_PricingStatus GCG_PRICINGSTATUS
various SCIP helper methods
SCIP ** pricingprobs
Definition: pricer_gcg.cpp:148
#define EVENTHDLR_DESC
Definition: pricer_gcg.cpp:124
SCIP_Bool artificialused
Definition: pricer_gcg.cpp:166
SCIP_EXPORT int GCGsolverGetPriority(GCG_SOLVER *solver)
Definition: solver.c:418
#define PRICER_STAT_ARRAYLEN_VARS
Definition: pricer_gcg.cpp:137
int GCGsepaGetNCuts(SCIP *scip)
Definition: sepa_master.c:419
SCIP_Real GCGgetPricingprobsMemUsed(SCIP *scip)
Definition: relax_gcg.c:4925
GCG_SOLVER ** solvers
Definition: pricer_gcg.cpp:181
ReducedCostPricing * getReducedCostPricingNonConst()
#define DEFAULT_DISABLECUTOFF
Definition: pricer_gcg.cpp:100
virtual SCIP_Real varGetObj(SCIP_VAR *var) const =0
#define GCG_DECL_SOLVERINITSOL(x)
Definition: type_solver.h:86
SCIP_CONS ** GCGlinkingVarGetLinkingConss(SCIP_VAR *var)
Definition: gcgvar.c:787
double rootnodedegeneracy
Definition: pricer_gcg.cpp:227
GCG_PRICINGPROB * GCGpricingjobGetPricingprob(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:126
SCIP_Real mincolorth
Definition: pricer_gcg.cpp:212
SCIP_Real computeRedCostGcgCol(PricingType *pricetype, GCG_Col *gcgcol, SCIP_Real *objvalptr) const
SCIP_DECL_PRICERREDCOST(ObjPricerGcg::scip_redcost)
GCG_COLPOOL * colpool
Definition: objpricer_gcg.h:62
SCIP_ROW ** GCGsepaGetOrigcuts(SCIP *scip)
Definition: sepa_master.c:400
SCIP_RETCODE computeColMastercuts(GCG_COL *gcgcol)
SCIP_RETCODE computeColMastercoefs(GCG_COL *gcgcol)
#define eventFreeVardeleted
Definition: pricer_gcg.cpp:273
static int threads
Definition: objpricer_gcg.h:64
#define DEFAULT_PRICE_EFFICIACYCHOICE
Definition: pricer_gcg.cpp:115
GCG_PRICESTORE * pricestore
Definition: objpricer_gcg.h:63
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
int * GCGgetVarLinkingconssBlock(SCIP *scip)
Definition: relax_gcg.c:5024
@ GCG_PRICINGSTATUS_NOTAPPLICABLE
#define DEFAULT_COLPOOL_AGELIMIT
Definition: pricer_gcg.cpp:109
void GCGcolpoolStartFarkas(GCG_COLPOOL *colpool)
Definition: colpool.c:481
int maxrealdualvaluescapacity
Definition: pricer_gcg.cpp:170
SCIP_RETCODE GCGpricestoreApplyCols(GCG_PRICESTORE *pricestore, GCG_COLPOOL *colpool, SCIP_Bool usecolpool, int *nfoundvars)
virtual SCIP_RETCODE addParameters()
SCIP_BRANCHRULE * GCGconsMasterbranchGetBranchrule(SCIP_CONS *cons)
#define PRICER_STAT_ARRAYLEN_TIME
Definition: pricer_gcg.cpp:135
ObjPricerGcg(SCIP *scip, SCIP *origscip, const char *name, const char *desc, int priority, unsigned int delay, SCIP_PRICERDATA *pricerdata)
SCIP_Bool GCGoriginalVarIsTransVar(SCIP_VAR *var)
Definition: gcgvar.c:199
SCIP_RETCODE createPricestore()
constraint handler for storing the branching decisions at each node of the tree
int GCGpricerGetNRaysProb(SCIP *scip, int probnr)
#define DEFAULT_HYBRIDASCENT
Definition: pricer_gcg.cpp:104
SCIP_Real orthofac
Definition: pricer_gcg.cpp:211
void GCGsetRootRedcostCall(SCIP_VAR *var, SCIP_Longint rootredcostcall)
Definition: gcgvar.c:1647
int GCGpricerGetMaxColsRound(SCIP *scip)
static SCIP_DECL_EVENTEXEC(eventExecVardeleted)
Definition: pricer_gcg.cpp:292
SCIP_Bool GCGisMaster(SCIP *scip)
Definition: misc.c:675
#define DEFAULT_ONLYRELIABLEBIGM
Definition: pricer_gcg.cpp:119
SCIP_RETCODE GCGsolverExitsol(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:240
master separator
#define GCG_DECL_SOLVEREXIT(x)
Definition: type_solver.h:75
SCIP_RETCODE GCGoriginalVarAddMasterVar(SCIP *scip, SCIP_VAR *origvar, SCIP_VAR *var, SCIP_Real val)
Definition: gcgvar.c:1121
@ GCG_COMPSENSE_GE
virtual SCIP_RETCODE addParameters()
branching rule based on vanderbeck's generic branching scheme
SCIP_RETCODE GCGmasterAddMasterconsToHashmap(SCIP *scip, SCIP_CONS *cons, int pos)
static SCIP_DECL_PARAMCHGD(paramChgdDisablecutoff)
Definition: pricer_gcg.cpp:254
basis separator
public methods for storing cols in a col pool
SCIP_Real * GCGoriginalVarGetCoefs(SCIP_VAR *var)
Definition: gcgvar.c:623
SCIP_RETCODE GCGcreateInitialMasterVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **newvar)
Definition: gcgvar.c:1472
pricing controller managing the pricing strategy
DEC_DECMODE GCGgetMasterDecompMode(SCIP *masterprob)
Definition: relax_gcg.c:5144
SCIP_Bool GCGisOriginal(SCIP *scip)
Definition: misc.c:665
DEC_DECMODE GCGgetDecompositionMode(SCIP *scip)
Definition: relax_gcg.c:5123
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4053
SCIP_Real objparalfac
Definition: pricer_gcg.cpp:210
SCIP_Real * GCGcolGetVals(GCG_COL *gcgcol)
Definition: gcgcol.c:335
SCIP_RETCODE GCGcolSetLinkvars(GCG_COL *gcgcol, int *linkvars, int nlinkvars)
Definition: gcgcol.c:536
SCIP_RETCODE GCGsolverFree(SCIP *scip, GCG_SOLVER **solver)
Definition: solver.c:144
GCG_PRICETYPE getType() const
SCIP_EXPORT SCIP_Bool GCGsolverIsExactEnabled(GCG_SOLVER *solver)
Definition: solver.c:438
SCIP_RETCODE GCGoriginalVarRemoveMasterVar(SCIP *scip, SCIP_VAR *origvar, SCIP_VAR *var)
Definition: gcgvar.c:1168
@ DEC_DECMODE_DANTZIGWOLFE
Definition: type_decomp.h:61
int * redcostcallsdist
Definition: pricer_gcg.cpp:224
SCIP_RETCODE GCGcreateMasterVar(SCIP *scip, SCIP *origscip, SCIP *pricingscip, SCIP_VAR **newvar, const char *varname, SCIP_Real objcoeff, SCIP_VARTYPE vartype, SCIP_Bool solisray, int prob, int nsolvars, SCIP_Real *solvals, SCIP_VAR **solvars, SCIP_Bool auxiliaryvar)
Definition: gcgvar.c:1309
int GCGgetNRelPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3959
@ GCG_PRICETYPE_FARKAS
Definition: pricer_gcg.h:56
SCIP * GCGpricingprobGetPricingscip(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:196
SCIP_RETCODE GCGpricestoreAddCol(SCIP *scip, GCG_PRICESTORE *pricestore, GCG_COL *col, SCIP_Bool forcecol)
SCIP_CONS ** GCGoriginalVarGetMasterconss(SCIP_VAR *var)
Definition: gcgvar.c:710
enum GCG_Pricetype GCG_PRICETYPE
Definition: pricer_gcg.h:59
#define DEFAULT_PRICE_ORTHOFAC
Definition: pricer_gcg.cpp:111
SCIP_Bool GCGmasterIsBestsolValid(SCIP *scip)
#define DEFAULT_STABILIZATION
Definition: pricer_gcg.cpp:102
#define eventExitsolVardeleted
Definition: pricer_gcg.cpp:285
SCIP_RETCODE GCGmasterTransOrigSolToMasterVars(SCIP *scip, SCIP_SOL *origsol, SCIP_Bool *stored)
SCIP_DECL_PRICEREXIT(ObjPricerGcg::scip_exit)
SCIP_Bool usecolpool
Definition: pricer_gcg.cpp:196
SCIP_RETCODE GCGpricerIncludeSolver(SCIP *scip, const char *name, const char *desc, int priority, SCIP_Bool heurenabled, SCIP_Bool exactenabled, GCG_DECL_SOLVERUPDATE((*solverupdate)), GCG_DECL_SOLVERSOLVE((*solversolve)), GCG_DECL_SOLVERSOLVEHEUR((*solversolveheur)), GCG_DECL_SOLVERFREE((*solverfree)), GCG_DECL_SOLVERINIT((*solverinit)), GCG_DECL_SOLVEREXIT((*solverexit)), GCG_DECL_SOLVERINITSOL((*solverinitsol)), GCG_DECL_SOLVEREXITSOL((*solverexitsol)), GCG_SOLVERDATA *solverdata)
SCIP_RETCODE getStabilizedDualObjectiveValue(PricingType *pricetype, SCIP_Real *stabdualval, SCIP_Bool stabilize)
int * GCGcolGetLinkvars(GCG_COL *gcgcol)
Definition: gcgcol.c:520
SCIP * GCGmasterGetOrigprob(SCIP *scip)
SCIP_RETCODE GCGpricerExistRays(SCIP *scip, SCIP_Bool *exist)
GCG_COMPSEQUENCE * GCGbranchGenericBranchdataGetConsS(GCG_BRANCHDATA *branchdata)
@ GCG_PRICETYPE_REDCOST
Definition: pricer_gcg.h:57
SCIP_Bool useartificialvars
Definition: pricer_gcg.cpp:197
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:621
SCIP * GCGcolGetPricingProb(GCG_COL *gcgcol)
Definition: gcgcol.c:319
#define PRICER_STAT_BUCKETSIZE_VARS
Definition: pricer_gcg.cpp:138
SCIP_CONS ** GCGgetOrigMasterConss(SCIP *scip)
Definition: relax_gcg.c:4117
SCIP_Bool GCGisRootNode(SCIP *scip)
Definition: scip_misc.c:921
void GCGpricerPrintPricingStatistics(SCIP *scip, FILE *file)
void GCGpricerPrintStatistics(SCIP *scip, FILE *file)
SCIP_VAR ** GCGcolGetVars(GCG_COL *gcgcol)
Definition: gcgcol.c:327
#define GCG_DECL_SOLVEREXITSOL(x)
Definition: type_solver.h:97
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:434
SCIP_RETCODE GCGcolSetMastercoefs(GCG_COL *gcgcol, SCIP_Real *mastercoefs, int nmastercoefs)
Definition: gcgcol.c:409
#define DEFAULT_FACTORUNRELIABLE
Definition: pricer_gcg.cpp:120
int GCGgetNLinkingvars(SCIP *scip)
Definition: relax_gcg.c:5062
SCIP_DECL_PRICERFREE(ObjPricerGcg::scip_free)
SCIP_Bool dispinfos
Definition: pricer_gcg.cpp:191
virtual void incCalls()
#define GCG_DECL_SOLVERFREE(x)
Definition: type_solver.h:59
SCIP_Real maxpricecols
Definition: pricer_gcg.cpp:214
SCIP_Bool onlyreliablebigm
Definition: pricer_gcg.cpp:200
SCIP_Bool GCGisBranchruleGeneric(SCIP_BRANCHRULE *branchrule)
GCG relaxator.
#define PRICER_DELAY
Definition: pricer_gcg.cpp:95
int GCGmasterGetNPricedvars(SCIP *scip)
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
virtual SCIP_Real consGetDual(SCIP *scip, SCIP_CONS *cons) const =0
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:1015
#define eventDeleteVardeleted
Definition: pricer_gcg.cpp:288
SCIP_RETCODE GCGpricestoreCreate(SCIP *scip, GCG_PRICESTORE **pricestore, SCIP_Real efficiacyfac, SCIP_Real objparalfac, SCIP_Real orthofac, SCIP_Real mincolorth, GCG_EFFICIACYCHOICE efficiacychoice)
#define DEFAULT_ABORTPRICINGGAP
Definition: pricer_gcg.cpp:98
int GCGcolGetNMastercoefs(GCG_COL *gcgcol)
Definition: gcgcol.c:401
int GCGmasterVarGetIndex(SCIP_VAR *var)
Definition: gcgvar.c:1878
virtual SCIP_Real getClockTime() const
#define DEFAULT_PRICE_OBJPARALFAC
Definition: pricer_gcg.cpp:112
GCG_COL ** GCGpricestoreGetCols(GCG_PRICESTORE *pricestore)
const SCIP_EXPORT char * GCGsolverGetName(GCG_SOLVER *solver)
Definition: solver.c:398
SCIP_Real abortpricinggap
Definition: pricer_gcg.cpp:193
SCIP_RETCODE GCGsepaBasisAddPricingCut(SCIP *scip, int ppnumber, SCIP_ROW *cut)
Definition: sepa_basis.c:1759
SCIP_Bool GCGpricingjobIsHeuristic(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:222
#define GCG_DECL_SOLVERINIT(x)
Definition: type_solver.h:67
SCIP_RETCODE GCGsolverUpdate(SCIP *pricingprob, GCG_SOLVER *solver, int probnr, SCIP_Bool varobjschanged, SCIP_Bool varbndschanged, SCIP_Bool consschanged)
Definition: solver.c:257
GCG_EFFICIACYCHOICE efficiacychoice
Definition: pricer_gcg.cpp:216
SCIP_RETCODE GCGsolverInitsol(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:223
SCIP_Bool GCGmasterIsCurrentSolValid(SCIP *scip)
const SCIP_EXPORT char * GCGsolverGetDesc(GCG_SOLVER *solver)
Definition: solver.c:408
SCIP_Longint pricingiters
Definition: pricer_gcg.cpp:178
SCIP_RETCODE GCGcolpoolFree(SCIP *scip, GCG_COLPOOL **colpool)
Definition: colpool.c:195
void GCGpricingprobGetGenericBranchData(GCG_PRICINGPROB *pricingprob, SCIP_CONS ***branchconss, SCIP_Real **branchduals, int *nbranchconss)
Definition: pricingprob.c:212
SCIP * getOrigprob()
SCIP_DECL_PRICERFARKAS(ObjPricerGcg::scip_farkas)
SCIP_RETCODE addColToPricestore(GCG_COL *col)
SCIP_RETCODE GCGmasterCreateInitialMastervars(SCIP *scip)
SCIP * origprob
Definition: objpricer_gcg.h:60
int GCGcolGetNVars(GCG_COL *gcgcol)
Definition: gcgcol.c:343
@ GCG_PRICINGSTATUS_UNKNOWN
SCIP_RETCODE GCGcolpoolUpdateNode(GCG_COLPOOL *colpool)
Definition: colpool.c:429
const ReducedCostPricing * getReducedCostPricing() const
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:182
SCIP_Real GCGcomputeRedCostGcgCol(SCIP *scip, SCIP_Bool infarkas, GCG_COL *gcgcol, SCIP_Real *objvalptr)
abstraction for SCIP pricing types
void GCGupdateVarStatistics(SCIP *scip, SCIP *origprob, SCIP_VAR *newvar, SCIP_Real redcost)
Definition: gcgvar.c:1761
#define PRICER_PRIORITY
Definition: pricer_gcg.cpp:94
int GCGcolGetProbNr(GCG_COL *gcgcol)
Definition: gcgcol.c:311
SCIP_RETCODE GCGpricerAddCol(SCIP *scip, GCG_COL *col)
#define DEFAULT_THREADS
Definition: pricer_gcg.cpp:101
#define DEFAULT_HYBRIDASCENT_NOAGG
Definition: pricer_gcg.cpp:105
void getBestCols(GCG_COL **pricingprobcols)
SCIP_Real * solvals
Definition: pricer_gcg.cpp:150
public methods for GCG variables
#define GCG_DECL_SOLVERUPDATE(x)
Definition: type_solver.h:105
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4000
SCIP_CONS ** GCGgetMasterConss(SCIP *scip)
Definition: relax_gcg.c:4098
const FarkasPricing * getFarkasPricing() const
void GCGpricestoreEndFarkas(GCG_PRICESTORE *pricestore)
SCIP_ROW ** GCGsepaGetMastercuts(SCIP *scip)
Definition: sepa_master.c:438
SCIP_DECL_PRICEREXITSOL(ObjPricerGcg::scip_exitsol)
SCIP_Bool usemaxobj
Definition: pricer_gcg.cpp:199
SCIP_VAR ** GCGlinkingVarGetPricingVars(SCIP_VAR *var)
Definition: gcgvar.c:409
SCIP_RETCODE GCGcreateNewMasterVarFromGcgCol(SCIP *scip, SCIP_Bool infarkas, GCG_COL *gcgcol, SCIP_Bool force, SCIP_Bool *added, SCIP_VAR **addedvar, SCIP_Real score)
int GCGpricestoreGetNEfficaciousCols(GCG_PRICESTORE *pricestore)
int GCGpricerGetNSolvers(SCIP *scip)
SCIP_RETCODE GCGcolpoolPrice(SCIP *scip, GCG_COLPOOL *colpool, GCG_PRICESTORE *pricestore, SCIP_SOL *sol, SCIP_Bool *foundvars)
Definition: colpool.c:352
#define GCG_DECL_SOLVERSOLVE(x)
Definition: type_solver.h:119
double * redcostnodetimedist
Definition: pricer_gcg.cpp:226
SCIP_RETCODE GCGsolverExit(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:206
int GCGgetNTransvars(SCIP *scip)
Definition: relax_gcg.c:5081
SCIP_RETCODE GCGsetPricingObjs(SCIP *scip, SCIP_Real *dualsolconv)
SCIP_RETCODE GCGmasterPrintSimplexIters(SCIP *scip, FILE *file)
SCIP_Real factorunreliable
Definition: pricer_gcg.cpp:201
SCIP_RETCODE SCIPactivateEventHdlrDisplay(SCIP *scip)
Definition: event_display.c:64
SCIP_CONS * GCGgetConvCons(SCIP *scip, int blocknr)
Definition: relax_gcg.c:4136
SCIP_RETCODE GCGcolpoolCreate(SCIP *scip, GCG_COLPOOL **colpool, int agelimit)
Definition: colpool.c:159
SCIP_Real redcostfac
Definition: pricer_gcg.cpp:209
SCIP_Real maxobj
Definition: pricer_gcg.cpp:198
SCIP_Real * GCGcolGetMastercuts(GCG_COL *gcgcol)
Definition: gcgcol.c:560
int getMaxColsRound() const
Definition: pricer_gcg.cpp:367
SCIP_CLOCK * transformclock
Definition: pricer_gcg.cpp:174
SCIP_RETCODE GCGcolUpdateMastercuts(GCG_COL *gcgcol, SCIP_Real *newmastercuts, int nnewmastercuts)
Definition: gcgcol.c:584
SCIP_EXPORT SCIP_Bool GCGsolverIsHeurEnabled(GCG_SOLVER *solver)
Definition: solver.c:428
SCIP_Longint currnodenr
Definition: pricer_gcg.cpp:154
SCIP_RETCODE SCIPincludePricerGcg(SCIP *scip, SCIP *origprob)
SCIP_EXPORT SCIP_Real GCGsolverGetOptRedcostTime(SCIP *scip, GCG_SOLVER *solver)
Definition: solver.c:500
SCIP_Bool hybridascentnoagg
Definition: pricer_gcg.cpp:204
SCIP_RETCODE GCGcomputeColMastercoefs(SCIP *scip, GCG_COL *gcgcol)
SCIP_RETCODE createPricingTypes()
void GCGmasterVarSetIndex(SCIP_VAR *var, int index)
Definition: gcgvar.c:1891
void createStabilization()
int GCGpricingprobGetProbnr(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:204
SCIP_Bool stabilizationtree
Definition: pricer_gcg.cpp:195
SCIP_VAR ** GCGmasterGetPricedvars(SCIP *scip)
SCIP_RETCODE setPricingObjs(PricingType *pricetype, SCIP_Bool stabilize)
Definition: pricer_gcg.cpp:704
int GCGpricingprobGetNImpCols(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:287
SCIP_RETCODE GCGlinkingVarGetBlocks(SCIP_VAR *var, int nblocks, int *blocks)
Definition: gcgvar.c:450
#define PRICER_STAT_BUCKETSIZE_TIME
Definition: pricer_gcg.cpp:136
SCIP_RETCODE createColpool()
SCIP_RETCODE SCIPsepaBasisAddPPObjConss(SCIP *scip, int ppnumber, SCIP_Real dualsolconv, SCIP_Bool newcuts)
Definition: sepa_basis.c:1869
#define eventExitVardeleted
Definition: pricer_gcg.cpp:279
SCIP_RETCODE GCGcolSetInitializedCoefs(GCG_COL *gcgcol)
Definition: gcgcol.c:502
SCIP_Bool GCGpricingprobBranchconsIsAdded(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:244
SCIP_Real getDualconvsum(GCG_COL **bestcols)