Scippy

SCIP

Solving Constraint Integer Programs

stat.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file stat.c
17  * @brief methods for problem statistics
18  * @author Tobias Achterberg
19  * @author Stefan Heinz
20  * @author Gregor Hendel
21  * @author Gerald Gamrath
22  * @author Marc Pfetsch
23  * @author Stefan Vigerske
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <assert.h>
29 
30 #include "scip/def.h"
31 #include "blockmemshell/memory.h"
32 #include "scip/set.h"
33 #include "scip/prob.h"
34 #include "scip/stat.h"
35 #include "scip/clock.h"
36 #include "scip/vbc.h"
37 #include "scip/mem.h"
38 #include "scip/history.h"
39 
40 
41 
42 /** creates problem statistics data */
43 SCIP_RETCODE SCIPstatCreate(
44  SCIP_STAT** stat, /**< pointer to problem statistics data */
45  BMS_BLKMEM* blkmem, /**< block memory */
46  SCIP_SET* set, /**< global SCIP settings */
47  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
48  )
49 {
50  assert(stat != NULL);
51  assert(set != NULL);
52 
53  SCIP_ALLOC( BMSallocMemory(stat) );
54 
55  SCIP_CALL( SCIPclockCreate(&(*stat)->solvingtime, SCIP_CLOCKTYPE_DEFAULT) );
56  SCIP_CALL( SCIPclockCreate(&(*stat)->presolvingtime, SCIP_CLOCKTYPE_DEFAULT) );
57  SCIP_CALL( SCIPclockCreate(&(*stat)->primallptime, SCIP_CLOCKTYPE_DEFAULT) );
58  SCIP_CALL( SCIPclockCreate(&(*stat)->duallptime, SCIP_CLOCKTYPE_DEFAULT) );
59  SCIP_CALL( SCIPclockCreate(&(*stat)->lexduallptime, SCIP_CLOCKTYPE_DEFAULT) );
60  SCIP_CALL( SCIPclockCreate(&(*stat)->barrierlptime, SCIP_CLOCKTYPE_DEFAULT) );
61  SCIP_CALL( SCIPclockCreate(&(*stat)->divinglptime, SCIP_CLOCKTYPE_DEFAULT) );
62  SCIP_CALL( SCIPclockCreate(&(*stat)->strongbranchtime, SCIP_CLOCKTYPE_DEFAULT) );
63  SCIP_CALL( SCIPclockCreate(&(*stat)->conflictlptime, SCIP_CLOCKTYPE_DEFAULT) );
64  SCIP_CALL( SCIPclockCreate(&(*stat)->lpsoltime, SCIP_CLOCKTYPE_DEFAULT) );
65  SCIP_CALL( SCIPclockCreate(&(*stat)->pseudosoltime, SCIP_CLOCKTYPE_DEFAULT) );
66  SCIP_CALL( SCIPclockCreate(&(*stat)->sbsoltime, SCIP_CLOCKTYPE_DEFAULT) );
67  SCIP_CALL( SCIPclockCreate(&(*stat)->nodeactivationtime, SCIP_CLOCKTYPE_DEFAULT) );
68  SCIP_CALL( SCIPclockCreate(&(*stat)->nlpsoltime, SCIP_CLOCKTYPE_DEFAULT) );
69  SCIP_CALL( SCIPclockCreate(&(*stat)->copyclock, SCIP_CLOCKTYPE_DEFAULT) );
70  SCIP_CALL( SCIPclockCreate(&(*stat)->strongpropclock, SCIP_CLOCKTYPE_DEFAULT) );
71 
72  SCIP_CALL( SCIPhistoryCreate(&(*stat)->glbhistory, blkmem) );
73  SCIP_CALL( SCIPhistoryCreate(&(*stat)->glbhistorycrun, blkmem) );
74  SCIP_CALL( SCIPvbcCreate(&(*stat)->vbc, messagehdlr) );
75 
76  (*stat)->status = SCIP_STATUS_UNKNOWN;
77  (*stat)->marked_nvaridx = 0;
78  (*stat)->marked_ncolidx = 0;
79  (*stat)->marked_nrowidx = 0;
80  (*stat)->userinterrupt = FALSE;
81  (*stat)->userrestart = FALSE;
82  (*stat)->inrestart = FALSE;
83  (*stat)->collectvarhistory = TRUE;
84  (*stat)->subscipdepth = 0;
85 
86  SCIPstatReset(*stat, set);
87 
88  return SCIP_OKAY;
89 }
90 
91 /** frees problem statistics data */
92 SCIP_RETCODE SCIPstatFree(
93  SCIP_STAT** stat, /**< pointer to problem statistics data */
94  BMS_BLKMEM* blkmem /**< block memory */
95  )
96 {
97  assert(stat != NULL);
98  assert(*stat != NULL);
99 
100  SCIPclockFree(&(*stat)->solvingtime);
101  SCIPclockFree(&(*stat)->presolvingtime);
102  SCIPclockFree(&(*stat)->primallptime);
103  SCIPclockFree(&(*stat)->duallptime);
104  SCIPclockFree(&(*stat)->lexduallptime);
105  SCIPclockFree(&(*stat)->barrierlptime);
106  SCIPclockFree(&(*stat)->divinglptime);
107  SCIPclockFree(&(*stat)->strongbranchtime);
108  SCIPclockFree(&(*stat)->conflictlptime);
109  SCIPclockFree(&(*stat)->lpsoltime);
110  SCIPclockFree(&(*stat)->pseudosoltime);
111  SCIPclockFree(&(*stat)->sbsoltime);
112  SCIPclockFree(&(*stat)->nodeactivationtime);
113  SCIPclockFree(&(*stat)->nlpsoltime);
114  SCIPclockFree(&(*stat)->copyclock);
115  SCIPclockFree(&(*stat)->strongpropclock);
116 
117  SCIPhistoryFree(&(*stat)->glbhistory, blkmem);
118  SCIPhistoryFree(&(*stat)->glbhistorycrun, blkmem);
119  SCIPvbcFree(&(*stat)->vbc);
120 
121  BMSfreeMemory(stat);
122 
123  return SCIP_OKAY;
124 }
125 
126 /** diables the collection of any statistic for a variable */
127 void SCIPstatDisableVarHistory(
128  SCIP_STAT* stat /**< problem statistics data */
129  )
130 {
131  assert(stat != NULL);
132 
133  stat->collectvarhistory = FALSE;
134 }
135 
136 /** enables the collection of statistics for a variable */
137 void SCIPstatEnableVarHistory(
138  SCIP_STAT* stat /**< problem statistics data */
139  )
140 {
141  assert(stat != NULL);
142 
143  stat->collectvarhistory = TRUE;
144 }
145 
146 /** marks statistics to be able to reset them when solving process is freed */
147 void SCIPstatMark(
148  SCIP_STAT* stat /**< problem statistics data */
149  )
150 {
151  assert(stat != NULL);
152 
153  stat->marked_nvaridx = stat->nvaridx;
154  stat->marked_ncolidx = stat->ncolidx;
155  stat->marked_nrowidx = stat->nrowidx;
156 }
157 
158 /** reset statistics to the data before solving started */
159 void SCIPstatReset(
160  SCIP_STAT* stat, /**< problem statistics data */
161  SCIP_SET* set /**< global SCIP settings */
162  )
163 {
164  assert(stat != NULL);
165  assert(stat->marked_nvaridx >= 0);
166  assert(stat->marked_ncolidx >= 0);
167  assert(stat->marked_nrowidx >= 0);
168 
169  SCIPclockReset(stat->solvingtime);
170  SCIPclockReset(stat->presolvingtime);
171  SCIPclockReset(stat->primallptime);
172  SCIPclockReset(stat->duallptime);
173  SCIPclockReset(stat->lexduallptime);
174  SCIPclockReset(stat->barrierlptime);
175  SCIPclockReset(stat->divinglptime);
176  SCIPclockReset(stat->strongbranchtime);
177  SCIPclockReset(stat->conflictlptime);
178  SCIPclockReset(stat->lpsoltime);
179  SCIPclockReset(stat->pseudosoltime);
180  SCIPclockReset(stat->sbsoltime);
181  SCIPclockReset(stat->nodeactivationtime);
182  SCIPclockReset(stat->nlpsoltime);
183  SCIPclockReset(stat->copyclock);
184  SCIPclockReset(stat->strongpropclock);
185 
186  SCIPhistoryReset(stat->glbhistory);
187 
188  stat->vsidsweight = 1.0;
189  stat->nlpiterations = 0;
190  stat->nrootlpiterations = 0;
191  stat->nrootfirstlpiterations = 0;
192  stat->nprimallpiterations = 0;
193  stat->nduallpiterations = 0;
194  stat->nlexduallpiterations = 0;
195  stat->nbarrierlpiterations = 0;
196  stat->nprimalresolvelpiterations = 0;
197  stat->ndualresolvelpiterations = 0;
198  stat->nlexdualresolvelpiterations = 0;
199  stat->nnodelpiterations = 0;
200  stat->ninitlpiterations = 0;
201  stat->ndivinglpiterations = 0;
202  stat->nsbdivinglpiterations = 0;
203  stat->nsblpiterations = 0;
204  stat->nrootsblpiterations = 0;
205  stat->nconflictlpiterations = 0;
206  stat->ntotalnodes = 0;
207  stat->ntotalinternalnodes = 0;
208  stat->ncreatednodes = 0;
209  stat->nlpsolsfound = 0;
210  stat->npssolsfound = 0;
211  stat->nsbsolsfound = 0;
212  stat->nexternalsolsfound = 0;
213  stat->domchgcount = 0;
214  stat->nboundchgs = 0;
215  stat->nholechgs = 0;
216  stat->nprobboundchgs = 0;
217  stat->nprobholechgs = 0;
218  stat->nsbdowndomchgs = 0;
219  stat->nsbupdomchgs = 0;
220  stat->nruns = 0;
221  stat->nconfrestarts = 0;
222  stat->nrootboundchgs = 0;
223  stat->nrootintfixings = 0;
224  stat->prevrunnvars = 0;
225  stat->nvaridx = stat->marked_nvaridx;
226  stat->ncolidx = stat->marked_ncolidx;
227  stat->nrowidx = stat->marked_nrowidx;
228  stat->lpcount = 0;
229  stat->nlps = 0;
230  stat->nrootlps = 0;
231  stat->nprimallps = 0;
232  stat->nprimalzeroitlps = 0;
233  stat->nduallps = 0;
234  stat->ndualzeroitlps = 0;
235  stat->nlexduallps = 0;
236  stat->nbarrierlps = 0;
237  stat->nbarrierzeroitlps = 0;
238  stat->nprimalresolvelps = 0;
239  stat->ndualresolvelps = 0;
240  stat->nlexdualresolvelps = 0;
241  stat->nnodelps = 0;
242  stat->ninitlps = 0;
243  stat->ndivinglps = 0;
244  stat->nsbdivinglps = 0;
245  stat->nstrongbranchs = 0;
246  stat->nrootstrongbranchs = 0;
247  stat->nconflictlps = 0;
248  stat->nnlps = 0;
249  stat->maxtotaldepth = -1;
250  stat->nactiveconss = 0;
251  stat->nenabledconss = 0;
252  stat->solindex = 0;
253  stat->memsavemode = FALSE;
254  stat->nnodesbeforefirst = -1;
255  stat->ninitconssadded = 0;
256  stat->nrunsbeforefirst = -1;
257  stat->firstprimalheur = NULL;
258  stat->firstprimaltime = SCIP_DEFAULT_INFINITY;
259  stat->firstprimalbound = SCIP_DEFAULT_INFINITY;
260  stat->firstsolgap = SCIP_DEFAULT_INFINITY;
261  stat->lastsolgap = SCIP_DEFAULT_INFINITY;
262  stat->primalzeroittime = 0.0;
263  stat->dualzeroittime = 0.0;
264  stat->barrierzeroittime = 0.0;
265  stat->maxcopytime = SCIP_REAL_MIN;
266  stat->mincopytime = SCIP_REAL_MAX;
267  stat->firstlptime = 0.0;
268  stat->firstlpdualbound = SCIP_UNKNOWN;
269  stat->ncopies = 0;
270  stat->marked_nvaridx = -1;
271  stat->marked_ncolidx = -1;
272  stat->marked_nrowidx = -1;
273 
274  SCIPstatResetImplications(stat);
275  SCIPstatResetPresolving(stat);
276  SCIPstatResetPrimalDualIntegral(stat, set, FALSE);
277 }
278 
279 /** reset implication counter */
280 void SCIPstatResetImplications(
281  SCIP_STAT* stat /**< problem statistics data */
282  )
283 {
284  assert(stat != NULL);
285 
286  stat->nimplications = 0;
287 }
288 
289 /** reset presolving and current run specific statistics */
290 void SCIPstatResetPresolving(
291  SCIP_STAT* stat /**< problem statistics data */
292  )
293 {
294  assert(stat != NULL);
295 
296  stat->npresolrounds = 0;
297  stat->npresolfixedvars = 0;
298  stat->npresolaggrvars = 0;
299  stat->npresolchgvartypes = 0;
300  stat->npresolchgbds = 0;
301  stat->npresoladdholes = 0;
302  stat->npresoldelconss = 0;
303  stat->npresoladdconss = 0;
304  stat->npresolupgdconss = 0;
305  stat->npresolchgcoefs = 0;
306  stat->npresolchgsides = 0;
307 
308  SCIPstatResetCurrentRun(stat);
309 }
310 
311 /** reset primal-dual integral */
312 void SCIPstatResetPrimalDualIntegral(
313  SCIP_STAT* stat, /**< problem statistics data */
314  SCIP_SET* set, /**< global SCIP settings */
315  SCIP_Bool partialreset /**< should time and integral value be kept? (in combination with no statistical
316  * reset, integrals are added for each problem to be solved) */
317  )
318 {
319  assert(stat != NULL);
320 
321  stat->previousgap = 100.0;
322  stat->lastprimalbound = SCIP_UNKNOWN;
323  stat->lastdualbound = SCIP_UNKNOWN;
324  stat->lastlowerbound = -SCIPsetInfinity(set);
325  stat->lastupperbound = SCIPsetInfinity(set);
326 
327  /* partial resets keep the integral value and previous evaluation time */
328  if( !partialreset )
329  {
330  stat->previntegralevaltime = 0.0;
331  stat->primaldualintegral = 0.0;
332  }
333 }
334 
335 /** update the primal-dual integral statistic. method accepts + and - SCIPsetInfinity() as values for
336  * upper and lower bound, respectively
337  */
338 void SCIPstatUpdatePrimalDualIntegral(
339  SCIP_STAT* stat, /**< problem statistics data */
340  SCIP_SET* set, /**< global SCIP settings */
341  SCIP_PROB* transprob, /**< transformed problem */
342  SCIP_PROB* origprob, /**< original problem */
343  SCIP_Real upperbound, /**< current upper bound in transformed problem, or infinity */
344  SCIP_Real lowerbound /**< current lower bound in transformed space, or -infinity */
345  )
346 {
347  SCIP_Real currentgap;
348  SCIP_Real solvingtime;
349  SCIP_Real primalbound;
350  SCIP_Real dualbound;
351 
352  assert(stat != NULL);
353  assert(set != NULL);
354 
355  solvingtime = SCIPclockGetTime(stat->solvingtime);
356  assert(solvingtime >= stat->previntegralevaltime);
357 
358  if( !SCIPsetIsInfinity(set, upperbound) ) /*lint !e777*/
359  {
360  /* get value in original space for gap calculation */
361  primalbound = SCIPprobExternObjval(transprob, origprob, set, upperbound);
362 
363  if( SCIPsetIsZero(set, primalbound) )
364  primalbound = 0.0;
365  }
366  else
367  {
368  /* no new upper bound: use stored values from last update */
369  upperbound = stat->lastupperbound;
370  primalbound = stat->lastprimalbound;
371  assert(SCIPsetIsZero(set, primalbound) == (primalbound == 0.0)); /*lint !e777*/
372  }
373 
374  if( !SCIPsetIsInfinity(set, -lowerbound) ) /*lint !e777*/
375  {
376  /* get value in original space for gap calculation */
377  dualbound = SCIPprobExternObjval(transprob, origprob, set, lowerbound);
378 
379  if( SCIPsetIsZero(set, dualbound) )
380  dualbound = 0.0;
381  }
382  else
383  {
384  /* no new lower bound: use stored values from last update */
385  lowerbound = stat->lastlowerbound;
386  dualbound = stat->lastdualbound;
387  assert(SCIPsetIsZero(set, dualbound) == (dualbound == 0.0)); /*lint !e777*/
388  }
389 
390  /* computation of the gap, special cases are handled first */
391  if( primalbound == SCIP_UNKNOWN || dualbound == SCIP_UNKNOWN ) /*lint !e777*/
392  currentgap = 100.0;
393  /* the gap is 0.0 if bounds coincide */
394  else if( SCIPsetIsGE(set, lowerbound, upperbound) || SCIPsetIsEQ(set, primalbound, dualbound) )
395  currentgap = 0.0;
396  /* the gap is 100.0 if bounds have different signs */
397  else if( primalbound * dualbound <= 0.0 ) /*lint !e777*/
398  currentgap = 100.0;
399  else if( !SCIPsetIsInfinity(set, REALABS(primalbound)) && !SCIPsetIsInfinity(set, REALABS(dualbound)) )
400  {
401  SCIP_Real absprim = REALABS(primalbound);
402  SCIP_Real absdual = REALABS(dualbound);
403 
404  /* The gap in the definition of the primal-dual integral differs from the default SCIP gap function.
405  * Here, the MAX(primalbound, dualbound) is taken for gap quotient in order to ensure a gap <= 100.
406  */
407  currentgap = 100.0 * REALABS(primalbound - dualbound) / MAX(absprim, absdual);
408  assert(SCIPsetIsLE(set, currentgap, 100.0));
409  }
410  else
411  currentgap = 100.0;
412 
413  /* if primal and dual bound have opposite signs, the gap always evaluates to 100.0% */
414  assert(currentgap == 0.0 || currentgap == 100.0 || SCIPsetIsGE(set, primalbound * dualbound, 0.0));
415  assert(SCIPsetIsGE(set, stat->previousgap, currentgap) || (set->stage == SCIP_STAGE_EXITPRESOLVE
416  && SCIPsetIsFeasGE(set, stat->previousgap, currentgap)));
417 
418  /* update the integral based on previous information */
419  stat->primaldualintegral += (solvingtime - stat->previntegralevaltime) * stat->previousgap;
420 
421  /* update all relevant information for next evaluation */
422  stat->previousgap = currentgap;
423  stat->previntegralevaltime = solvingtime;
424  stat->lastprimalbound = primalbound;
425  stat->lastdualbound = dualbound;
426  stat->lastlowerbound = lowerbound;
427  stat->lastupperbound = upperbound;
428 }
429 
430 /** reset current branch and bound run specific statistics */
431 void SCIPstatResetCurrentRun(
432  SCIP_STAT* stat /**< problem statistics data */
433  )
434 {
435  assert(stat != NULL);
436 
437  stat->nnodes = 0;
438  stat->ninternalnodes = 0;
439  stat->ncreatednodesrun = 0;
440  stat->nactivatednodes = 0;
441  stat->ndeactivatednodes = 0;
442  stat->nbacktracks = 0;
443  stat->ndelayedcutoffs = 0;
444  stat->nreprops = 0;
445  stat->nrepropboundchgs = 0;
446  stat->nrepropcutoffs = 0;
447  stat->lastdivenode = 0;
448  stat->lastconflictnode = 0;
449  stat->bestsolnode = 0;
450  stat->rootlowerbound = SCIP_REAL_MIN;
451  stat->lastbranchvalue = SCIP_UNKNOWN;
452  stat->lastbranchvar = NULL;
453  stat->status = SCIP_STATUS_UNKNOWN;
454  stat->lastbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
455  stat->nrootboundchgsrun = 0;
456  stat->nrootintfixingsrun = 0;
457  stat->npricerounds = 0;
458  stat->nseparounds = 0;
459  stat->maxdepth = -1;
460  stat->plungedepth = 0;
461 
462  SCIPhistoryReset(stat->glbhistorycrun);
463 
464  SCIPstatResetDisplay(stat);
465 }
466 
467 /** resets display statistics, such that a new header line is displayed before the next display line */
468 void SCIPstatResetDisplay(
469  SCIP_STAT* stat /**< problem statistics data */
470  )
471 {
472  assert(stat != NULL);
473 
474  stat->lastdispnode = 0;
475  stat->ndisplines = 0;
476 }
477 
478 /** increases LP count, such that all lazy updates depending on the LP are enforced again */
479 void SCIPstatEnforceLPUpdates(
480  SCIP_STAT* stat /**< problem statistics data */
481  )
482 {
483  assert(stat != NULL);
484 
485  stat->lpcount++;
486 }
487 
488 /** depending on the current memory usage, switches mode flag to standard or memory saving mode */
489 void SCIPstatUpdateMemsaveMode(
490  SCIP_STAT* stat, /**< problem statistics data */
491  SCIP_SET* set, /**< global SCIP settings */
492  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
493  SCIP_MEM* mem /**< block memory pools */
494  )
495 {
496  assert(stat != NULL);
497  assert(set != NULL);
498 
499  if( SCIPsetIsLT(set, set->mem_savefac, 1.0) )
500  {
501  SCIP_Longint memused;
502 
503  memused = SCIPmemGetUsed(mem);
504  if( !stat->memsavemode && memused >= set->mem_savefac * set->limit_memory * 1024.0 * 1024.0 )
505  {
506  /* switch to memory saving mode */
507  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
508  "(node %"SCIP_LONGINT_FORMAT") switching to memory saving mode (mem: %.1fM/%.1fM)\n",
509  stat->nnodes, (SCIP_Real)memused/(1024.0*1024.0), set->limit_memory);
510  stat->memsavemode = TRUE;
511  set->nodesel = NULL;
512  }
513  else if( stat->memsavemode && memused < 0.5 * set->mem_savefac * set->limit_memory * 1024.0 * 1024.0 )
514  {
515  /* switch to standard mode */
516  SCIPmessagePrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_HIGH,
517  "(node %"SCIP_LONGINT_FORMAT") switching to standard mode (mem: %.1fM/%.1fM)\n",
518  stat->nnodes, (SCIP_Real)memused/(1024.0*1024.0), set->limit_memory);
519  stat->memsavemode = FALSE;
520  set->nodesel = NULL;
521  }
522  }
523  else
524  stat->memsavemode = FALSE;
525 }
526