NAME vcsp.tcl vcsp SYNOPSIS vcsp.tcl vcsp vcsp-file.ds instancy infinity algos varheuristic classe-vcsp maxrealtime simplify-minimum-valuation mastervalues-file.mv minimum maxcc init-max-depth quality-sa temperature-geom-decr-min temperature-geom-decr-max temperature-init temperature-min temperature-geom-decr levelsize greedy-descent-search-size max-number-of-variables-per-components selected-first-variable-value-index rdsoptimum-file.rds degree-of-approximation number-of-partition balance-coefficient DESCRIPTION vcsp solves CSPs and VCSPs. vcsp.tcl is a graphical frontend for the application vcsp. example% vcsp.tcl and click "GO!" reads the random VCSP problem 15_10_80_80.ds instancy number 0, performs a static variable ordering "max degree first", and solves it with partial forward checking using dynamic "min domain then max degree first" variable order and dynamic "min inconsistency count" value order. example% vcsp ../benchs/famous/zebra.ds 0 reads the Zebra CSP problem (file zebra.ds, instancy number 0, see ds-format.txt) example% vcsp ../benchs/famous/zebra.ds 0 -1 8 reads the Zebra CSP problem and solves it with partial forward checking and initial static variable and value orders. OPERANDS & OPTIONS Must appear in the order given by the synopsis. Operands 1 and 2 are mandatory. Keywords used in the vcsp.tcl interface are given in parenthesis. 1. vcsp-file.ds (VCSP:) CSP or VCSP file name in '.ds' format 2. instancy (Instancy:) Instancy number (selects a subset of the constraints) 3. infinity (GUB) Initial global upper bound (GUB). Used as the maximum element of the valuation set. Any cost greater than GUB is converted to GUB. A negative value -1 sets GUB to the sum of all constraint costs plus one. Default value: -1 4. algos (Solving methods: & Static variable orders:) Bitvector to select static variable orders and solving methods. Each following number is a switch (2^x) to activate a function. - static variable order preprocessing (several orders can be performed successively) 1 Max degree (var-maxdeg) 4096 Max cardinality [Givry98, p.61] (var-maxcard) 8192 Min criticality [Givry98, p.64] (var-mincrit) 16384 Reverse variable order (reverse-var-order) 65536 Max cruciality [Givry98, p.64] (var-maxcruc) 262144 Min domain (var-mindom) 2 Sort constraints by max tightness then max priority (constr-max-tightness-priority) - solving methods 8 Partial forward checking 1024 Russian Doll Search (RDS) 2048 Russian Doll Search for VariableValuedCSPs (VVCSP) (use this flag for SPOT5 problems) 32 Simulated Annealing (not accessible from the interface) (automatic tuning of temperature cooling scheme) 128 Simple Simulated Annealing (by default in the interface) 33554432 Simulated Annealing for K-Partitioning - simplification techniques 4 Extract connected components (Connected Components) 32768 Heuristic k-partitioning (QuasiConnected Components) 8388608 Inverse static variable order before domain reduction simplification process (RevOrder) 16777216 When reducing domains, always select the best value to be removed from all the variables instead of from the cyclical-next variable (Greedy) - solving method extensions 16 Directed Arc-Consistency Counts (DAC) 1048576 DAC taking into account value deletion (DACdyn) 67108864 DACdyn until a fix point is reached (FullDACdyn) 524288 Arc Consistency preprocessing (AC3) 131072 Maintain Arc Consistency (MAC3) 2097152 Iterative Deepening Search (IDS) 4194304 Iterative Deepening Search with double ratio (x2) - miscellaneous 64 Print or save variables and constraints (Save VCSP to file) It depends on the shell environment variable SAVEVCSP. 256 Convert VCSP to 01-ILP format (not accessible from the interface) 512 Convert VCSP arc-consistency to 01-ILP format (not accessible from the interface) example% vcsp ../benchs/famous/zebra.ds 0 -1 9 reads the Zebra CSP problem, performs max degree variable order preprocessing (1) and solves it with partial forward checking (8). example% vcsp ../benchs/famous/zebra.ds 0 1 655369 reads the Zebra CSP problem, performs max degree variable order preprocessing (1), performs arc consistency preprocessing (524288), and solves it with partial forward checking (8) while maintaining arc consistency (131072). Default value: 0 (do nothing) 5. varheuristic (Dynamic variable orders: & Dynamic value orders:) Bitvector to select dynamic variable and value orders. Each following number is a switch (2^x) to activate a function. - dynamic variable orders 0 static variable order 1 min domain / max degree (dom1/deg) 2 min domain then max degree (dom1_deg) 4 min domain then min criticality (dom1_crit) 8 min domain then max criticality (dom1_invcrit) 16 min domain then max cruciality (dom1_cruc) 32 min domain then min cruciality (dom1_invcruc) 64 min criticality (criticality) 128 max criticality (invcrit) 256 max cruciality (cruciality) 512 min cruciality (invcruc) 1024 min domain then max degree then max inconsistency counts (fcval) (dom1_deg_fcval) - dynamic value orders 0 min fcval then min RDS count (if present) (min_fcval_RDS) 2048 min fcval then min cruciality then min rds count (min_fcval_cruciality) 4096 min fcval + cruciality (min_fcval+cruciality) 8192 initial domain order (next) example% vcsp ../benchs/famous/zebra.ds 0 -1 9 2 reads the Zebra CSP problem, performs max degree variable order preprocessing (1) and solves it with partial forward checking (8) using a dynamic variable order "min domain max degree" and a dynamic value order "min fcval". Default value: 0 (use static variable order and dynamic "min fcval first" value order) 6. classe-vcsp (Operator:) Select the class of VCSP (i.e its valuation set and aggregation operator): - "classic" : classic CSP (<=> GUB = 1) - "max" : possibilistic CSP (Max) - "lexico" : lexicographic CSP (Lex) - "penalty" : additive/weighted CSP (Sum) Default value: "penalty" 7. maxrealtime (cpu time:) Maximum computation time in seconds Default value: 0 (no cpu time limit) 8. simplify-minimum-valuation (Cost >=) Remove all soft constraints with a cost strictly lower than the given minimum. Reduce the valuation set accordingly. Default value: 0 (no simplification) 9. mastervalues-file.mv (DomReduc:) If the file exists, load domain reduction information. Else if the option corresponds to a strictly positive integer, then performs as a preprocessing step the given number of domain reductions and saves this information in the file vcsp-file.mv. Default value: "" (no domain reduction) 10. minimum (GLB) Set initial global lower bound (GLB). Default value: 0 (do nothing) 11. maxcc (constraint checks:) Maximum number of constraint checks Default value: -1 (no constraint check limit) 12. init-max-depth (IDRDS_InitDepth:) Initial maximum depth in Russian Doll Search. See [Cabon et al., CP-98]. If non zero, an iterative deepening scheme is mixed with RDS. Default value: 0 (no simplification) 13. quality-sa Automatic tuning for Simulated Annealing. A smaller value means a longer cooling scheme. Default value: 1.0 14. temperature-geom-decr-min Automatic tuning for Simulated Annealing. Maximum geometric decreasing factor for the temperature cooling scheme. Default value: 0.5 15. temperature-geom-decr-max Automatic tuning for Simulated Annealing. Minimum geometric decreasing factor for the temperature cooling scheme. Default value: 0.99 16. temperature-init (not accessible in the interface) Initial temperature for the simple Simulated Annealing algorithm. This initial temperature is automatically adjusted at the beginning of the cooling scheme. Default value: 10.0 17. temperature-min (TMin:) Minimum temperature for the simple Simulated Annealing algorithm. Default value: 0.001 18. temperature-geom-decr (TGDecr:) Geometric decreasing factor for the simple Simulated Annealing algorithm. Default value: 0.99 19. levelsize (#step:) Number of random moves at a given temperature for the simple Simulated Annealing algorithm. Default value: -1 (= sum of domain sizes) 20. greedy-descent-search-size (#greedy:) Number of additional random moves before the current configuration is re-evaluated by the Gibbs-Boltzmann probability function when the normal random flip was refused. Default value: 0 21. max-number-of-variables-per-components (QuasiCC_size:) Set K for the heuristic K-partitioning algorithm. Default value: 0 22. selected-first-variable-value-index (AssignFirstVar:) Preassign the first variable in the current static order to a given value. Useful when implementing parallel solving methods. Default value: -1 (no preassignment) 23. rdsoptimum-file.rds (RDSoptima:) Set the optimum values for some of the successive steps/sweep (associated to a given "last-included" variable in the current static order) of the Russian Doll Search method. Default value: "" (no RDS information) 24. degree-of-approximation (e-BB) Epsilon-approximation branch and bound. A large value means a poor lower bound. Ex: 0.1 means a solution at 10% from the optimum at most. Default value: 0. (assume a complete search) 25. number-of-partition (K =) Number of partitions for the K-Partioning algorithms. Each partition should contain the same number of variables. Default value: 0 26. balance-coefficient (Size/cost ratio) Ratio between partition size disequilibrium and inter-partition constraint costs. Default value: 0.0 (should be equal to 1.0 or more) FILES ./vcsp.tcl Tcl/Tk/Tix interface for solaris/vcsp solaris/vcsp application directory solaris/tixwish Tcl/Tk/Tix interpret SEE ALSO vcsp_anytime.tcl vcsp_anytime AUTHOR Simon de Givry (degivry@toulouse.inra.fr)