class_pricingcontroller.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 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
36 #include "pricer_gcg.h"
37 #include "class_pricingtype.h"
38 #include "gcg.h"
39 #include "scip_misc.h"
40 #include "branch_generic.h"
41 #include "cons_masterbranch.h"
42 #include "pub_gcgpqueue.h"
43 #include "pub_pricingjob.h"
44 #include "pub_pricingprob.h"
45 #include "pub_solver.h"
46 #include "pricingjob.h"
47 #include "pricingprob.h"
48 
49 #include "scip/scip.h"
50 #include "objscip/objscip.h"
51 
52 #include <exception>
53 
54 #define DEFAULT_HEURPRICINGITERS 1
55 #define DEFAULT_MAXHEURDEPTH -1
56 #define DEFAULT_SORTING 'r'
62 #define DEFAULT_NROUNDSCOL 15
63 #define DEFAULT_CHUNKSIZE INT_MAX
64 #define DEFAULT_EAGERFREQ 10
66 #define SCIP_CALL_EXC(x) do \
67  { \
68  SCIP_RETCODE _retcode_; \
69  if( (_retcode_ = (x)) != SCIP_OKAY ) \
70  { \
71  SCIPerrorMessage("Error <%d> in function call\n", _retcode_); \
72  throw std::exception(); \
73  } \
74  } \
75  while( FALSE )
76 
77 
78 namespace gcg {
79 
81  SCIP* scip
82  )
83 {
84  scip_ = scip;
85  pricingprobs = NULL;
86  npricingprobs = 0;
87  pricingjobs = NULL;
88  npricingjobs = 0;
89 
90  sorting = DEFAULT_SORTING;
91  nroundscol = DEFAULT_NROUNDSCOL;
92  chunksize = DEFAULT_CHUNKSIZE;
93  eagerfreq = DEFAULT_EAGERFREQ;
94 
95  pqueue = NULL;
96  maxniters = INT_MAX;
97  nchunks = 1;
98  curchunk = 0;
99 
100  pricingtype_ = NULL;
101 
102  eagerage = 0;
103  nsolvedprobs = 0;
104 }
105 
107 {
108 }
109 
111 {
112  SCIP* origprob = GCGmasterGetOrigprob(scip_);
113 
114  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/heurpricingiters",
115  "maximum number of heuristic pricing iterations per pricing call and problem",
116  &heurpricingiters, FALSE, DEFAULT_HEURPRICINGITERS, 0, INT_MAX, NULL, NULL) );
117 
118  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/maxheurdepth",
119  "maximum depth at which heuristic pricing should be performed (-1 for infinity)",
120  &maxheurdepth, FALSE, DEFAULT_MAXHEURDEPTH, -1, INT_MAX, NULL, NULL) );
121 
122  SCIP_CALL( SCIPaddCharParam(origprob, "pricing/masterpricer/sorting",
123  "order by which the pricing problems should be sorted ('i'ndices, 'd'ual solutions of convexity constraints, 'r'eliability from previous rounds, reliability from the 'l'ast nroundscol rounds)",
124  &sorting, FALSE, DEFAULT_SORTING, "dilr", NULL, NULL) );
125 
126  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/nroundscol",
127  "number of previous pricing rounds for which the number of improving columns should be counted",
128  &nroundscol, TRUE, DEFAULT_NROUNDSCOL, 1, INT_MAX, NULL, NULL) );
129 
130  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/chunksize",
131  "maximal number of pricing problems to be solved during one pricing loop",
132  &chunksize, TRUE, DEFAULT_CHUNKSIZE, 1, INT_MAX, NULL, NULL) );
133 
134  SCIP_CALL( SCIPaddIntParam(origprob, "pricing/masterpricer/eagerfreq",
135  "frequency at which all pricingproblems should be solved (0 to disable)",
136  &eagerfreq, FALSE, DEFAULT_EAGERFREQ, 0, INT_MAX, NULL, NULL) );
137 
138  return SCIP_OKAY;
139 }
140 
142 SCIP_DECL_SORTPTRCOMP(Pricingcontroller::comparePricingjobs)
143 {
144  GCG_PRICINGJOB* pricingjob1;
145  GCG_PRICINGJOB* pricingjob2;
146  GCG_PRICINGPROB* pricingprob1;
147  GCG_PRICINGPROB* pricingprob2;
148  GCG_SOLVER* solver1;
149  GCG_SOLVER* solver2;
150 
151  pricingjob1 = (GCG_PRICINGJOB*) elem1;
152  pricingjob2 = (GCG_PRICINGJOB*) elem2;
153 
154  pricingprob1 = GCGpricingjobGetPricingprob(pricingjob1);
155  pricingprob2 = GCGpricingjobGetPricingprob(pricingjob2);
156 
157  solver1 = GCGpricingjobGetSolver(pricingjob1);
158  solver2 = GCGpricingjobGetSolver(pricingjob2);
159 
166  if( GCGsolverGetPriority(solver1) > GCGsolverGetPriority(solver2) )
167  return -1;
168  else if( GCGsolverGetPriority(solver1) < GCGsolverGetPriority(solver2) )
169  return 1;
170 
171  if( GCGpricingjobIsHeuristic(pricingjob1) && GCGpricingjobIsHeuristic(pricingjob2) )
172  {
173  if( GCGpricingjobGetNHeurIters(pricingjob1) < GCGpricingjobGetNHeurIters(pricingjob2) )
174  return -1;
175  else if( GCGpricingjobGetNHeurIters(pricingjob1) > GCGpricingjobGetNHeurIters(pricingjob2) )
176  return 1;
177  }
178 
179  if( GCGpricingjobIsHeuristic(pricingjob1) != GCGpricingjobIsHeuristic(pricingjob2) )
180  {
181  if( GCGpricingjobIsHeuristic(pricingjob1) )
182  return -1;
183  else if( GCGpricingjobIsHeuristic(pricingjob2) )
184  return 1;
185  }
186 
187  if( GCGpricingjobGetScore(pricingjob1) > GCGpricingjobGetScore(pricingjob2) )
188  return -1;
189  else if( GCGpricingjobGetScore(pricingjob1) < GCGpricingjobGetScore(pricingjob2) )
190  return 1;
191 
192  // @todo: preliminary tie breaking by pricing problem index
193  if( GCGpricingprobGetProbnr(pricingprob1) < GCGpricingprobGetProbnr(pricingprob2) )
194  return -1;
195  else
196  return 1;
197 
198  return 0;
199 }
200 
202 SCIP_RETCODE Pricingcontroller::getGenericBranchconss()
203 {
204  /* get current branching rule */
205  SCIP_CONS* branchcons = GCGconsMasterbranchGetActiveCons(scip_);
206  SCIP_BRANCHRULE* branchrule = GCGconsMasterbranchGetBranchrule(branchcons);
207 
208  assert(branchcons != NULL);
209  assert(SCIPnodeGetDepth(GCGconsMasterbranchGetNode(branchcons)) == 0 || branchrule != NULL);
210 
211  while( GCGisBranchruleGeneric(branchrule) )
212  {
213  GCG_BRANCHDATA* branchdata;
214  SCIP_CONS* mastercons;
215  int consblocknr;
216 
217  int i;
218 
219  branchdata = GCGconsMasterbranchGetBranchdata(branchcons);
220  assert(branchdata != NULL);
221 
222  mastercons = GCGbranchGenericBranchdataGetMastercons(branchdata);
223  consblocknr = GCGbranchGenericBranchdataGetConsblocknr(branchdata);
224  assert(mastercons != NULL);
225  assert(consblocknr >= 0);
226 
227  for( i = 0; i < npricingprobs; ++i )
228  {
229  /* search for the pricing problem to which the generic branching decision belongs */
230  if( consblocknr == GCGpricingprobGetProbnr(pricingprobs[i]) )
231  {
232  SCIP_CALL( GCGpricingprobAddGenericBranchData(scip_, pricingprobs[i], branchcons, pricingtype_->consGetDual(scip_, mastercons)) );
233  break;
234  }
235  }
236  assert(i < npricingprobs);
237 
238  branchcons = GCGconsMasterbranchGetParentcons(branchcons);
239  branchrule = GCGconsMasterbranchGetBranchrule(branchcons);
240  }
241 
242  return SCIP_OKAY;
243 }
244 
246 SCIP_Bool Pricingcontroller::pricingprobIsDone(
247  GCG_PRICINGPROB* pricingprob
248  ) const
249 {
250  return GCGpricingprobGetNImpCols(pricingprob) > 0
254 }
255 
257 SCIP_Bool Pricingcontroller::pricingprobNeedsNextBranchingcons(
258  GCG_PRICINGPROB* pricingprob
259  ) const
260 {
261  return GCGpricingprobGetNImpCols(pricingprob) == 0
263  && GCGpricingprobGetBranchconsIdx(pricingprob) > 0;
264 }
265 
266 SCIP_RETCODE Pricingcontroller::initSol()
267 {
268  SCIP* origprob = GCGmasterGetOrigprob(scip_);
269  int nblocks = GCGgetNPricingprobs(origprob);
270  GCG_SOLVER** solvers = GCGpricerGetSolvers(scip_);
271  int nsolvers = GCGpricerGetNSolvers(scip_);
272  int actchunksize = MIN(chunksize, GCGgetNRelPricingprobs(origprob));
273 
274  npricingprobs = 0;
275  npricingjobs = 0;
276  nchunks = (int) SCIPceil(scip_, (SCIP_Real) GCGgetNRelPricingprobs(origprob) / actchunksize);
277  curchunk = nchunks - 1;
278  eagerage = 0;
279 
280  /* create pricing problem and pricing job data structures */
281  SCIP_CALL_EXC( SCIPallocMemoryArray(scip_, &pricingprobs, GCGgetNRelPricingprobs(origprob)) );
282  SCIP_CALL_EXC( SCIPallocMemoryArray(scip_, &pricingjobs, GCGgetNRelPricingprobs(origprob) * nsolvers) );
283  for( int i = 0; i < nblocks; ++i )
284  {
285  if( GCGisPricingprobRelevant(origprob, i) )
286  {
287  SCIP_CALL_EXC( GCGpricingprobCreate(scip_, &pricingprobs[npricingprobs], GCGgetPricingprob(origprob, i), i, nroundscol) );
288 
289  for( int j = 0; j < nsolvers; ++j )
290  {
291  if( GCGsolverIsEnabled(solvers[j]) )
292  {
293  SCIP_CALL_EXC( GCGpricingjobCreate(scip_, &pricingjobs[npricingjobs], pricingprobs[npricingprobs], solvers[j], npricingprobs / actchunksize) );
294  ++npricingjobs;
295  }
296  }
297  ++npricingprobs;
298  }
299  }
300 
301  SCIP_CALL_EXC( GCGpqueueCreate(&pqueue, npricingjobs, 2.0, comparePricingjobs) );
302 
303  return SCIP_OKAY;
304 }
305 
306 SCIP_RETCODE Pricingcontroller::exitSol()
307 {
308  GCGpqueueFree(&pqueue);
309 
310  for( int i = 0; i < npricingprobs; ++i )
311  {
312  GCGpricingprobFree(scip_, &pricingprobs[i]);
313  }
314  for( int i = 0; i < npricingjobs; ++i )
315  {
316  GCGpricingjobFree(scip_, &pricingjobs[i]);
317  }
318  SCIPfreeMemoryArray(scip_, &pricingprobs);
319  SCIPfreeMemoryArray(scip_, &pricingjobs);
320 
321  return SCIP_OKAY;
322 }
323 
325 SCIP_RETCODE Pricingcontroller::initPricing(
326  PricingType* pricingtype
327  )
328 {
329  SCIP_Longint tmpmaxniters;
331  pricingtype_ = pricingtype;
332 
333  /* move chunk index forward */
334  curchunk = (curchunk + 1) % nchunks;
335  startchunk = curchunk;
336 
337  for( int i = 0; i < npricingprobs; ++i )
338  GCGpricingprobInitPricing(pricingprobs[i]);
339 
340  SCIP_CALL( getGenericBranchconss() );
341 
342  /* calculate maximal possible number of pricing iterations per mis-pricing iteration */
343  tmpmaxniters = 0;
344  for( int i = 0; i < npricingprobs; ++i )
345  tmpmaxniters += GCGpricerGetNSolvers(scip_) * ((SCIP_Longint) heurpricingiters + 1) * (GCGpricingprobGetNGenericBranchconss(pricingprobs[i]) + 1);
346  maxniters = (int) MIN(tmpmaxniters, 16383);
347 
348  SCIPdebugMessage("initialize pricing, chunk = %d/%d\n", curchunk+1, nchunks);
349 
350  return SCIP_OKAY;
351 }
352 
355 {
356  for( int i = npricingprobs-1; i >= 0; --i )
357  GCGpricingprobExitPricing(pricingprobs[i], nroundscol);
358 
359  pricingtype_ = NULL;
360 }
361 
364  SCIP_Real* dualsolconv
365  )
366 {
367  SCIPdebugMessage("Setup pricing queue, chunk = %d/%d\n", curchunk+1, nchunks);
369  GCGpqueueClear(pqueue);
370 
371  /* reset pricing problems */
372  for( int i = 0; i < npricingprobs; ++i )
373  GCGpricingprobReset(scip_, pricingprobs[i]);
374 
375  for( int i = 0; i < npricingjobs; ++i )
376  {
377  int probnr = GCGpricingprobGetProbnr(GCGpricingjobGetPricingprob(pricingjobs[i]));
378 
379  SCIP_CALL_EXC( GCGpricingjobSetup(pricingjobs[i],
380  (heurpricingiters > 0 && (maxheurdepth == -1 || SCIPnodeGetDepth(SCIPgetCurrentNode(scip_)) <= maxheurdepth)),
381  sorting, nroundscol, dualsolconv[probnr], GCGpricerGetNPointsProb(scip_, probnr), GCGpricerGetNRaysProb(scip_, probnr)) );
382 
383  if( GCGpricingjobGetChunk(pricingjobs[i]) == curchunk )
384  {
385  SCIP_CALL_EXC( GCGpqueueInsert(pqueue, (void*) pricingjobs[i]) );
386  }
387  }
388 
389  nsolvedprobs = 0;
390 
391  return SCIP_OKAY;
392 }
393 
396 {
397  GCG_PRICINGJOB* pricingjob = NULL;
398 
399  do
400  {
401  pricingjob = (GCG_PRICINGJOB*) GCGpqueueRemove(pqueue);
402  }
403  while( pricingjob != NULL && pricingprobIsDone(GCGpricingjobGetPricingprob(pricingjob)) );
404 
405  return pricingjob;
406 }
407 
412  GCG_PRICINGPROB* pricingprob
413  )
414 {
415  int i;
417  GCGpricingprobNextBranchcons(pricingprob);
418 
419  /* reset heuristic pricing counter and flag for every corresponding pricing job */
420  if( heurpricingiters > 0 )
421  for( i = 0; i < npricingjobs; ++i )
422  if( GCGpricingjobGetPricingprob(pricingjobs[i]) == pricingprob )
423  GCGpricingjobResetHeuristic(pricingjobs[i]);
424 
425  /* re-sort the priority queue */
426  SCIP_CALL( GCGpqueueResort(pqueue) );
427 
428  return SCIP_OKAY;
429 }
430 
433  GCG_PRICINGJOB* pricingjob
434  )
435 {
436  SCIP* pricingscip = GCGpricingprobGetPricingscip(GCGpricingjobGetPricingprob(pricingjob));
437  SCIP_Real mastertimelimit;
438  SCIP_Real timelimit;
439 
440  SCIP_CALL( SCIPgetRealParam(scip_, "limits/time", &mastertimelimit) );
441 
442  /* do not give pricing job more time than is left for solving the master problem */
443  timelimit = MAX(0, mastertimelimit - SCIPgetSolvingTime(scip_));
444 
445  SCIP_CALL( SCIPsetRealParam(pricingscip, "limits/time", timelimit) );
446 
447  return SCIP_OKAY;
448 }
449 
452  GCG_PRICINGPROB* pricingprob,
453  GCG_PRICINGSTATUS status,
454  SCIP_Real lowerbound,
455  int nimpcols
456  )
457 {
458  GCGpricingprobUpdate(scip_, pricingprob, status, lowerbound, nimpcols);
459 }
460 
463  GCG_PRICINGJOB* pricingjob,
464  GCG_PRICINGSTATUS status
465  )
466 {
467  GCG_PRICINGPROB* pricingprob = GCGpricingjobGetPricingprob(pricingjob);
468  SCIP_Bool heuristic = GCGpricingjobIsHeuristic(pricingjob);
469 
470  /* Go to the next heuristic pricing iteration */
471  if( heuristic )
473 
474  /* If the solver was not appliable to the pricing problem, leave and do not add the job to the queue again */
475  if( status == GCG_PRICINGSTATUS_NOTAPPLICABLE )
476  return;
477 
478  /* If the pricing job has not yielded any improving column, possibly solve it again;
479  * increase at least one of its limits, or solve it exactly if it was solved heuristically before
480  */
481  // @todo: update score of pricing job
482  if( !pricingprobIsDone(pricingprob) )
483  {
484  SCIPdebugMessage("Solving problem %d with <%s> has not yielded improving columns.\n",
486 
487  if( heuristic && status != GCG_PRICINGSTATUS_OPTIMAL )
488  {
489  assert(status == GCG_PRICINGSTATUS_UNKNOWN || status == GCG_PRICINGSTATUS_SOLVERLIMIT);
490 
491  if( status != GCG_PRICINGSTATUS_SOLVERLIMIT || GCGpricingjobGetNHeurIters(pricingjob) >= heurpricingiters )
492  {
493  GCGpricingjobSetExact(pricingjob);
494  SCIPdebugMessage(" -> set exact\n");
495  }
496  else
497  {
498  SCIPdebugMessage(" -> increase a limit\n");
499  }
500  SCIP_CALL_EXC( GCGpqueueInsert(pqueue, (void*) pricingjob) );
501 
502  return;
503  }
504 
505  if( pricingprobNeedsNextBranchingcons(pricingprob) )
506  {
507 
508  SCIPdebugMessage(" -> consider next generic branching constraint.\n");
509 
511 
512  SCIP_CALL_EXC( GCGpqueueInsert(pqueue, (void*) pricingjob) );
513 
514  return;
515  }
516  }
517  else
518  ++nsolvedprobs;
519 }
520 
523  GCG_COL** bestcols,
524  SCIP_Bool* infeasible,
525  SCIP_Bool* optimal,
526  SCIP_Real* bestobjvals,
527  SCIP_Real* beststabobj,
528  SCIP_Real* bestredcost,
529  SCIP_Bool* bestredcostvalid
530  )
531 {
532  SCIP* origprob = GCGmasterGetOrigprob(scip_);
533  int nblocks = GCGgetNPricingprobs(origprob);
534  SCIP_Bool foundcols = FALSE;
535 
536  /* initializations */
537  *infeasible = FALSE;
538  *optimal = TRUE;
539  *beststabobj = 0.0;
540  *bestredcost = 0.0;
541  for( int i = 0; i < nblocks; ++i )
542  bestobjvals[i] = -SCIPinfinity(scip_);
543 
544  for( int i = 0; i < npricingprobs; ++i )
545  {
546  int probnr = GCGpricingprobGetProbnr(pricingprobs[i]);
547  int nidentblocks = GCGgetNIdenticalBlocks(origprob, probnr);
548  SCIP_Real lowerbound = GCGpricingprobGetLowerbound(pricingprobs[i]);
549 
550  /* check infeasibility */
551  *infeasible |= GCGpricingprobGetStatus(pricingprobs[i]) == GCG_PRICINGSTATUS_INFEASIBLE;
552 
553  /* check optimality */
554  *optimal &= GCGpricingprobGetStatus(pricingprobs[i]) == GCG_PRICINGSTATUS_OPTIMAL;
555 
556  if( GCGpricingprobGetNImpCols(pricingprobs[i]) > 0 )
557  foundcols = TRUE;
558 
559  /* update lower bound information */
560  bestobjvals[probnr] = SCIPisInfinity(scip_, ABS(lowerbound)) ? lowerbound : nidentblocks * lowerbound;
561  if( SCIPisInfinity(scip_, -lowerbound) )
562  *beststabobj = -SCIPinfinity(scip_);
563  else if( !SCIPisInfinity(scip_, -(*beststabobj)) )
564  *beststabobj += bestobjvals[probnr];
565 
566  if( bestcols[probnr] != NULL )
567  *bestredcost += GCGcolGetRedcost(bestcols[probnr]) * nidentblocks;
568  }
569 
570  *infeasible |= (pricingtype_->getType() == GCG_PRICETYPE_FARKAS && *optimal && !foundcols);
571  *bestredcostvalid &= foundcols || *optimal;
572 }
573 
576 {
577  int nextchunk = (curchunk + 1) % nchunks;
578 
579  if( nextchunk == startchunk )
580  {
581  SCIPdebugMessage("not considering next chunk.\n");
582  return FALSE;
583  }
584  else
585  {
586  SCIPdebugMessage("need considering next chunk = %d/%d\n", nextchunk+1, nchunks);
587  curchunk = nextchunk;
588  return TRUE;
589  }
590 }
591 
594  PricingType* pricingtype,
595  int nfoundcols,
596  int nsuccessfulprobs
597  ) const
598 {
599  int nrelpricingprobs = GCGgetNRelPricingprobs(GCGmasterGetOrigprob(scip_));
600 
601  if( eagerage == eagerfreq )
602  return FALSE;
603 
604  return !((nfoundcols < pricingtype->getMaxcolsround())
605  && nsuccessfulprobs < pricingtype->getMaxsuccessfulprobs()
606  && nsuccessfulprobs < pricingtype->getRelmaxsuccessfulprobs() * nrelpricingprobs
607  && (nfoundcols == 0 || nsolvedprobs < pricingtype->getRelmaxprobs() * nrelpricingprobs));
608 }
609 
611 {
612  eagerage = 0;
613 }
614 
616 {
617  if( eagerfreq > 0 )
618  eagerage++;
619 }
623  int probnr
624  )
625 {
626  for( int i = 0; i < npricingprobs; ++i )
627  if( GCGpricingprobGetProbnr(pricingprobs[i]) == probnr )
628  return pricingprobs[i];
629 
630  return NULL;
631 }
632 
635 {
636  return maxniters;
637 }
638 
639 } /* namespace gcg */
void * GCGpqueueRemove(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:192
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3918
void evaluatePricingjob(GCG_PRICINGJOB *pricingjob, GCG_PRICINGSTATUS status)
struct GCG_PricingJob GCG_PRICINGJOB
SCIP_Real GCGpricingjobGetChunk(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:136
SCIP_RETCODE setPricingjobTimelimit(GCG_PRICINGJOB *pricingjob)
#define DEFAULT_SORTING
struct GCG_Solver GCG_SOLVER
Definition: type_solver.h:50
SCIP_BRANCHRULE * GCGconsMasterbranchGetBranchrule(SCIP_CONS *cons)
SCIP_Bool canPricingloopBeAborted(PricingType *pricingtype, int nfoundcols, int nsuccessfulprobs) const
SCIP_RETCODE GCGpricingprobCreate(SCIP *scip, GCG_PRICINGPROB **pricingprob, SCIP *pricingscip, int probnr, int nroundscol)
Definition: pricingprob.c:51
abstraction for SCIP pricing types
int GCGpricingprobGetProbnr(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:203
SCIP_RETCODE GCGpricingprobAddGenericBranchData(SCIP *scip, GCG_PRICINGPROB *pricingprob, SCIP_CONS *branchcons, SCIP_Real branchdual)
Definition: pricingprob.c:121
GCG interface methods.
int GCGpricingprobGetBranchconsIdx(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:235
EXTERN SCIP_Bool GCGsolverIsEnabled(GCG_SOLVER *solver)
Definition: solver.c:404
SCIP_RETCODE GCGpqueueCreate(GCG_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)))
Definition: gcgpqueue.c:116
int GCGpricingjobGetNHeurIters(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:186
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3857
int GCGpricingprobGetNGenericBranchconss(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:227
SCIP_Real GCGpricingprobGetLowerbound(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:278
void GCGpricingprobFree(SCIP *scip, GCG_PRICINGPROB **pricingprob)
Definition: pricingprob.c:81
void updatePricingprob(GCG_PRICINGPROB *pricingprob, GCG_PRICINGSTATUS status, SCIP_Real lowerbound, int nimpcols)
void GCGpricingprobReset(SCIP *scip, GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:159
SCIP_Real GCGpricingjobGetScore(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:144
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
EXTERN int GCGsolverGetPriority(GCG_SOLVER *solver)
Definition: solver.c:394
void GCGpqueueClear(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:152
SCIP_RETCODE GCGpricingjobSetup(GCG_PRICINGJOB *pricingjob, SCIP_Bool heuristic, int scoring, int nroundscol, SCIP_Real dualsolconv, int npointsprob, int nraysprob)
Definition: pricingjob.c:80
SCIP_Bool GCGpricingjobIsHeuristic(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:152
void GCGpricingjobFree(SCIP *scip, GCG_PRICINGJOB **pricingjob)
Definition: pricingjob.c:70
enum GCG_PricingStatus GCG_PRICINGSTATUS
SCIP_RETCODE GCGpqueueResort(GCG_PQUEUE *pqueue)
Definition: gcgpqueue.c:233
SCIP_Real GCGcolGetRedcost(GCG_COL *gcgcol)
Definition: gcgcol.c:356
void GCGpricingprobInitPricing(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:94
SCIP_RETCODE GCGpqueueInsert(GCG_PQUEUE *pqueue, void *elem)
Definition: gcgpqueue.c:162
void GCGpricingjobIncreaseNHeurIters(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:177
SCIP_CONS * GCGconsMasterbranchGetParentcons(SCIP_CONS *cons)
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3897
SCIP_CONS * GCGbranchGenericBranchdataGetMastercons(GCG_BRANCHDATA *branchdata)
private methods for working with pricing jobs, to be used by the pricing controller only ...
SCIP_Bool GCGisBranchruleGeneric(SCIP_BRANCHRULE *branchrule)
private methods for working with pricing problems, to be used by the pricing controller only ...
int GCGgetNRelPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3877
void GCGpricingprobExitPricing(GCG_PRICINGPROB *pricingprob, int nroundscol)
Definition: pricingprob.c:106
#define DEFAULT_HEURPRICINGITERS
struct GCG_Col GCG_COL
Definition: type_gcgcol.h:45
int GCGpricerGetNRaysProb(SCIP *scip, int probnr)
EXTERN const char * GCGsolverGetName(GCG_SOLVER *solver)
Definition: solver.c:374
int GCGbranchGenericBranchdataGetConsblocknr(GCG_BRANCHDATA *branchdata)
various SCIP helper methods
#define DEFAULT_NROUNDSCOL
SCIP * GCGpricingprobGetPricingscip(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:195
void GCGpricingprobUpdate(SCIP *scip, GCG_PRICINGPROB *pricingprob, GCG_PRICINGSTATUS status, SCIP_Real lowerbound, int nimpcols)
Definition: pricingprob.c:173
virtual int getMaxcolsround() const =0
#define DEFAULT_CHUNKSIZE
GCG variable pricer.
GCG_PRICINGJOB * getNextPricingjob()
GCG_SOLVER ** GCGpricerGetSolvers(SCIP *scip)
SCIP_RETCODE initPricing(PricingType *pricingtype)
virtual SCIP_Real getRelmaxprobs() const =0
GCG_PRICINGSTATUS GCGpricingprobGetStatus(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:270
GCG_PRICETYPE getType() const
void GCGpricingjobSetExact(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:160
SCIP_RETCODE GCGpricingjobCreate(SCIP *scip, GCG_PRICINGJOB **pricingjob, GCG_PRICINGPROB *pricingprob, GCG_SOLVER *solver, int chunk)
Definition: pricingjob.c:49
SCIP_RETCODE pricingprobNextBranchcons(GCG_PRICINGPROB *pricingprob)
#define SCIP_CALL_EXC(x)
SCIP * GCGmasterGetOrigprob(SCIP *scip)
void collectResults(GCG_COL **bestcols, SCIP_Bool *infeasible, SCIP_Bool *optimal, SCIP_Real *bestobjvals, SCIP_Real *beststabobj, SCIP_Real *bestredcost, SCIP_Bool *bestredcostvalid)
GCG_PRICINGPROB * getPricingprob(int probnr)
int GCGpricerGetNSolvers(SCIP *scip)
GCG_SOLVER * GCGpricingjobGetSolver(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:128
void GCGpqueueFree(GCG_PQUEUE **pqueue)
Definition: gcgpqueue.c:141
SCIP_NODE * GCGconsMasterbranchGetNode(SCIP_CONS *cons)
int GCGpricingprobGetNImpCols(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:286
branching rule based on vanderbeck&#39;s generic branching scheme
void GCGpricingjobResetHeuristic(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:168
constraint handler for storing the branching decisions at each node of the tree
public methods for working with pricing jobs
GCG_BRANCHDATA * GCGconsMasterbranchGetBranchdata(SCIP_CONS *cons)
#define DEFAULT_EAGERFREQ
public methods for working with pricing problems
struct GCG_PricingProb GCG_PRICINGPROB
SCIP_Real getRelmaxsuccessfulprobs() const
int GCGpricerGetNPointsProb(SCIP *scip, int probnr)
GCG_PRICINGPROB * GCGpricingjobGetPricingprob(GCG_PRICINGJOB *pricingjob)
Definition: pricingjob.c:121
pricing controller managing the pricing strategy
virtual SCIP_Real consGetDual(SCIP *scip, SCIP_CONS *cons) const =0
SCIP_RETCODE setupPriorityQueue(SCIP_Real *dualsolconv)
#define DEFAULT_MAXHEURDEPTH
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3966
void GCGpricingprobNextBranchcons(GCG_PRICINGPROB *pricingprob)
Definition: pricingprob.c:259