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