misc.c
Go to the documentation of this file.
36/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
68 * a critical value represents a threshold for rejecting the null-hypothesis in hypothesis testing at
99/**< critical values for higher degrees of freedom of Student-T distribution for the same error probabilities; infact,
109/** get critical value of a Student-T distribution for a given number of degrees of freedom at a confidence level */
121/** compute a t-value for the hypothesis that x and y are from the same population; Assuming that
194/** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
226 /* scale and translate to standard normal distribution. Factor sqrt(2) is needed for SCIPerf() function */
229 SCIPdebugMessage(" Normalized value %g = ( %g - %g ) / (%g * 1.4142136)\n", normvalue, value, mean, std);
231 /* calculate the cumulative distribution function for normvalue. For negative normvalues, we negate the normvalue and
302 /* if there is no variance in the y's (but in the x's), the regression line is horizontal with y-intercept through the mean y */
314 regression->slope = (regression->sumxy - regression->nobservations * regression->meanx * regression->meany) / regression->variancesumx;
320 regression->corrcoef = (regression->sumxy - regression->nobservations * regression->meanx * regression->meany) /
347 /* it may happen that *sumvarptr is slightly negative, especially after a series of add/removal operations */
362 /* simply call the reset function in the case of a single remaining observation to avoid numerical troubles */
373 incrementalStatsUpdate(x, ®ression->meanx, ®ression->variancesumx, regression->nobservations, add);
374 incrementalStatsUpdate(y, ®ression->meany, ®ression->variancesumy, regression->nobservations, add);
395 incrementalStatsUpdate(x, ®ression->meanx, ®ression->variancesumx, regression->nobservations, add);
396 incrementalStatsUpdate(y, ®ression->meany, ®ression->variancesumy, regression->nobservations, add);
463 /* calculate the size with this loop, such that the resulting numbers are always the same (-> block memory) */
488 * For a detailed format decription see http://docs.yworks.com/yfiles/doc/developers-guide/gml.html
736 fprintf(file, "\t%d [shape=\"%s\", label=\"%s\", style=\"filled\", fillcolor=\"%s\", color=\"%s\"];\n", node, nodetype, label, fillcolor, bordercolor);
870/** constructs the first solution of sparse solution (all variables are set to their lower bound value */
893/** constructs the next solution of the sparse solution and return whether there was one more or not */
994/** creates a (circular) queue, best used if the size will be fixed or will not be increased that much */
1057 BMSmoveMemoryArray(&(queue->slots[queue->firstused + sizediff]), &(queue->slots[queue->firstused]), oldsize - queue->firstused); /*lint !e866*/
1155 /* if we reached the first free position we can reset both, firstused and firstused, positions */
1159 queue->firstfree = 0; /* this is not necessary but looks better if we have an empty list to reset this value */
1165/** removes and returns the first unsigned integer element of the queue, or UINT_MAX if no element exists */
1189 /* if we reached the first free position we can reset both, firstused and firstused, positions */
1193 queue->firstfree = 0; /* this is not necessary but looks better if we have an empty list to reset this value */
1217/** returns the first unsigned integer element of the queue without removing it, or UINT_MAX if no element exists */
1302 SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)) /**< callback to act on position change of elem in priority queue, or NULL */
1387 if( rightchild < SCIPpqueueNElems(pqueue) && pqueue->ptrcomp(pqueue->slots[i], pqueue->slots[rightchild]) > 0)
1410 /* insert element as leaf in the tree, move it towards the root as long it is better than its parent */
1446 /* remove element at specified position of the tree, move the better child to its parents position until the last element
1457 /* last element is brought to pos. it may now violate the heap property compared to its parent, or to its children.
1472 if( brotherpos < pqueue->len && (*pqueue->ptrcomp)(pqueue->slots[brotherpos], pqueue->slots[childpos]) < 0 )
1539/** returns the elements of the queue; changing the returned array may destroy the queue's ordering! */
1638/** returns a reasonable hash table size (a prime number) that is at least as large as the specified value */
1697/** finds multihash list entry pointing to element with given key in the multihash list, returns NULL if not found */
1764 SCIPerrorMessage("WARNING: hashkey with same value exists multiple times (e.g. duplicate constraint/variable names), so the return value is maybe not correct\n");
1781 SCIP_MULTIHASHLIST** multihashlist, /**< on input: hash list to search; on exit: hash list entry corresponding
1796 h = multihashlistFind(*multihashlist, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
1864 nnewlists = (int) MIN((unsigned int)(multihash->nlists * SCIP_MULTIHASH_GROW_FACTOR), SCIP_MULTIHASH_MAXSIZE);
1867 SCIPdebugMessage("load = %g, nelements = %" SCIP_LONGINT_FORMAT ", nlists = %d, nnewlist = %d\n", SCIPmultihashGetLoad(multihash), multihash->nelements, multihash->nlists, nnewlists);
1892 /* if the old hash table list consists of only one entry, we still can use this old memory block instead
1920 SCIP_CALL( multihashlistAppend(&(newlists[hashval]), multihash->blkmem, multihashlist->element) );
2023 * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding an element
2062/** inserts element in multihash table (multiple insertion of same element is checked and results in an error)
2064 * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding a new
2076 if( SCIPmultihashRetrieve(multihash, multihash->hashgetkey(multihash->userptr, element)) != NULL )
2106 return multihashlistRetrieve(multihash->lists[hashval], multihash->hashgetkey, multihash->hashkeyeq,
2113 * @note The returned multimultihashlist pointer might get invalid when adding a new element to the multihash table.
2117 SCIP_MULTIHASHLIST** multihashlist, /**< input: entry in hash table list from which to start searching, or NULL
2173 return (multihashlistFind(multihash->lists[hashval], multihash->hashgetkey, multihash->hashkeyeq,
2209 * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
2210 * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
2289 SCIPmessagePrintInfo(messagehdlr, "%" SCIP_LONGINT_FORMAT " multihash entries, used %d/%d slots (%.1f%%)",
2290 multihash->nelements, usedslots, multihash->nlists, 100.0*(SCIP_Real)usedslots/(SCIP_Real)(multihash->nlists));
2371 uint32_t probelen = ((i + table->mask + 1 - (table->hashes[i]>>(table->shift))) & table->mask) + 1;
2394#define ELEM_DISTANCE(pos) (((pos) + hashtable->mask + 1 - (hashtable->hashes[(pos)]>>(hashtable->shift))) & hashtable->mask)
2403 SCIP_Bool override /**< should element be overridden or an error be returned if already existing */
2460 /* if this is the case we insert the new element here and find a new position for the old one */
2520 SCIP_CALL_ABORT( hashtableInsert(hashtable, slots[i], hashtable->hashgetkey(hashtable->userptr, slots[i]), hashes[i], FALSE) );
2632 /* element cannot be contained since otherwise we would have swapped it with this one during insert */
2661 return (SCIPhashtableRetrieve(hashtable, hashtable->hashgetkey(hashtable->userptr, element)) != NULL);
2886#define ELEM_DISTANCE(pos) (((pos) + hashmap->mask + 1 - (hashmap->hashes[(pos)]>>(hashmap->shift))) & hashmap->mask)
2895 SCIP_Bool override /**< should element be overridden or error be returned if already existing */
2944 /* if this is the case we insert the new element here and find a new position for the old one */
2961/** lookup origin in the hashmap. If element is found returns true and the position of the element,
2995 /* element can not be contained since otherwise we would have swapped it with this one during insert */
3117 uint32_t probelen = ((i + (*hashmap)->mask + 1 - ((*hashmap)->hashes[i]>>((*hashmap)->shift))) & (*hashmap)->mask) + 1;
3124 (unsigned int)(*hashmap)->nelements, (unsigned int)(*hashmap)->nelements, (unsigned int)nslots,
3156 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
3192 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3228 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_LONG);
3264 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3295 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
3315 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3323/** retrieves image of given origin from the hash map, or SCIP_LONGINT_MAX if no image exists */
3335 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_LONG);
3355 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3363/** sets image for given origin in the hash map, either by modifying existing origin->image pair
3378 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
3397/** sets image for given origin in the hash map, either by modifying existing origin->image pair
3412 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3431/** sets image for given origin in the hash map, either by modifying existing origin->image pair
3446 assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3697#define ELEM_DISTANCE(pos) (((pos) + nslots - hashSetDesiredPos(hashset, hashset->slots[(pos)])) & mask)
3748 /* if this is the case we insert the new element here and find a new position for the old one */
3891 /* element can not be contained since otherwise we would have swapped it with this one during insert */
3933 /* element can not be contained since otherwise we would have swapped it with this one during insert */
4050/** gives the array of hash set slots; contains all elements in indetermined order and may contain NULL values */
4124 BMSfreeBlockMemoryArrayNull((*realarray)->blkmem, &(*realarray)->vals, (*realarray)->valssize);
4148 assert(realarray->maxusedidx == INT_MIN || realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4157 SCIPdebugMessage("extending realarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4158 (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, minidx, maxidx);
4236 for( i = realarray->maxusedidx - realarray->firstidx; i >= realarray->minusedidx - realarray->firstidx; --i )
4267 for( i = realarray->minusedidx - realarray->firstidx; i <= realarray->maxusedidx - realarray->firstidx; ++i )
4293 (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx);
4349 SCIPdebugMessage("setting realarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %g\n",
4350 (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, idx, val);
4477 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*intarray)->vals, sourceintarray->vals, sourceintarray->valssize) );
4519 assert(intarray->maxusedidx == INT_MIN || intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4528 SCIPdebugMessage("extending intarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4529 (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, minidx, maxidx);
4607 for( i = intarray->maxusedidx - intarray->firstidx; i >= intarray->minusedidx - intarray->firstidx; --i )
4638 for( i = intarray->minusedidx - intarray->firstidx; i <= intarray->maxusedidx - intarray->firstidx; ++i )
4664 (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx);
4721 (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, idx, val);
4785 return SCIPintarraySetVal(intarray, arraygrowinit, arraygrowfac, idx, SCIPintarrayGetVal(intarray, idx) + incval);
4861 BMSfreeBlockMemoryArrayNull((*boolarray)->blkmem, &(*boolarray)->vals, (*boolarray)->valssize);
4885 assert(boolarray->maxusedidx == INT_MIN || boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4894 SCIPdebugMessage("extending boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4895 (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, minidx, maxidx);
4973 for( i = boolarray->maxusedidx - boolarray->firstidx; i >= boolarray->minusedidx - boolarray->firstidx; --i )
5032 (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx);
5088 SCIPdebugMessage("setting boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %u\n",
5089 (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, idx, val);
5198 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*ptrarray)->vals, sourceptrarray->vals, sourceptrarray->valssize) );
5240 assert(ptrarray->maxusedidx == INT_MIN || ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5249 SCIPdebugMessage("extending ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
5250 (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, minidx, maxidx);
5328 for( i = ptrarray->maxusedidx - ptrarray->firstidx; i >= ptrarray->minusedidx - ptrarray->firstidx; --i )
5359 for( i = ptrarray->minusedidx - ptrarray->firstidx; i <= ptrarray->maxusedidx - ptrarray->firstidx; ++i )
5385 (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx);
5442 (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, idx, val);
5580/** sort an indexed element set in non-decreasing order, resulting in a permutation index array */
5600/* SCIPsortInd(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5607/* SCIPsortPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5614/* SCIPsortPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5622/* SCIPsortPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5630/* SCIPsortPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5638/* SCIPsortPtrBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5646/* SCIPsortPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5655/* SCIPsortPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5663/* SCIPsortPtrRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5672/* SCIPsortPtrRealRealBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5682/* SCIPsortPtrRealRealIntBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5692/* SCIPsortPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5701/* SCIPsortPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5710/* SCIPsortPtrPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5719/* SCIPsortPtrRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5729/* SCIPsortPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5739/* SCIPsortPtrPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5749/* SCIPsortPtrPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5759/* SCIPsortPtrPtrLongInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5769/* SCIPsortPtrPtrLongIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5780/* SCIPsortReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5786/* SCIPsortRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5794/* SCIPsortRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5801/* SCIPsortRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5808/* SCIPsortRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5816/* SCIPsortRealIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5824/* SCIPsortRealIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5832/* SCIPsortRealPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5840/* SCIPsortRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5848/* SCIPsortRealLongRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5856/* SCIPsortRealRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5865/* SCIPsortRealRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5874/* SCIPsortRealRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5883/* SCIPsortRealPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5892/* SCIPsortRealPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5902/* SCIPsortRealRealRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5912/* SCIPsortRealRealRealBoolBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5923/* SCIPsortInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5929/* SCIPsortIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5936/* SCIPsortIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5943/* SCIPsortIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5950/* SCIPsortIntIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5958/* SCIPsortIntIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5965/* SCIPsortIntRealLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5973/* SCIPsortIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5981/* SCIPsortIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5989/* SCIPsortIntPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5997/* SCIPsortIntIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6005/* SCIPsortIntIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6013/* SCIPsortIntPtrIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6021/* SCIPsortIntIntPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6029/* SCIPsortIntIntPtrPtrInterval(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6038/* SCIPsortLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6044/* SCIPsortLongPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6051/* SCIPsortLongPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6059/* SCIPsortLongPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6068/* SCIPsortLongPtrRealRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6078/* SCIPsortLongPtrRealRealIntBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6089/* SCIPsortLongPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6098/* SCIPsortLongPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6108/* SCIPsortLongPtrPtrBoolInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6118/* SCIPsortPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6129/* SCIPsortIntPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6143/** sort an indexed element set in non-increasing order, resulting in a permutation index array */
6164/* SCIPsortDownInd(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6172/* SCIPsortDownPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6180/* SCIPsortDownPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6189/* SCIPsortDownPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6198/* SCIPsortDownPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6206/* SCIPsortDownPtrBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6214/* SCIPsortDownPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6224/* SCIPsortDownPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6234/* SCIPsortDownPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6244/* SCIPsortDownPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6254/* SCIPsortDownPtrPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6264/* SCIPsortDownPtrRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6275/* SCIPsortDownPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6286/* SCIPsortDownPtrPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6297/* SCIPsortDownPtrPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6308/* SCIPsortDownPtrPtrLongInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6319/* SCIPsortDownPtrPtrLongIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6331/* SCIPsortDownReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6338/* SCIPsortDownRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6347/* SCIPsortDownRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6355/* SCIPsortDownRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6362/* SCIPsortDownRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6370/* SCIPsortDownRealIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6379/* SCIPsortDownRealIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6388/* SCIPsortDownRealPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6396/* SCIPsortDownRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6404/* SCIPsortDownRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6412/* SCIPsortDownRealRealPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6422/* SCIPsortDownRealLongRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6432/* SCIPsortDownRealRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6442/* SCIPsortDownRealRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6452/* SCIPsortDownRealRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6462/* SCIPsortDownRealPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6471/* SCIPsortDownRealPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6482/* SCIPsortDownRealRealRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6493/* SCIPsortDownRealRealRealBoolBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6504/* SCIPsortDownInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6511/* SCIPsortDownIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6519/* SCIPsortDownIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6528/* SCIPsortDownIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6536/* SCIPsortDownIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6544/* SCIPsortDownIntIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6553/* SCIPsortDownIntIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6562/* SCIPsortDownIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6571/* SCIPsortDownIntIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6581/* SCIPsortDownIntIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6591/* SCIPsortDownIntPtrIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6601/* SCIPsortDownLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6608/* SCIPsortDownLongPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6616/* SCIPsortDownLongPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6625/* SCIPsortDownLongPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6635/* SCIPsortDownLongPtrRealRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6646/* SCIPsortLongPtrRealRealIntBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6658/* SCIPsortDownLongPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6668/* SCIPsortDownLongPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6679/* SCIPsortDownLongPtrPtrBoolInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6690/* SCIPsortDownPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6702/* SCIPsortDownIntPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6870 SCIPmessageFPrintInfo(messagehdlr, file, "Profile <%p> (capacity %d) --> ", (void*)profile, profile->capacity);
6875 SCIPmessageFPrintInfo(messagehdlr, file, "%d:(%d,%d)", t, profile->timepoints[t], profile->loads[t]);
6877 SCIPmessageFPrintInfo(messagehdlr, file, ", %d:(%d,%d)", t, profile->timepoints[t], profile->loads[t]);
6947/** returns if the given time point exists in the resource profile and stores the position of the given time point if it
6992/** inserts the given time point into the resource profile if it this time point does not exists yet; returns its
7006 /* get the position of the given time point in the resource profile array if it exists; otherwise the position of the
7019 SCIPsortedvecInsertIntInt(profile->timepoints, profile->loads, timepoint, profile->loads[*pos],
7094/** insert a core into resource profile; if the core is non-empty the resource profile will be updated otherwise nothing
7140 /* check if the left and right time points of the core correspond to a time point in the resource profile; this
7157/** returns TRUE if the core (given by its demand and during) can be inserted at the given time point; otherwise FALSE */
7192 SCIPdebugMessage("profile <%p>: core does not fit at time point %d (pos %d)\n", (void*)profile, profile->timepoints[pos], pos);
7214/** return the earliest possible starting point within the time interval [lb,ub] for a given core (given by its demand
7238 SCIPdebugMessage("profile <%p>: find earliest start time (demad %d, duration %d) [%d,%d]\n", (void*)profile, demand, duration, est, lst);
7247 SCIPdebugMessage("profile <%p>: earliest start time does %s exist as time point (pos %d)\n", (void*)profile, found ? "" : "not", pos);
7249 /* if the position is the last time point in the profile, the core can be inserted at its earliest start time */
7267 /* if the the time point left to the start time has not enough free capacity we can just search the profile
7291 pos = profileFindFeasibleStart(profile, pos+1, profile->timepoints[pos+1], remainingduration, demand, infeasible);
7307/** returns TRUE if the core (given by its demand and during) can be inserted at the given time point; otherwise FALSE */
7340 SCIPdebugMessage("profile <%p>: core does not fit at time point %d (pos %d)\n", (void*)profile, profile->timepoints[pos-1], pos-1);
7363/** return the latest possible starting point within the time interval [lb,ub] for a given core (given by its demand and
7399 SCIPdebugMessage("profile <%p>: latest completion time %d does %s exist as time point (pos %d)\n", (void*)profile, lct, found ? "" : "not", pos);
7412 /* if the time point left to the start time has not enough free capacity we can just search the profile starting
7434 pos = profileFindDownFeasibleStart(profile, pos, profile->timepoints[pos], remainingduration, demand, infeasible);
7505 SCIP_ALLOC( BMSreallocBlockMemoryArray(digraph->blkmem, &digraph->successors, digraph->nnodes, nnodes) );
7506 SCIP_ALLOC( BMSreallocBlockMemoryArray(digraph->blkmem, &digraph->arcdata, digraph->nnodes, nnodes) );
7507 SCIP_ALLOC( BMSreallocBlockMemoryArray(digraph->blkmem, &digraph->successorssize, digraph->nnodes, nnodes) );
7508 SCIP_ALLOC( BMSreallocBlockMemoryArray(digraph->blkmem, &digraph->nsuccessors, digraph->nnodes, nnodes) );
7509 SCIP_ALLOC( BMSreallocBlockMemoryArray(digraph->blkmem, &digraph->nodedata, digraph->nnodes, nnodes) );
7534 BMS_BLKMEM* targetblkmem /**< block memory to store the target block memory, or NULL to use the same
7562 SCIP_ALLOC( BMSallocClearBlockMemoryArray(targetblkmem, &(*targetdigraph)->successors, nnodes) );
7564 SCIP_ALLOC( BMSallocClearBlockMemoryArray(targetblkmem, &(*targetdigraph)->nodedata, nnodes) );
7579 /* copy node data - careful if these are pointers to some information -> need to be copied by hand */
7584 SCIP_ALLOC( BMSduplicateBlockMemoryArray(targetblkmem, &(*targetdigraph)->successorssize, sourcedigraph->nsuccessors, nnodes) );
7585 SCIP_ALLOC( BMSduplicateBlockMemoryArray(targetblkmem, &(*targetdigraph)->nsuccessors, sourcedigraph->nsuccessors, nnodes) );
7590 SCIP_ALLOC( BMSduplicateBlockMemoryArray(targetblkmem, &(*targetdigraph)->components, sourcedigraph->components,
7606 SCIP_ALLOC( BMSduplicateBlockMemoryArray(targetblkmem, &(*targetdigraph)->articulations, sourcedigraph->articulations, sourcedigraph->narticulations) );
7620/** sets the sizes of the successor lists for the nodes in a directed graph and allocates memory for the lists */
7635 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &digraph->successors[i], sizes[i]) ); /*lint !e866*/
7663 BMSfreeBlockMemoryArrayNull(blkmem, &digraphptr->successors[i], digraphptr->successorssize[i]);
7717 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &digraph->successors[idx], digraph->successorssize[idx]) ); /*lint !e866*/
7718 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &digraph->arcdata[idx], digraph->successorssize[idx]) ); /*lint !e866*/
7724 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &digraph->successors[idx], digraph->successorssize[idx], newsize) ); /*lint !e866*/
7725 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &digraph->arcdata[idx], digraph->successorssize[idx], newsize) ); /*lint !e866*/
7895/** returns the array of indices of the successor nodes; this array must not be changed from outside */
7911/** returns the array of data corresponding to the arcs originating at the given node, or NULL if no data exist; this
7937 int* stackadjvisited, /**< array of size number of nodes to store the number of adjacent nodes already visited
7939 int* dfsnodes, /**< array of nodes that can be reached starting at startnode, in reverse dfs order */
7940 int* ndfsnodes /**< pointer to store number of nodes that can be reached starting at startnode */
8003/** checks for articulation points in a given directed graph through a recursive depth-first-search.
8004 * starts from a given start node and keeps track of the nodes' discovery time in search for back edges.
8006 * @note an articulation point is a node whose removal disconnects a connected graph or increases
8015 int* mindisc, /**< array of size number of nodes to store the discovery time of the earliest discovered vertex
8018 SCIP_Bool* articulationflag, /**< array to mark whether a node is identified as an articulation point */
8051 findArticulationPointsUtil(digraph, succnodes[n], visited, tdisc, mindisc, parent, articulationflag, time + 1);
8059 * there is no back edge from the subtree rooted at child n to any of the ancestors of startnode */
8079 int** articulations, /**< array to store the sorted node indices of the computed articulation points, or NULL */
8104 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&articulationflag, digraph->nnodes), TERMINATE );
8109 if( digraph->narticulations >= 0 ) /* case: articulations have already been computed but not up-to-date */
8122 /* the function is called on every unvisited node in the graph to cover the disconnected graph case */
8126 findArticulationPointsUtil(digraph, n, visited, tdisc, mindisc, parent, articulationflag, time);
8130 SCIP_ALLOC_TERMINATE( retcode, BMSallocBlockMemoryArray(blkmem, &digraph->articulations, digraph->narticulations), TERMINATE );
8162 * @note For each arc, its reverse is added, so the graph does not need to be the directed representation of an
8206 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &digraph->componentstarts, digraph->componentstartsize) );
8209 SCIP_ALLOC_TERMINATE( retcode, BMSallocClearMemoryArray(&visited, digraph->nnodes), TERMINATE );
8211 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&stackadjvisited, digraph->nnodes), TERMINATE );
8212 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&ndirectedsuccessors, digraph->nnodes), TERMINATE );
8224 SCIP_CALL_TERMINATE( retcode, SCIPdigraphAddArc(digraph, digraph->successors[i][j], i, NULL), TERMINATE );
8251 SCIP_ALLOC_TERMINATE( retcode, BMSreallocBlockMemoryArray(blkmem, &digraph->componentstarts, digraph->componentstartsize, newsize), TERMINATE );
8289/** Performs an (almost) topological sort on the undirected components of the given directed graph. The undirected
8292 * @note In general a topological sort is not unique. Note, that there might be directed cycles, that are randomly
8319 SCIP_ALLOC_TERMINATE( retcode, BMSallocClearMemoryArray(&visited, digraph->nnodes), TERMINATE );
8322 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&stackadjvisited, digraph->nnodes), TERMINATE );
8334 /* perform depth first search, nodes visited in this call are appended to the list dfsnodes in reverse
8360/** returns the number of previously computed undirected components for the given directed graph */
8371/** Returns the previously computed undirected component of the given number for the given directed graph.
8372 * If the components were sorted using SCIPdigraphTopoSortComponents(), the component is (almost) topologically sorted.
8393/* Performs Tarjan's algorithm for a given directed graph to obtain the strongly connected components
8456 tarjan(digraph, w, lowlink, dfsidx, stack, stacksize, unprocessed, nodeinstack, maxdfs, strongcomponents,
8500/** Computes all strongly connected components of an undirected connected component with Tarjan's Algorithm.
8501 * The resulting strongly connected components are sorted topologically (starting from the end of the
8540 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&unprocessed, digraph->nnodes), TERMINATE );
8541 SCIP_ALLOC_TERMINATE( retcode, BMSallocMemoryArray(&nodeinstack, digraph->nnodes), TERMINATE );
8575 assert(nstorednodes == digraph->componentstarts[compidx + 1] - digraph->componentstarts[compidx]);
9051 * @note The user pointers (object) of the nodes are not freed. If needed, it has to be done by the user.
9067/** prints the rooted subtree of the given binary tree node in GML format into the given file */
9234 /* the following if/else condition is only to make sure that we do not overflow when adding up both values before
9313/* on systems where the function nextafter is not defined, we provide an implementation from Sun */
9464static const SCIP_Real simplednoms[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0,
9467/** converts a real number into a (approximate) rational representation, and returns TRUE iff the conversion was
9500 /* try the simple denominators first: each value of the simpledenoms table multiplied by powers of 10
9536 /* the simple denominators didn't work: calculate rational representation with arbitrary denominator */
9574 if( REALABS(g0) > (SCIP_Real)(SCIP_LONGINT_MAX >> 4) || h0 > (SCIP_Real)(SCIP_LONGINT_MAX >> 4) )
9611/** checks, whether the given scalar scales the given value to an integral number with error in the given bounds */
9616 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
9617 SCIP_Real maxdelta /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
9638/** tries to find a value, such that all given values, if scaled with this value become integral in relative allowed
9644 SCIP_Real mindelta, /**< minimal relative allowed difference of scaled coefficient s*c and integral i */
9645 SCIP_Real maxdelta, /**< maximal relative allowed difference of scaled coefficient s*c and integral i */
9648 SCIP_Real* intscalar, /**< pointer to store scalar that would make the coefficients integral, or NULL */
9710 /* try, if values can be made integral multiplying them with the reciprocal of the smallest value and a power of 2 */
9745 /* make values integral by dividing them by the smallest value (and multiplying them with a power of 2) */
9754 /* if the scalar is still the reciprocal of the minimal value, all coeffcients are the same and we do not get a better scalar */
9766 /* convert each value into a rational number, calculate the greatest common divisor of the numerators
9787 SCIPdebugMessage(" -> c=%d first rational: val: %g == %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", gcd=%" SCIP_LONGINT_FORMAT ", scm=%" SCIP_LONGINT_FORMAT ", rational=%u\n",
9807 SCIPdebugMessage(" -> c=%d next rational : val: %g == %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", gcd=%" SCIP_LONGINT_FORMAT ", scm=%" SCIP_LONGINT_FORMAT ", rational=%u\n",
9818 /* make values integral by multiplying them with the smallest common multiple of the denominators */
9825 SCIPdebugMessage(" -> integrality could be achieved by scaling with %g (rational:%" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ")\n",
9841/** tries to find a value, such that all given values, if scaled with this value become integral */
9847 SCIP_RATIONAL* intscalar, /**< pointer to store scalar that would make the coefficients integral */
9870 * SCIPcalcIntegralScalarExact(); even if we stay with the SCIP_Longint conversion, we could use the other way
9873 /* calculate the greatest common divisor of the numerators and the smallest common multiple of the denominators */
9938 /* update scm via newscm = scm * denominator / gcd(scm, denominator) and check whether it fits into SCIP_Longint */
9958 /* make values integral by multiplying them with the smallest common multiple of the denominators */
9975 * certain optimizations should be omitted (http://www.cplusplus.com/reference/cfenv/FENV_ACCESS/).
9990/** given a (usually very small) interval, tries to find a rational number with simple denominator (i.e. a small
9991 * number, probably multiplied with powers of 10) out of this interval; returns TRUE iff a valid rational
10009 /* in order to compute a rational number that is exactly within the bounds (as the user expects),
10037/** given a (usually very small) interval, selects a value inside this interval; it is tried to select a rational number
10039 * if no valid rational number inside the interval was found, selects the central value of the interval
10062 SCIPdebugPrintf(" %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " == %.9f\n", numerator, denominator, val);
10079/** Performs the Newton Procedure from a given starting point to compute a root of the given function with
10080 * specified precision and maximum number of iterations. If the procedure fails, SCIP_INVALID is returned.
10165 * KISS has a period of 2^123 and passes all statistical test part of BigCrush-Test of TestU01 [1].
10236 /* we need to shift the range to the non-negative integers to handle negative integer values correctly.
10257 /* we multiply minrandval and maxrandval separately by randnumber in order to avoid overflow if they are more than
10278 /* loop backwards through all elements and always swap the current last element to a random position */
10308 /* loop backwards through all elements and always swap the current last element to a random position */
10324 * this implementation is suited for the case that nsubelems is considerably smaller then nelems
10347 SCIPerrorMessage("Cannot create %d-elementary subset of %d-elementary set.\n", nsubelems, nelems);
10383/** calculates a binomial coefficient n over m, choose m elements out of n, maximal value will be 33 over 16 (because
10384 * the n=33 is the last line in the Pascal's triangle where each entry fits in a 4 byte value), an error occurs due to
10424 /* first half of Pascal's triangle numbers(without the symmetric part) backwards from (33,16) over (32,16),
10430 1166803110, 601080390, 1037158320, 565722720, 300540195, 155117520, 818809200, 471435600, 265182525, 145422675,
10431 77558760, 40116600, 573166440, 347373600, 206253075, 119759850, 67863915, 37442160, 20058300, 10400600,
10432 354817320, 225792840, 141120525, 86493225, 51895935, 30421755, 17383860, 9657700, 5200300, 2704156, 193536720,
10433 129024480, 84672315, 54627300, 34597290, 21474180, 13037895, 7726160, 4457400, 2496144, 1352078, 705432,
10434 92561040, 64512240, 44352165, 30045015, 20030010, 13123110, 8436285, 5311735, 3268760, 1961256, 1144066,
10435 646646, 352716, 184756, 38567100, 28048800, 20160075, 14307150, 10015005, 6906900, 4686825, 3124550, 2042975,
10436 1307504, 817190, 497420, 293930, 167960, 92378, 48620, 13884156, 10518300, 7888725, 5852925, 4292145, 3108105,
10437 2220075, 1562275, 1081575, 735471, 490314, 319770, 203490, 125970, 75582, 43758, 24310, 12870, 4272048, 3365856,
10438 2629575, 2035800, 1560780, 1184040, 888030, 657800, 480700, 346104, 245157, 170544, 116280, 77520, 50388, 31824,
10439 19448, 11440, 6435, 3432, 1107568, 906192, 736281, 593775, 475020, 376740, 296010, 230230, 177100, 134596,
10440 100947, 74613, 54264, 38760, 27132, 18564, 12376, 8008, 5005, 3003, 1716, 924, 237336, 201376, 169911, 142506,
10441 118755, 98280, 80730, 65780, 53130, 42504, 33649, 26334, 20349, 15504, 11628, 8568, 6188, 4368, 3003, 2002,
10442 1287, 792, 462, 252, 40920, 35960, 31465, 27405, 23751, 20475, 17550, 14950, 12650, 10626, 8855, 7315, 5985,
10459#if defined(__GNUC__) && __GNUC__ * 100 + __GNUC_MINOR__ * 10 >= 490 && !defined(__INTEL_COMPILER)
10529/** computes set intersection (duplicates removed) of two integer arrays that are ordered ascendingly */
10582/** computes set intersection (duplicates removed) of two void-pointer arrays that are ordered ascendingly */
10638/** computes set difference (duplicates removed) of two integer arrays that are ordered ascendingly */
10689/** copies characters from 'src' to 'dest', copying is stopped when either the 'stop' character is reached or after
10713/** prints an error message containing of the given string followed by a string describing the current system error
10715 * Prefers to use the strerror_r method, which is threadsafe. On systems where this method does not exist,
10716 * NO_STRERROR_R should be defined (see INSTALL). In this case, strerror is used which is not guaranteed to be
10733#elif (_POSIX_C_SOURCE >= 200112L || __DARWIN_C_LEVEL > 200112L || _XOPEN_SOURCE >= 600) && ! defined(_GNU_SOURCE)
10734 /* We are in the POSIX/XSI case, where strerror_r returns 0 on success; \0 termination is unclear. */
10740 /* We are in the GNU case, where strerror_r returns a pointer to the error string. This string is possibly stored
10742 * However, if compiling on one system and executing on another system, we might actually call a different
10781/** translates the given string into a string where unescaped symbols ", ', and spaces are escaped with a \ prefix */
10815/** increases string pointer as long as it refers to a space character or an explicit space control sequence */
10820 while( isspace((unsigned char)**s) || ( **s == '\\' && *(*s+1) != '\0' && strchr(SCIP_SPACECONTROL, *(*s+1)) ) )
10875/** portable version of strncasecmp for case-insensitive comparison of two strings up to a given number of characters */
10892 * Copies string in s to t using at most @a size-1 nonzero characters (strncpy copies size characters). It always adds
10893 * a terminating zero char. Does not pad the remaining string with zero characters (unlike strncpy). Returns the number
10894 * of copied nonzero characters, if the length of s is at most size - 1, and returns size otherwise. Thus, the original
10920/** extract the next token as a integer value if it is one; in case no value is parsed the endptr is set to @p str
10927 char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */
10951/** extract the next token as a double value if it is one; in case no value is parsed the endptr is set to @p str
10958 char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */
10982/** copies the first size characters between a start and end character of str into token, if no error occurred endptr
10991 char** endptr /**< pointer to store the final string position if successfully parsed, otherwise @p str */
11101 if( lastslash != NULL && lastdot != NULL && lastdot < lastslash ) /* is the last dot belonging to the path? */
11122 if( lastslash != NULL && lastdot != NULL && lastdot < lastslash ) /* is the last dot belonging to the path? */
11206/** creates a disjoint set (union find) structure \p djset for \p ncomponents many components (of size one) */
11343/** returns the number of independent components in this disjoint set (union find) data structure */
11363/** checks whether a given string t appears at the beginning of the string s (up to spaces at beginning) */
common defines and data types used in all packages of SCIP
void SCIPcomputeArraysIntersectionPtr(void **array1, int narray1, void **array2, int narray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void **intersectarray, int *nintersectarray)
Definition: misc.c:10583
void SCIPcomputeArraysSetminusInt(int *array1, int narray1, int *array2, int narray2, int *setminusarray, int *nsetminusarray)
Definition: misc.c:10639
void SCIPcomputeArraysIntersectionInt(int *array1, int narray1, int *array2, int narray2, int *intersectarray, int *nintersectarray)
Definition: misc.c:10530
void SCIPbtnodeSetRightchild(SCIP_BTNODE *node, SCIP_BTNODE *right)
Definition: misc.c:9023
SCIP_BTNODE * SCIPbtnodeGetRightchild(SCIP_BTNODE *node)
Definition: misc.c:8892
SCIP_RETCODE SCIPbtnodeCreate(SCIP_BT *tree, SCIP_BTNODE **node, void *dataptr)
Definition: misc.c:8753
void SCIPbtnodeSetParent(SCIP_BTNODE *node, SCIP_BTNODE *parent)
Definition: misc.c:8995
void SCIPbtnodeSetLeftchild(SCIP_BTNODE *node, SCIP_BTNODE *left)
Definition: misc.c:9009
SCIP_BTNODE * SCIPbtnodeGetLeftchild(SCIP_BTNODE *node)
Definition: misc.c:8882
void SCIPdigraphPrintComponents(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:8700
void ** SCIPdigraphGetSuccessorsData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7914
void SCIPdigraphFreeComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8594
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7881
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:8165
void SCIPdigraphPrintGml(SCIP_DIGRAPH *digraph, FILE *file)
Definition: misc.c:8661
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition: misc.c:8374
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7739
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8295
SCIP_RETCODE SCIPdigraphSetSizes(SCIP_DIGRAPH *digraph, int *sizes)
Definition: misc.c:7621
SCIP_RETCODE SCIPdigraphComputeDirectedComponents(SCIP_DIGRAPH *digraph, int compidx, int *strongcomponents, int *strongcompstartidx, int *nstrongcomponents)
Definition: misc.c:8506
SCIP_RETCODE SCIPdigraphAddArcSafe(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7770
void SCIPdigraphPrint(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:8626
void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7833
void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node)
Definition: misc.c:7849
SCIP_RETCODE SCIPdigraphSetNSuccessors(SCIP_DIGRAPH *digraph, int node, int nsuccessors)
Definition: misc.c:7807
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7896
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8361
SCIP_RETCODE SCIPdigraphResize(SCIP_DIGRAPH *digraph, int nnodes)
Definition: misc.c:7491
SCIP_RETCODE SCIPdigraphGetArticulationPoints(SCIP_DIGRAPH *digraph, int **articulations, int *narticulations)
Definition: misc.c:8077
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11344
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11247
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11274
void SCIPsplitFilename(char *filename, char **path, char **name, char **extension, char **compression)
Definition: misc.c:11073
void SCIPdotWriteArc(FILE *file, int source, int target, const char *color)
Definition: misc.c:740
void SCIPgmlWriteNodeWeight(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor, SCIP_Real weight)
Definition: misc.c:549
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:501
void SCIPdotWriteNode(FILE *file, int node, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:725
void SCIPgmlWriteEdge(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:599
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:643
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3613
SCIP_Real SCIPhashmapGetImageReal(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3344
SCIP_RETCODE SCIPhashmapInsertReal(SCIP_HASHMAP *hashmap, void *origin, SCIP_Real image)
Definition: misc.c:3251
void SCIPhashmapPrintStatistics(SCIP_HASHMAP *hashmap, SCIP_MESSAGEHDLR *messagehdlr)
Definition: misc.c:3528
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3304
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3284
SCIP_RETCODE SCIPhashmapSetImageReal(SCIP_HASHMAP *hashmap, void *origin, SCIP_Real image)
Definition: misc.c:3434
void SCIPhashmapEntrySetImageInt(SCIP_HASHMAPENTRY *entry, int image)
Definition: misc.c:3654
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3143
SCIP_RETCODE SCIPhashmapSetImage(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3366
int SCIPhashmapEntryGetImageInt(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3623
void SCIPhashmapEntrySetImageReal(SCIP_HASHMAPENTRY *entry, SCIP_Real image)
Definition: misc.c:3665
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3592
void SCIPhashmapEntrySetImage(SCIP_HASHMAPENTRY *entry, void *image)
Definition: misc.c:3643
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3061
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3603
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3466
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3179
SCIP_RETCODE SCIPhashmapInsertLong(SCIP_HASHMAP *hashmap, void *origin, SCIP_Longint image)
Definition: misc.c:3215
SCIP_Real SCIPhashmapEntryGetImageReal(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3633
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3482
SCIP_Longint SCIPhashmapGetImageLong(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3324
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3400
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3833
void SCIPhashsetPrintStatistics(SCIP_HASHSET *hashset, SCIP_MESSAGEHDLR *messagehdlr)
Definition: misc.c:3976
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3860
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3843
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3802
SCIP_RETCODE SCIPhashsetRemove(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3901
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2647
int SCIPhashtableGetNEntries(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2765
SCIP_RETCODE SCIPhashtableSafeInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2567
void * SCIPhashtableGetEntry(SCIP_HASHTABLE *hashtable, int entryidx)
Definition: misc.c:2773
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2298
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2596
SCIP_Real SCIPhashtableGetLoad(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2782
void SCIPhashtablePrintStatistics(SCIP_HASHTABLE *hashtable, SCIP_MESSAGEHDLR *messagehdlr)
Definition: misc.c:2792
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2665
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2535
SCIP_Longint SCIPhashtableGetNElements(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2755
SCIP_Longint SCIPmultihashGetNElements(SCIP_MULTIHASH *multihash)
Definition: misc.c:2233
SCIP_RETCODE SCIPmultihashInsert(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2026
SCIP_RETCODE SCIPmultihashRemove(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2178
SCIP_RETCODE SCIPmultihashSafeInsert(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2067
SCIP_Real SCIPmultihashGetLoad(SCIP_MULTIHASH *multihash)
Definition: misc.c:2243
SCIP_RETCODE SCIPmultihashCreate(SCIP_MULTIHASH **multihash, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:1962
void * SCIPmultihashRetrieve(SCIP_MULTIHASH *multihash, void *key)
Definition: misc.c:2086
void * SCIPmultihashRetrieveNext(SCIP_MULTIHASH *multihash, SCIP_MULTIHASHLIST **multihashlist, void *key)
Definition: misc.c:2115
SCIP_Bool SCIPmultihashExists(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2151
void SCIPmultihashPrintStatistics(SCIP_MULTIHASH *multihash, SCIP_MESSAGEHDLR *messagehdlr)
Definition: misc.c:2253
SCIP_Longint SCIPcalcGreComDiv(SCIP_Longint val1, SCIP_Longint val2)
Definition: misc.c:9197
SCIP_Longint SCIPcalcSmaComMul(SCIP_Longint val1, SCIP_Longint val2)
Definition: misc.c:9449
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:10041
SCIP_Real SCIPcomputeGap(SCIP_Real eps, SCIP_Real inf, SCIP_Real primalbound, SCIP_Real dualbound)
Definition: misc.c:11180
SCIP_Bool SCIPfindSimpleRational(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom, SCIP_Longint *numerator, SCIP_Longint *denominator)
Definition: misc.c:9994
SCIP_Real SCIPcalcRootNewton(SCIP_DECL_NEWTONEVAL((*function)), SCIP_DECL_NEWTONEVAL((*derivative)), SCIP_Real *params, int nparams, SCIP_Real x, SCIP_Real eps, int k)
Definition: misc.c:10082
SCIP_RETCODE SCIPcalcIntegralScalarExact(BMS_BUFMEM *buffer, SCIP_RATIONAL **vals, int nvals, SCIP_Real maxscale, SCIP_RATIONAL *intscalar, SCIP_Bool *success)
Definition: misc.c:9842
SCIP_Bool SCIPrealToRational(SCIP_Real val, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Longint *numerator, SCIP_Longint *denominator)
Definition: misc.c:9470
SCIP_RETCODE SCIPcalcIntegralScalar(SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
Definition: misc.c:9641
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
Definition: misc.c:10264
void SCIPrandomPermuteArray(SCIP_RANDNUMGEN *randnumgen, void **array, int begin, int end)
Definition: misc.c:10294
SCIP_RETCODE SCIPpqueueInsert(SCIP_PQUEUE *pqueue, void *elem)
Definition: misc.c:1396
SCIP_RETCODE SCIPpqueueCreate(SCIP_PQUEUE **pqueue, int initsize, SCIP_Real sizefac, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), SCIP_DECL_PQUEUEELEMCHGPOS((*elemchgpos)))
Definition: misc.c:1297
void SCIPintervalSetRoundingModeDownwards(void)
Definition: intervalarith.c:345
SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
Definition: intervalarith.c:277
void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
Definition: intervalarith.c:269
SCIP_Bool SCIPintervalHasRoundingControl(void)
Definition: intervalarith.c:240
void SCIPrationalMult(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition: rational.cpp:1066
void SCIPrationalFreeBuffer(BMS_BUFMEM *bufmem, SCIP_RATIONAL **rational)
Definition: rational.cpp:473
SCIP_Longint SCIPrationalDenominator(SCIP_RATIONAL *rational)
Definition: rational.cpp:2027
SCIP_RETCODE SCIPrationalCreateBuffer(BMS_BUFMEM *bufmem, SCIP_RATIONAL **rational)
Definition: rational.cpp:123
SCIP_Bool SCIPrationalIsZero(SCIP_RATIONAL *rational)
Definition: rational.cpp:1624
void SCIPrationalCanonicalize(SCIP_RATIONAL *rational)
Definition: rational.cpp:538
void SCIPrationalSetFraction(SCIP_RATIONAL *res, SCIP_Longint nom, SCIP_Longint denom)
Definition: rational.cpp:582
SCIP_Longint SCIPrationalNumerator(SCIP_RATIONAL *rational)
Definition: rational.cpp:2018
SCIP_RETCODE SCIPqueueInsertUInt(SCIP_QUEUE *queue, unsigned int elem)
Definition: misc.c:1107
SCIP_RETCODE SCIPqueueCreate(SCIP_QUEUE **queue, int initsize, SCIP_Real sizefac)
Definition: misc.c:995
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10245
SCIP_RETCODE SCIPrandomGetSubset(SCIP_RANDNUMGEN *randnumgen, void **set, int nelems, void **subset, int nsubelems)
Definition: misc.c:10326
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:10223
void SCIPregressionRemoveObservation(SCIP_REGRESSION *regression, SCIP_Real x, SCIP_Real y)
Definition: misc.c:353
void SCIPregressionAddObservation(SCIP_REGRESSION *regression, SCIP_Real x, SCIP_Real y)
Definition: misc.c:385
SCIP_Real SCIPregressionGetIntercept(SCIP_REGRESSION *regression)
Definition: misc.c:278
int SCIPregressionGetNObservations(SCIP_REGRESSION *regression)
Definition: misc.c:258
SCIP_RETCODE SCIPregressionCreate(SCIP_REGRESSION **regression)
Definition: misc.c:420
SCIP_Real SCIPregressionGetSlope(SCIP_REGRESSION *regression)
Definition: misc.c:268
SCIP_RETCODE SCIPactivityCreate(SCIP_RESOURCEACTIVITY **activity, SCIP_VAR *var, int duration, int demand)
Definition: misc.c:6718
int SCIPactivityGetDuration(SCIP_RESOURCEACTIVITY *activity)
Definition: misc.c:6773
int SCIPactivityGetEnergy(SCIP_RESOURCEACTIVITY *activity)
Definition: misc.c:6793
SCIP_VAR * SCIPactivityGetVar(SCIP_RESOURCEACTIVITY *activity)
Definition: misc.c:6763
int SCIPactivityGetDemand(SCIP_RESOURCEACTIVITY *activity)
Definition: misc.c:6783
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
Definition: misc.c:7097
int * SCIPprofileGetTimepoints(SCIP_PROFILE *profile)
Definition: misc.c:6904
int SCIPprofileGetLatestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7366
SCIP_Bool SCIPprofileFindLeft(SCIP_PROFILE *profile, int timepoint, int *pos)
Definition: misc.c:6950
int SCIPprofileGetEarliestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7217
int SCIPprofileGetNTimepoints(SCIP_PROFILE *profile)
Definition: misc.c:6894
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
Definition: misc.c:6832
SCIP_RETCODE SCIPprofileDeleteCore(SCIP_PROFILE *profile, int left, int right, int demand)
Definition: misc.c:7127
void SCIPprofilePrint(SCIP_PROFILE *profile, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:6862
SCIP_Real SCIPnormalCDF(SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
Definition: misc.c:200
SCIP_Real SCIPcomputeTwoSampleTTestValue(SCIP_Real meanx, SCIP_Real meany, SCIP_Real variancex, SCIP_Real variancey, SCIP_Real countx, SCIP_Real county)
Definition: misc.c:127
SCIP_Real SCIPnormalGetCriticalValue(SCIP_CONFIDENCELEVEL clevel)
Definition: misc.c:187
SCIP_Real SCIPstudentTGetCriticalValue(SCIP_CONFIDENCELEVEL clevel, int df)
Definition: misc.c:110
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
void SCIPsortDown(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:6144
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5581
void SCIPsortedvecInsertIntInt(int *intarray1, int *intarray2, int keyval, int field1val, int *len, int *pos)
void SCIPsortDownInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
SCIP_Longint * SCIPsparseSolGetLbs(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:851
void SCIPsparseSolGetFirstSol(SCIP_SPARSESOL *sparsesol, SCIP_Longint *sol, int nvars)
Definition: misc.c:871
SCIP_RETCODE SCIPsparseSolCreate(SCIP_SPARSESOL **sparsesol, SCIP_VAR **vars, int nvars, SCIP_Bool cleared)
Definition: misc.c:767
SCIP_Longint * SCIPsparseSolGetUbs(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:861
SCIP_Bool SCIPsparseSolGetNextSol(SCIP_SPARSESOL *sparsesol, SCIP_Longint *sol, int nvars)
Definition: misc.c:894
SCIP_VAR ** SCIPsparseSolGetVars(SCIP_SPARSESOL *sparsesol)
Definition: misc.c:831
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10924
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10955
void SCIPstrCopySection(const char *str, char startchar, char endchar, char *token, int size, char **endptr)
Definition: misc.c:10985
SCIP_Bool SCIPstrAtStart(const char *s, const char *t, size_t tlen)
Definition: misc.c:11364
int SCIPstrncasecmp(const char *s1, const char *s2, int length)
Definition: misc.c:10876
int SCIPmemccpy(char *dest, const char *src, char stop, unsigned int cnt)
Definition: misc.c:10694
static SCIP_RETCODE optimize(SCIP *scip, SCIP_SOL *worksol, SCIP_VAR **vars, int *blockstart, int *blockend, int nblocks, OPTTYPE opttype, SCIP_Real *activities, int nrows, SCIP_Bool *improvement, SCIP_Bool *varboundserr, SCIP_HEURDATA *heurdata)
Definition: heur_twoopt.c:967
interval arithmetics for provable bounds
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition: memory.h:462
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:468
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:458
#define BMSallocClearBlockMemoryArray(mem, ptr, num)
Definition: memory.h:455
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:618
void SCIPmessagePrintInfo(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:594
SCIP_RETCODE SCIPrealarrayExtend(SCIP_REALARRAY *realarray, int arraygrowinit, SCIP_Real arraygrowfac, int minidx, int maxidx)
Definition: misc.c:4131
SCIP_Bool SCIPboolarrayGetVal(SCIP_BOOLARRAY *boolarray, int idx)
Definition: misc.c:5056
static void incrementalStatsUpdate(SCIP_Real value, SCIP_Real *meanptr, SCIP_Real *sumvarptr, int nobservations, SCIP_Bool add)
Definition: misc.c:327
static SCIP_RETCODE doProfileCreate(SCIP_PROFILE **profile, int capacity)
Definition: misc.c:6810
SCIP_RETCODE SCIPboolarrayCopy(SCIP_BOOLARRAY **boolarray, BMS_BLKMEM *blkmem, SCIP_BOOLARRAY *sourceboolarray)
Definition: misc.c:4830
static void pqueueElemChgPos(SCIP_PQUEUE *pqueue, void *elem, int oldpos, int newpos)
Definition: misc.c:1346
static void multihashlistFree(SCIP_MULTIHASHLIST **multihashlist, BMS_BLKMEM *blkmem)
Definition: misc.c:1675
static SCIP_RETCODE multihashlistAppend(SCIP_MULTIHASHLIST **multihashlist, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:1653
static SCIP_RETCODE hashtableCheckLoad(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2482
SCIP_RETCODE SCIPrealarraySetVal(SCIP_REALARRAY *realarray, int arraygrowinit, SCIP_Real arraygrowfac, int idx, SCIP_Real val)
Definition: misc.c:4338
SCIP_RETCODE SCIPintarraySetVal(SCIP_INTARRAY *intarray, int arraygrowinit, SCIP_Real arraygrowfac, int idx, int val)
Definition: misc.c:4709
static SCIP_Bool multihashlistRemove(SCIP_MULTIHASHLIST **multihashlist, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:1813
static int profileFindFeasibleStart(SCIP_PROFILE *profile, int pos, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7159
static void tarjan(SCIP_DIGRAPH *digraph, int v, int *lowlink, int *dfsidx, int *stack, int *stacksize, SCIP_Bool *unprocessed, SCIP_Bool *nodeinstack, int *maxdfs, int *strongcomponents, int *nstrongcomponents, int *strongcompstartidx, int *nstorednodes)
Definition: misc.c:8397
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
Definition: misc.c:11325
static void depthFirstSearch(SCIP_DIGRAPH *digraph, int startnode, SCIP_Bool *visited, int *dfsstack, int *stackadjvisited, int *dfsnodes, int *ndfsnodes)
Definition: misc.c:7931
static SCIP_RETCODE profileUpdate(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
Definition: misc.c:7037
static SCIP_RETCODE ensureSuccessorsSize(SCIP_DIGRAPH *digraph, int idx, int newsize)
Definition: misc.c:7692
static SCIP_RETCODE profileInsertTimepoint(SCIP_PROFILE *profile, int timepoint, int *pos)
Definition: misc.c:6996
SCIP_RETCODE SCIPptrarrayExtend(SCIP_PTRARRAY *ptrarray, int arraygrowinit, SCIP_Real arraygrowfac, int minidx, int maxidx)
Definition: misc.c:5223
SCIP_RETCODE SCIPboolarrayExtend(SCIP_BOOLARRAY *boolarray, int arraygrowinit, SCIP_Real arraygrowfac, int minidx, int maxidx)
Definition: misc.c:4868
SCIP_RETCODE SCIPptrarrayCopy(SCIP_PTRARRAY **ptrarray, BMS_BLKMEM *blkmem, SCIP_PTRARRAY *sourceptrarray)
Definition: misc.c:5186
static void * multihashlistRetrieve(SCIP_MULTIHASHLIST *multihashlist, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr, uint64_t keyval, void *key)
Definition: misc.c:1730
static SCIP_RETCODE hashtableInsert(SCIP_HASHTABLE *hashtable, void *element, void *key, uint32_t hashval, SCIP_Bool override)
Definition: misc.c:2398
static void btPrintSubtree(SCIP_BTNODE *node, FILE *file, int *nnodes)
Definition: misc.c:9069
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem)
Definition: misc.c:10209
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
Definition: misc.c:11207
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:10193
SCIP_RETCODE SCIPintarrayCopy(SCIP_INTARRAY **intarray, BMS_BLKMEM *blkmem, SCIP_INTARRAY *sourceintarray)
Definition: misc.c:4465
static SCIP_RETCODE hashmapInsert(SCIP_HASHMAP *hashmap, void *origin, SCIP_HASHMAPIMAGE image, uint32_t hashval, SCIP_Bool override)
Definition: misc.c:2890
SCIP_RETCODE SCIPdigraphCreate(SCIP_DIGRAPH **digraph, BMS_BLKMEM *blkmem, int nnodes)
Definition: misc.c:7454
static uint32_t hashSetDesiredPos(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3701
SCIP_RETCODE SCIPintarrayCreate(SCIP_INTARRAY **intarray, BMS_BLKMEM *blkmem)
Definition: misc.c:4445
static SCIP_RETCODE hashsetCheckLoad(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3761
static void regressionRecompute(SCIP_REGRESSION *regression)
Definition: misc.c:289
SCIP_Real SCIPrealarrayGetVal(SCIP_REALARRAY *realarray, int idx)
Definition: misc.c:4317
SCIP_RETCODE SCIPrealarrayIncVal(SCIP_REALARRAY *realarray, int arraygrowinit, SCIP_Real arraygrowfac, int idx, SCIP_Real incval)
Definition: misc.c:4407
SCIP_RETCODE SCIPrealarrayCreate(SCIP_REALARRAY **realarray, BMS_BLKMEM *blkmem)
Definition: misc.c:4073
static void findArticulationPointsUtil(SCIP_DIGRAPH *digraph, int startnode, SCIP_Bool *visited, int *tdisc, int *mindisc, int *parent, SCIP_Bool *articulationflag, int time)
Definition: misc.c:8010
static int profileFindDownFeasibleStart(SCIP_PROFILE *profile, int pos, int ect, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7309
static SCIP_RETCODE pqueueResize(SCIP_PQUEUE *pqueue, int minsize)
Definition: misc.c:1280
SCIP_RETCODE SCIPrealarrayCopy(SCIP_REALARRAY **realarray, BMS_BLKMEM *blkmem, SCIP_REALARRAY *sourcerealarray)
Definition: misc.c:4093
void * SCIPptrarrayGetVal(SCIP_PTRARRAY *ptrarray, int idx)
Definition: misc.c:5409
void SCIPrandomSetSeed(SCIP_RANDNUMGEN *randnumgen, unsigned int initseed)
Definition: misc.c:10139
SCIP_RETCODE SCIPintarrayExtend(SCIP_INTARRAY *intarray, int arraygrowinit, SCIP_Real arraygrowfac, int minidx, int maxidx)
Definition: misc.c:4502
static SCIP_RETCODE multihashResize(SCIP_MULTIHASH *multihash)
Definition: misc.c:1846
SCIP_RETCODE SCIPboolarrayCreate(SCIP_BOOLARRAY **boolarray, BMS_BLKMEM *blkmem)
Definition: misc.c:4810
static SCIP_RETCODE ensureProfileSize(SCIP_PROFILE *profile, int neededsize)
Definition: misc.c:6973
static SCIP_Bool isIntegralScalar(SCIP_Real val, SCIP_Real scalar, SCIP_Real mindelta, SCIP_Real maxdelta)
Definition: misc.c:9613
static SCIP_RETCODE btnodeCreateEmpty(SCIP_BT *tree, SCIP_BTNODE **node)
Definition: misc.c:8737
static void * multihashlistRetrieveNext(SCIP_MULTIHASHLIST **multihashlist, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr, uint64_t keyval, void *key)
Definition: misc.c:1780
SCIP_RETCODE SCIPintarrayIncVal(SCIP_INTARRAY *intarray, int arraygrowinit, SCIP_Real arraygrowfac, int idx, int incval)
Definition: misc.c:4777
static SCIP_Bool hashmapLookup(SCIP_HASHMAP *hashmap, void *origin, uint32_t *pos)
Definition: misc.c:2965
SCIP_RETCODE SCIPdigraphCopy(SCIP_DIGRAPH **targetdigraph, SCIP_DIGRAPH *sourcedigraph, BMS_BLKMEM *targetblkmem)
Definition: misc.c:7531
SCIP_RETCODE SCIPptrarrayCreate(SCIP_PTRARRAY **ptrarray, BMS_BLKMEM *blkmem)
Definition: misc.c:5166
SCIP_RETCODE SCIPptrarraySetVal(SCIP_PTRARRAY *ptrarray, int arraygrowinit, SCIP_Real arraygrowfac, int idx, void *val)
Definition: misc.c:5430
static SCIP_MULTIHASHLIST * multihashlistFind(SCIP_MULTIHASHLIST *multihashlist, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr, uint64_t keyval, void *key)
Definition: misc.c:1699
SCIP_RETCODE SCIPboolarraySetVal(SCIP_BOOLARRAY *boolarray, int arraygrowinit, SCIP_Real arraygrowfac, int idx, SCIP_Bool val)
Definition: misc.c:5077
internal miscellaneous methods
Definition: pqueue.h:38
public methods for message output
public data structures and miscellaneous methods
wrapper for rational number arithmetic
template functions for sorting
Definition: memory.c:2545
Definition: struct_misc.h:181
Definition: struct_misc.h:240
Definition: struct_misc.h:249
Definition: struct_misc.h:221
Definition: struct_misc.h:279
Definition: struct_misc.h:132
Definition: struct_misc.h:139
Definition: struct_misc.h:151
Definition: struct_misc.h:90
Definition: struct_misc.h:170
Definition: struct_message.h:46
Definition: struct_misc.h:105
Definition: struct_misc.h:112
Definition: struct_misc.h:79
Definition: struct_misc.h:211
Definition: struct_misc.h:192
Definition: struct_misc.h:61
Definition: struct_misc.h:270
Definition: struct_rational.h:47
Definition: struct_misc.h:159
Definition: struct_misc.h:256
Definition: struct_misc.h:203
Definition: struct_misc.h:47
Definition: struct_var.h:262
miscellaneous datastructures
Definition: heur_padm.c:135
Definition: struct_misc.h:123