********************************************************************** This file gives some examples about: - simplification techniques - anytime optimum bounding - local consistency enforcement - save simplified VCSPs into files ********************************************************************** Legend: PFC = Partial Forward Checking RDS = Russian Doll Search SA = Simulated Annealing KPART = K-Partitioning CC = Connected Components QCC = QuasiConnected Components Other abbreviations are the same as in the graphical interface and are described in the vcsp.txt documentation. In parenthesis, we give the options for the graphical interface. -------------------------------------------- An overview of the simplification techniques -------------------------------------------- The goal is to simplified the problem or the objective or to modify the search exploration strategy in order to obtain a global lower bound more rapidly. Examples of problem simplifications: ------------------------------------ The optimum found when solving these simplifications is directly a global lower bound of the original problem. - Reduce the number of constraints by removing the smallest ones. Solve benchs/spot5/509.ds without any simplification: example% cd vcsp example% solaris/vcsp benchs/spot5/509.ds 0 -1 2052 0 penalty 0 0 (RDS VVCSP, CC, no static variable order) results% optimum= 36446 in 144496 nd, 13647474 ccks, 67.8 sec Solve benchs/spot5/509.ds removing constraints of cost less than 1000: example% solaris/vcsp benchs/spot5/509.ds 0 -1 2052 0 penalty 0 1000 (RDS VVCSP, CC, Cost >= 1000, no static variable order) results% optimum= 36000 in 1768 nd, 4574702 ccks, 6.7 sec - Reduce the maximum number of variables connected together by removing constraints such that the connected components have a given maximum size. The goal is to partition the variables into disjoint subsets. All the intra constraints , i.e. between subsets, are removed. --> First algorithm: heuristic K-partitioning. Solve benchs/spot5/509.ds with maximum of 50 or 100 variables/subset: example% solaris/vcsp benchs/spot5/509.ds 0 -1 34820 0 penalty 0 0 "" 0 -1 0 1.0 0.5 0.99 -1 0.01 0.95 -1 10 50 (RDS VVCSP, QCC, QuasiCC_size: 50, no static variable order) results% optimum= 33437 in 11381 nd, 460399 ccks, 1.6 sec example% solaris/vcsp benchs/spot5/509.ds 0 -1 34820 0 penalty 0 0 "" 0 -1 0 1.0 0.5 0.99 -1 0.01 0.95 -1 10 100 (RDS VVCSP, QCC, QuasiCC_size: 100, no static variable order) results% optimum= 34444 in 173116 nd, 6708335 ccks, 31.3 sec Solve benchs/celar/6.ds with maximum of 10 variables/subset and constraints cost less than 100 removed: example% solaris/vcsp benchs/celar/6.ds 0 -1 37893 0 penalty 0 100 "" 0 -1 0 1.0 0.5 0.99 -1 0.01 0.95 -1 10 10 (RDS, QCC, QuasiCC_size: 10, Cost >= 100, var-maxdeg, var-maxcard) results% optimum= 900 in 12124 nd, 2518372 ccks, 3.2 sec --> Second algorithm: balanced K-partitioning. This is not fully automatic. You have to transform first your initial problem into a k-partitioning problem by using a simple awk program. Every constraint is transformed into an equality constraint. And domain sizes are set to k. Then you solve this new problem using the "K-partitioning" solving method. Next, you produce from your initial problem and the partitioning result a simplified problem, by using another awk program. Last you solve the simplified problem with option "Connected Component" on. Transform benchs/celar/6.ds into a 6-partitioning problem: example% nawk -f benchs/celar/ds2kpart.awk benchs/celar/6.ds 6 > benchs/celar/6_6part_new.ds Solve this problem using a bi-criterion Simulated Annealing taking into account partition size disequilibrium and inter-partition constraint costs: example% solaris/vcsp benchs/celar/6_6part.ds 0 -1 33558529 0 penalty 0 0 "" 0 -1 0 1.0 0.5 0.99 -1 0.01 0.9 1000 50 100 -1 "" 0.0 6 100.0 (KPART, TMin:0.01, TGDecr:0.9, #step:1000, #greedy:50, K = 6, Size/cost ratio: 100, var-maxdeg, var-maxcard) results% 0 nd, 65912617 ccks, 56.3 sec Constraints relaxation cost = 19090 , balance term = 2533 Partition 0 contains 21 variables Partition 1 contains 15 variables Partition 2 contains 16 variables Partition 3 contains 16 variables Partition 4 contains 17 variables Partition 5 contains 15 variables KPART outputs the k-partitioning result in a file, in the current directory: example% mv Celar_6_computer_275393.0_0.010_0.900_1000_50_6_200.0_1 benchs/celar/6_6part.result_new From this file, you can generate the simplified CELAR 6 problem: example% nawk -f benchs/celar/kpart2ds.awk benchs/celar/6_6part.result benchs/celar/6.ds > benchs/celar/6_6part_result_new.ds Then solve this problem with SA applied on the connected components in order to estimate the quality of the lower bound that could be deduced by a complete solving: example% solaris/vcsp benchs/celar/6_6part_result.ds 0 -1 132 0 penalty 0 0 "" 0 -1 0 1.0 0.5 0.99 -1 0.01 0.9 1000 50 (SA, CC, TMin:0.01, TGDecr:0.9, #step:1000, #greedy:50) results% 0 nd, 349688080 ccks, 456.2 sec There are 12 connected components. SA found a total upper bound of 2260 - Reduce the number of values by removing values which are quasi-substitutable to others using the notion of valued epsilon-interchangeability and valued epsilon-substitutability. Transforms the constraints accordingly in order to ensure the optimum of the simplified problem is a global lower bound of the initial problem. Solve benchs/celar/6sub1.ds by removing at most 30 values for each variable domain: example% solaris/vcsp benchs/celar/6sub1.ds 0 -1 8389633 0 penalty 0 0 30 (RDS, var-maxdeg, DomReduc:30, RevOrder) results% optimum= 1852 in 110131 nd, 123781952 ccks, 6.5 sec The domain reduction process generates a file benchs/celar/6sub1.ds_30.mv which contains information about this process. You can reuse this file: example% solaris/vcsp benchs/celar/6sub1.ds 0 -1 1025 0 penalty 0 0 "benchs/celar/6sub1_14val.mv" Another example, with 24 domain reductions: example% solaris/vcsp benchs/celar/6sub1.ds 0 -1 8389633 0 penalty 0 0 24 (RDS, var-maxdeg, DomReduc:24, RevOrder) results% optimum= 2338 in 5304669 nd, 227293092 ccks, 235.2 sec Examples of objective simplifications: -------------------------------------- In these examples, we modify the objective function. Solve benchs/random/15_10_80_80.ds without any simplification: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 -1 9 2 (PFC, var-maxdeg, dom1_deg) results% optimum= 3186 in 76936 nd, 4174190 ccks, 8.7 sec - Add a global upper bound information example% solaris/vcsp benchs/random/15_10_80_80.ds 0 3186 9 2 (PFC, GUB:3186, var-maxdeg, dom1_deg) results% optimum= 3186 in 44149 nd, 2349220 ccks, 5.3 sec - Use an epsilon-approximating Branch and Bound method: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 -1 9 2 penalty 0 0 "" 0 -1 0 1.0 0.5 0.99 -1 0.01 0.95 -1 10 14 -1 "" 0.1 (PFC, e-BB:0.1, var-maxdeg, dom1_deg) results% ub= 3196, lb= 2906 in 65153 nd, 3555101 ccks, 7.5 sec - Modify the valuation aggregation operator: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 -1 9 2 lexico (PFC, operator:Lex, var-maxdeg, dom1_deg) results% optimum= (1000-2 100-10 10-17 1-16) in 76262 nd, 3973493 ccks, 8.8 sec From this result, we can deduce a lower-bound equal to 3000 We can combine several simplifications. For instance, select the lex operator, give GUB information and remove small-cost constraints: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 "(1000-3)" 9 2 lexico 0 "(100-1)" (PFC, operator:Lex, GUB:(1000-3), Cost >= (100-1), var-maxdeg, dom1_deg) results% optimum= (1000-2 100-10) in 2402 nd, 83480 ccks, 0.3 sec From this result, we can deduce a lower-bound equal to 3000 Examples of modified exploration strategies: -------------------------------------------- - Iterative Deepening Solve benchs/random/30_10_50_70.ds with an iterative deepening scheme and a limit on the maximum number of constraint checks: example% solaris/vcsp benchs/random/30_10_50_70.ds 0 -1 2097161 2 penalty 0 0 "" 0 10000000 (PFC, ID, var-maxdeg, dom1_deg, constraint checks:10000000) results% global lower bound= 18 in 73443 nd, 10000063 ccks, 27.4 sec Solve the same problem by multiplying per two the lower bound found at each step of the iterative deepening scheme: example% solaris/vcsp benchs/random/30_10_50_70.ds 0 -1 4194313 2 penalty 0 0 "" 0 10000000 (PFC, ID, x2, var-maxdeg, dom1_deg, constraint checks:10000000) results% global lower bound= 16 in 86587 nd, 10000046 ccks, 20 sec - Iterative Deepening Russian Doll Search example% solaris/vcsp benchs/random/30_10_50_70.ds 0 -1 1025 2 penalty 0 0 "" 0 10000000 1 (RDS, IDRDS_InitDepth:1, var-maxdeg, dom1_deg, constraint checks:10000000) results% global lower bound= 32 in 111493 nd, 10000076 ccks, 19.6 sec For comparison, normal Russian Doll Search produces: example% solaris/vcsp benchs/random/30_10_50_70.ds 0 -1 1025 2 penalty 0 0 "" 0 10000000 (RDS, var-maxdeg, dom1_deg, constraint checks:10000000) results% global lower bound= 10 in 337831 nd, 10002214 ccks, 31.5 sec ------------------------------- Anytime bounding of the optimum ------------------------------- See the following paper for a complete description of the anytime bounding approach used in this software: S. de Givry, G. Verfaillie, and T. Schiex Bounding the Optimum of Constraint Optimization Problems In Proc. of CP-97, pages 405-419, Schloss Hagenberg, Austria, 1997 Our approach is common to ILP solvers, like CPLEX, where a lower bound and an upper bound are produced simultaneously. Solve benchs/random/15_10_80_80.ds without any simplification: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 -1 9 2 (PFC, var-maxdeg, dom1_deg) results% optimum= 3186 in 76936 nd, 4174190 ccks, 8.4 sec Then use the vcsp_anytime application for anytime bounding of the optimum using a complete solving method only: example% solaris/vcsp_anytime benchs/random/15_10_80_80.ds 0 -1 0 -1 9 2 (PFC, var-maxdeg, dom1_deg, Number of SA:0, Initial operator:Or) results% optimum= 3186 in 61077 nd, 2964255 ccks, 6.5 sec Solve benchs/random/20_10_50_50.ds without any simplification using Russian Doll Search: example% solaris/vcsp benchs/random/20_10_50_50.ds 0 -1 1025 2 (RDS, var-maxdeg, dom1_deg) results% optimum= 7 in 766175 nd, 31532438 ccks, 77.1 sec Then use the vcsp_anytime application for anytime bounding of the optimum using a collaboration of a complete solving method (RDS) and two incomplete solving methods (SA): example% solaris/vcsp_anytime benchs/random/20_10_50_50.ds 0 -1 0 -1 1025 2 1.0 0.5 0.99 2 (RDS, var-maxdeg, dom1_deg, Number of SA:2, Initial operator:Or, SA speed:1, TempGeomDecrMin:0.5, TempGeomDecrMax:0.99) results% optimum= 7 in 766557 nd, 32212919 ccks, 84.3 sec Note the decreasing speed of the global upper bound. ------------------------------------ Other local consistency enforcement ------------------------------------ Directed arc consistency enforcement: -------------------------------------- Solve benchs/random/15_10_80_80.ds without DAC: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 -1 9 2 (PFC, var-maxdeg, dom1_deg) results% optimum= 3186 in 76936 nd, 4174190 ccks, 8.4 sec Then use DAC. Note that PFC + DAC implies a static variable order: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 -1 25 0 (PFC, DAC, var-maxdeg) results% optimum= 3186 in 111962 nd, 4426293 ccks, 9.3 sec Compare with DACdyn: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 -1 1048601 0 (PFC, DACdyn, var-maxdeg) results% optimum= 3186 in 24885 nd, 1668271 ccks, 5.9 sec And compare with FullDACdyn: example% solaris/vcsp benchs/random/15_10_80_80.ds 0 -1 68157465 0 (PFC, DACdyn, var-maxdeg) results% optimum= 3186 in 22936 nd, 1561871 ccks, 4.8 sec Arc consistency enforcement on hard constraints: ------------------------------------------------ Solve the CELAR 6sub1.ds problem by maintaining arc-consistency on hard constraints. Add an upper bound information, modify the valuation aggregation operator to the Lex operator and remove small constraints: example% solaris/vcsp benchs/celar/6sub1.ds 0 "(1000-1)" 656385 0 lexico 0 "(100-1)" (RDS, AC3, MAC3, GUB:(1000-1), Operator:Lex, Cost >= (100-1), var-maxdeg) results% optimum= (100-24) in 1442820 nd, 423348168 ccks, 366.3 sec We can only deduce a lower bound equal to 1000. Normal RDS applied without any simplification takes more than two hours to solve the problem. -------------------------------- Save simplified VCSPs into files -------------------------------- You can save a simplified VCSP into file. All the constraints of the resulting saved VCSP are expressed in extension. Extension constraints, compared to equivalent intension constraints, take more memory space but are faster to check during the search. Moreover this "save" feature allows to link the vcsp software to other VCSP softwares. For instance, LVCSP software from Michel Lemaître. For instance, save the CELAR 6sub1 problem after removing constraints with cost smaller than 100 and performing 20 domain reductions: example% setenv SAVEVCSP 1 example% solaris/vcsp benchs/celar/6sub1.ds 0 -1 64 0 penalty 0 100 "benchs/celar/6sub1_24val.mv" example% unsetenv SAVEVCSP (Save VCSP to file, Cost >= 100, DomReduc:benchs/celar/6sub1_20val.mv, no variable order) It produces a file "Celar_6__100.ds" in the current directory.