NAME vcsp_anytime.tcl vcsp_anytime SYNOPSIS vcsp_anytime.tcl vcsp_anytime file-vcsp instancy infinity maxrealtime maxcc algos varheuristic quality-sa temperature-geom-decr-min temperature-geom-decr-max number-of-sa first-classe-vcsp minimum init-max-depth DESCRIPTION vcsp_anytime solves CSPs and VCSPs with an anytime bounding of the optimum. vcsp_anytime.tcl is a graphical frontend for the application vcsp_anytime. example% vcsp_anytime.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 then builds an anytime bounding of the optimum: - performs a succession of problem simplifications by modying the aggregation operator, starting from the simplest one (`logical-or' by default) to the most complex one (`sum') and by removing the constraints with the smallest costs first. Every simplified problem is solved with partial forward checking using dynamic "min domain then max degree first" variable order. and dynamic "min inconsistency count" value order. Every complete solving produces an increasing lower bound until the optimum is reached. - in parallel, runs two simulated annealing algorithms which produce decreasing upper bounds. example% vcsp_anytime benchs/random/15_10_80_80.ds 0 -1 0 -1 9 2 1.0 0.5 0.99 0 classic 0 0 does exactly the same thing without the graphical interface. OPERANDS & OPTIONS Must appear in the order given by the synopsis. Operands 1 and 2 are mandatory. Keywords used in the vcsp_anytime.tcl interface are given in parenthesis. 1. file-vcsp (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. maxrealtime (cpu time:) Maximum computation time in seconds Default value: 0 (no cpu time limit) 5. maxcc (constraint checks:) Maximum number of constraint checks Default value: -1 (no constraint check limit) 6. algos (Complete solving methods: & Static var 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 (InvSort) 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 (not accessible from the interface) 64 Print variables and constraints 256 Convert VCSP to 01-ILP format 512 Convert VCSP arc-consistency to 01-ILP format Default value: 12 (extract connected components and solve with partial forward checking) 7. varheuristic (Dynamic var 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) Default value: 2 (use "min domain then max degree" dynamic variable order and dynamic "min fcval first" value order) 8. quality-sa (SA speed:) Automatic tuning for Simulated Annealing. A smaller value means a longer cooling scheme. Default value: 1.0 9. temperature-geom-decr-min (TempGeomDecrMin:) Automatic tuning for Simulated Annealing. Maximum geometric decreasing factor for the temperature cooling scheme. Default value: 0.5 10. temperature-geom-decr-max (TempGeomDecrMax:) Automatic tuning for Simulated Annealing. Minimum geometric decreasing factor for the temperature cooling scheme. Default value: 0.99 11. number-of-sa (Number of SA:) Number of simulated annealing algorithms running in parallel (in multi-threading) Default value: 0 12. first-classe-vcsp (Initial operator:) Select the initial class of VCSP (i.e its valuation set and aggregation operator) used to simplify the search: - "nothing" : do not use any complete search method (No complete solving) - "classic" : classic CSP (Or) - "max" : possibilistic CSP (Max) - "lexico" : lexicographic CSP (Lex) - "penalty" : additive/weighted CSP (Sum) - "original" : do not use any operator simplification (No simplification) Default value: "classic" 13. minimum (GLB) Set initial global lower bound (GLB). Default value: 0 (do nothing) 14. 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) FILES ./vcsp_anytime.tcl Tcl/Tk/Tix interface for solaris/vcsp_anytime solaris/vcsp_anytime application directory solaris/tixwish Tcl/Tk/Tix interpret SEE ALSO vcsp.tcl vcsp AUTHOR Simon de Givry (degivry@toulouse.inra.fr)