Remarques sur les révisions

Nom de version : Release 0.9.6.0

Notes

Toulbar2 source release 0.9.6.0  including Dead end elimination  (DEE ) and various features and bugs fix. 

Journaux

[feature] DEE applied for EnumerateVariables only
[feature] DEE for binary and ternary cost functions only
[feature] 	-epsilon=[float] : approximation factor for computing the partition function Z
[feature] improved DEE and Goldstein dominance rules
[feature] maximum spanning tree DAC ordering using median costs in cost functions (option -mst)
[feature] modified option -m=[integer] : variable ordering heuristic based on mean (m=1) or median (m=2) costs (in conjunction with weighted degree heuristic -q) (default value is 0)
[feature] new approximation scheme for computing the partition function Z of a Bayesian/Markov network (epsilon branch and bound, aka K*)
[feature] new options -dee=[integer] : restricted dead-end elimination (value pruning by dominance rule from EAC value (dee>=1 and dee<=3)) and soft neighborhood substitutability (in preprocessing (dee=2 or dee=4) or during search (dee=3)) -m : cost-based variable ordering heuristic (in conjunction with -q) -mst : maximum spanning tree DAC ordering
[feature] putative new variable ordering heuristic based on median cost function costs


[bug] allows functional and variable elimination only on intermediate  variables (due to global cost function decomposition) if all solutions are searched for.
[bug] always allows bijective variable elimination
[bug] better check functional ternary cost functions and update supports more frequently
[bug] bug correction in new dichotomic (d=2) search with LDS
[bug] bug correction in ternaryconstraint between Value/domain index and check type correction for Value and domain indices (unsigned int) in the main code.
[bug] bug  in narycsp  reader format corrected
[bug] check functional elimination does not increase n-ary cost function size too much (MAX_NB_TUPLES) and speed up n-ary cost function processing during functional elimination.
[bug] correction for saving wcsp problem with n-ary cost functions using arbitrary (negative) domain values
[bug] correction in DEBUG mode using DEE and Lc=AC
[bug] correction in INCOP local solver for computing constraint nbtuples.
[bug] correction in lower_ and upper_bound EnumVar methods
[bug] correction in lower_ and upper_bound methods (wrongly redefine as macro)
[bug] DEE cannot be performed before the whole problem is read
[bug] do not extend unary costs in ternary cost functions in preprocessing if soft AC is used instead of EDAC (better for SPOT5 using RDS)
[bug] functional elimination was not using toIndex/toValue properly
[bug] global cost functions were not initialized by setDACOrder when reserve DAC is applied in preprocessing
[bug] global monolithic cost functions did not checked for assigned variables BEFORE the search (due to single domain or partial solution input)
[bug] global monolithic cost functions must not be propagated outside general WCSP::propagate (they need structure initialization) => use flag method isGlobal() to avoid this in assignLS or setDACOrder
[bug] nary cost functions (in extension) have to be propagated (including creating their associated ternary and binary cost functions) after all variables have been created in order to get the right maxdomainsize value. (=> NOW DONE in sortConstraints() )
[bug] propagate first before reading a solution otherwise if the search continue after then propagation queues are not correctly initialized
[bug]  sort domains based on unary costs in preprocessing now give correct output solutions
[bug] ternary cost functions using functional short cuts now working with negative domains
[bug] XML reader need to update number of decision variables.


[code] Additional data structure for sorting "triplets".
[code] allows to save a problem with negative values if reencoding of domains is used (-z=2)
[code] cast modification compliant with g++ 4.7.3. 
[code]Changed the '-t' behavior: always tries to create triplets and stops when memory is exhausted. Triplets are sorted by a simple heuristics (thightness/memory).
[code] check bad values when reading cost function from file
[code] check cost function scope has no duplicated variables in DEBUG mode
[code]  cost-based variable ordering heuristic is in conjunction with weighted degree heuristic (no more restricted to binary search or lastconflict)
[code] fabs replaced by template abs
[code] file toulbar2test.cpp replacing tb2main.cpp shows examples using negative domains with global decomposable cost functions
[code] free STL memory (does not work?)
[code] improve memory usage for variable elimination during search and for n-ary cost function propagation (allocates memory on demand instead of using maximum initial domain size)
[code] incop outputs its best solution which can be saved in sol file
[code] in debug mode (-Z) output a current search size estimate
[code] integration with numberjack: convert Value into index and vice-versa
[code] interrupt solver using CtrlC or timer
[code] MacOS compatibility issue
[code] Modified output for DEE removal to facilitate parsing when DEE not activated.
[code] move DEE getmax from hpp to cpp (but again profiling is not satisfactory.. getUb,getLb not inlined?!)
[code] new methods for compatibility with Numberjack
[code] new timer functionality in order to stop the search
[code] numberjack: add nextValue generic function in the toulbar2 interface
[code] output messages compatible with MaxSAT Evaluation
[code] possibility to decompose wamong using additionnal LB/UB linear constraints on all subsets of values. (code in comment)
[code] print DEE node removal when reporting number of search nodes
[code] RDS now is compatible with static variable ordering (-svo).  note that for SPOT5 best option is  -B=3 -j=1 -k=1 -svo -h:
[code] remove some trace messages.
[code] replace breaking ties with epsilon by epsilon * best
[code] show maximum domain size after preprocessing global decomposable cost functions
[code] special main to test toulbar2 API.
[code] special Makefile to test toulbar2 API and check type conversions.
[code] update code for new g++ 4.7.2 compiler
[code] use default abs function for int rather than its template version
[code] warning! EDAC is not performed for non-decomposable global cost functions


[doc] minor documentation change
[doc] new release 0.9.6
[doc] unit tests for decomposable cost functions
[doc] wvaramong and wvarsum short documentation
Powered By FusionForge