User Guide and Reference Manual
Contents
1. 8 er 8 How to backtrack 5e mter lea br VEN eS SUE TeY eie Yel ete ve eani eee des e ee EHE 8 Building the Example 2 ert ie etr Ux eee RENE RENE RETURN RE FECE DN AE ERE siouvbesnesestassareaes 11 Solver Extension oro oerte eater bee raten Eee ER vue PEE eV KETENE TE EKEREN EESK TEE ERR T 11 bM 11 Compilation and LINKING M 11 lutei daneben 11 Stand alone Applicat Oi sess ccssesteccsscesecvedsteusisescdsawsestouacedeccsdstensscasessacesscenscedectsccheutenstesdecsdsonedeuwtscudsdedescsoshcnnctecessteressevece 13 DO eXe ke X 13 Compilation atid Linking PY aporte en ERE Pe eee De saseadeuscesveasbaaes 13 E T AE EAE LI 13 Writingia seare OG ss ETE TETTE 16 HWaricrDq 17 Marii us Nterei c M 18 2 KNAPSAGCK CONSTRAINT2. stu Lun ORE RE SERRE 25 SPIELE 26 dum ERE A E 26 IEEE 26 dull ee 26 Key 26 Initializing 27 Filtering Updating cnsscscssssisiensssecscsecesosesessossnsostescedechensvedssnctebedionseasdsssectesoendobendwnoacsetasbestenchtnaendectesesiess 29 Bounds and Thresholds Page 1 CORNFLOWER LIBRARY ETT LE II sagecsevaseuevsosenssecsseseevvedesecpesesucogceseesscedesueede 30 REFERENCE MUG d MIRI UTE EO DEDE 31 PARIS SYMATEIRY BREAKING ur tena tie Sa ru MER aT Un bap o Cre ve Eee Uns voe 39 m H 36 brief OVERVIEW e sussnesetedevsesonsssie ssenedsanssesedencenvestesossucvnceevesecsseseassede esseoss sasseosseesevetseescedeesse 36 36 acl dt 36 Neue AE EE sate 37 Building The Example Using Solver eee eee esee eeee ene e ene ten ente intuens inest tn tatnen sense tnae 38 B
3. a simple branching routine IloMyBranching which selects the variable with the minimum domain size and assigns it to the first value in its domain You can modify IlcGCl file to implement your own branching heuristic solver solve IloMyBranching env variables cfgcPtr incremental Display solution for i 0 i numVariables 1 solver out string solver getAnyValue variable il 6 2 Standalone Application Download cfgc tar gz file from the webpage and unzip it The package includes a precompiled library a file necessary header files cfgc h grammar h and a sample main cpp together with a make file to compile them all All source codes are compiled using g 4 1 on a Linux machine Compilation and Linking Inside the unzipped package type make main to compile In order to link your source codes to our library you can use L option of g compiler If you are using another compiler please refer to its manual Implementation Include the necessary header files lude grammar h lude cfgc h Page 13 CORNFLOWER LIBRARY Construct a grammar The input grammar file must have one production per line and must be in Chomsky Normal Form grammar g input txt Example input file for the language of all correctly bracketed expressions SO SO SO SOAC SOBC B A SO input txt Initialize domains A STL set container is used a domain The doma
4. can cause severe difficulties for exact solvers since we might waste time visiting symmetric solutions and the parts of the search space that we visited already Hence symmetry breaking is crucial for search space exploration We can define two types symmetry A variable symmetry is a bijection on variables that preserves solutions For example consider an all different constraint on a set of variables We can always change any two variable Analogously value symmetry is a bijection on values that preserves solutions Again in our all different example we can freely interchange any two values There are various methods to break symmetries Static symmetry breaking adds static constraints to the problem before the search and dynamic symmetry breaking tries to detect symmetries during search Fahle et al 2001 presents one such dynamic method symmetry breaking by dominance detection SBDD where they filter values based on symmetric dominance analysis when comparing the current node with other previously expanded nodes Sellmann and Hentenryck 2005 devised structural symmetry breaking SSB for problems exhibiting both piecewise symmetric values and variables Static and dynamic SSB was developed in Flener et al 2006 and recently Heller et al 2008 compared static SSB and dynamic SSB in practice It was shown that static SSB works much faster than dynamic counter part However one disadvantage of static SSB is reported to be the variance in
5. level constraints that capture and exploit problem structure However this expressiveness comes at the price that the user must be aware of the constraints that are supported by a solver One way to overcome this problem is by providing highly expressive global constraints that can be used to model a wide variety of problems and that are associated with efficient filtering algorithms A promising avenue in this direction is the introduction of constraints that are based on formal languages which enjoy a wide range of applicability while allowing the user to focus on the desired properties of solutions rather than having to deal for herself with the problem of constraint filtering Sellmann 2006 devises algorithms which perform filtering for context free grammar constraints in polynomial time and Kadioglu and Sellmann 2008 focuses on an incremental filtering algorithm which combines low memory requirements with very efficient incremental behavior 1 Definition For a given grammar alphabet N non terminals P productions So start symbol and variables X X with domains D1 D X1 Dn D Xn we say that 1 is true for an instantiation wi Xn lt if and only if it holds that w w1 wn Lc A Di x x Dn We denote a given constraint over a context free grammar by 1 Sellmann 2006 presents the
6. must be either included or excluded respectively from the knapsack in order to achieve the specified weight and profit thresholds filter is called with references to the two arrays that will hold the indices of the filtered items as well as references to the sizes of these arrays These provided arrays must be allocated to hold twice the number of items in the problem Upon completion the method returns the total number of filtered items Thus to find which items can be filtered from the current knapsack problem the following code can be used Page 27 CORNFLOWER LIBRARY number of items that need to be included ong long numInclude 0 number of items that can be excluded long long numExclude 0 total number of items that can be filtered long long numFilter 0 array to hold the items that need to be included to maintain feasibility long long flnclude long long malloc 2 numItems sizeof long long array to hold items that can be excluded since they will not be part of any feasible solution long long fExclude long long malloc 2 numItems sizeof long 1long filter all possible itmes numFilter kp gt filter fInclude fExclude numInclude numExclude Once filter returns the arrays of items that can be filtered the changes can be applied to the internal representation of the KPF instance through the update function update tak
7. representation of the knapsack problem and filtering items the KPF instance can also be used to inquire about statistics of the current knapsack problem These statistics include the upper bound on the achievable profit and the lower bound on the accumulated weight These values can be extracted by calling getUpperBoundProfit and getLowerBoundWeight respectively as is demonstrated bellow get the upper bound on the achievable profit of the knapsack problem given the items that have been filtered double upperBoundProfit kp getUpperBoundProfit get the lower bound on the achievable weight of the knapsack problem given the items that have been filtered double lowerBoundWeight kp gt getLowerBoundWeight The user can change the thresholds of the knapsack problem being filtered by KPF using setNewThreshold and setNewCapacity Require that a feasible solution have an accumulated profit greater or equal to the current accumulated profit kp setNewThreshold kp gt getTotalProfit Require that a feasible solution have an accumulated weight less than the current accumulated weight kp setNewCapacity kp getTotalWeight Page 29 CORNFLOWER LIBRARY 4 References 1 Yuri Malitsky Meinolf Sellmann Willem Jan van Hoeve Length Lex Bounds Consistency for Knapsack Constraint Proceedings of the 12th intern Conference on the Principles and Practice of Cons
8. runtime when static symmetry breaking constraints clashes with dynamic search orderings or when the static search orderings is not performing well for different problem instances Heller et al 2008 combines static SSB with model restarts to address this problem The details and formal definitions which are omitted here can be found in related papers In Cornflower library we offer a method to apply static SSB given the symmetric partition for values and variables Before we outline static SSB we need to introduce the definition of signature Given a partial assignment A to variables we define a signature for each value as follows Signaturea Value v Variable x x v A isnumber0fvariablePartitions That is given an assignment A the signature of a value v is the tuple that counts for each variable partition the number of variables x that are assigned to the value v Consider the following problem with variables Xi over domains D X vi vs Assume that the first four and the last four variables are symmetric with each other i e P Xi X4 and Xs Xa Further assume that there are two value partitions V vi and va vo Suppose we are given the assignment in Figure 1 Page 35 CORNFLOWER LIBRARY FIGURE 1 Assignment A The signatures for each value are v2 Vi has signature 2 2 ll vi Vi has signature 1 1 Ill ve V2has signat
9. BRARY part of the Tracer that is pointed by the marker Tracer marker considering the changes in reverse order it re creates the removed nodes using their stored information Non Incremental Filtering 1 Create the initial data structure So The figure on the left works bottom up and the picture on the right works top down Left parenthesis is removed from the domain of first variable and right parenthesis is removed from the domain of last variable j j 4 s N 4 s N een EL NIV UND CN EN 1 1 2 3 4 1 1 2 3 4 1 2 Now consider change the domain of third variable The algorithm clears the old data structure So and creates a new data structure 51 Again the left figure works bottom up and the right figure works top down Notice the filtered values from the domains 4A NYO Wo A c bo Page 9 CORNFLOWER LIBRARY Incremental Filtering 1 The initialization part is identical to the non incremental case create the initial data structure So The figure on the left works bottom up and the picture on the right works top down Left parenthesis is removed from the domain of first variable and right parenthesis is removed from the domain of last variable WN wo A c 2 Now when the left parenthesis is removed from the domain of third variable the incremental algorithm removes the corresponding node the node in red circle from So and pr
10. CORNFLOWER LIBRARY October 2008 User Guide Reference Manual CORNFLOWER LIBRARY Table of Contents PREFACE WELCOME CORNFLOW ER issssssssscsssnssesssonvsincinssspesessscnssencsonssenvsonpseuvsaavsensscnoseadsoneventesnoiunesnnssanssazeaeeesais 3 PN orolt BIE To Lairo 1 Meo 3 this mangdi 1S OF GAMIZE c 3 dCICII rg M 4 ballade n 4 OF USE D 4 License Information terrent EEEa a EES rA EA e a EESTE E 4 4 PART 1 CONTEXT FREE GRAMMAR CONSTRAINTS 5 mscvesssicescssnnsnseveriessontessaduroserecesscbassndtouesedsovesseosovasoenessedevesdssasuenedeievascoseassterscebasses ssseseatnsdesssdescosess eosesesicoses bencensasns 6 CFG C mL D 6 CEG G FIG IAG c 6 CEG GC Example ecc 6 Incremental COMPUTATION decetero ettet nete isso preron cbenseteseceieetedsocacesoasbebissessvssneseersesaviiendasoctiusouchevascesebisnteetecnesteceat e 8 Efficient S
11. I IOI 38 Compilations Linking sene erinnere tenete the eoa bna eros eee eee eb eve epe p exe et ence bbscdeonscastseassedseesacesiaestssrevasstvese 38 Died Tue MISERE TALL LIC 38 Refer nC8S E VENUE EPI EVER LEE ESERENE YN SERE ERXEEE YS CREER EVIREEN SE RED EE R REN ERU REN eR Se Eee ve 38 REFERENCE r 41 2 CORNFLOWER LIBRARY Welcome to Cornflower Cornflower Project aims to solve the algorithmic problems that arise in the context of optimization driven decision support systems Our main goal is to develop techniques that allow inexperienced users to exploit optimization power efficiently We integrate and hybridize ideas developed in different communities in order to provide easily accessible high performance optimization technology Particularly we focus on the development of high level constraints that allow users to model the problems as conjunctions of intuitive substructures and provide hybrid methods for their efficient combination Moreover we develop automization techniques for the handling of symmetries that can the cause of severe inefficiencies when handled poorly Cornflower Library makes our algorithms and methods publicly available Read more about Cornflower from our webpage this manu This guide is composed of parts that use an example based learning strategy to illustrate the algori
12. and to prune infeasible values from the domain of lloAnyVar variables Page 18 Constructor Methods CORNFLOWER LIBRARY cfgc grammar g IloSolver s IloAnyVarArray V int n bool incremental string id This constructor creates an instance of grammar constraint to be used as an llog extension Before using it in llog you must wrap it into an llog grammar constraint See also IlcGCl class cfgc grammar g vector set lt sring gt gt variablesPTr string id This constructor creates an instance of grammar constraint to be used for standalone applications public bool propagate This member function is invoked when the incremental algorithm is called When a domain change happens in any of the variables propagation is called You should use that function if you want to modify the llog search goal The method returns true unless the propagation causes an empty domain for some variable public void setMarker Whenever a variable is assigned to a value setMarker is used to create a restore point You should use that function if you want to modify the provided llog search goal The setMarker method indicates the nearest restore point on Tracer data structure which is used to store backtrack information public void backtrack This member is invoked when propagation returns false It restores back the previous state before the propagation using a data structure called Tracer Whenever a node in the gr
13. aph is removed or its supports change the Tracer saves its previous support indices from above and below and the splitting indices to be used later as backtrack information See also setMarker public void filterFromScratch Non incremental filtering algorithm Page 19 CORNFLOWER LIBRARY public void filterFromUpdate public void filterFromUpdate vector lt pair lt int string gt gt affected Incremental filtering algorithm The second function is used in standalone applications It requires an array of domain delta information which stores a variablelndex and pointer to removed value Page 20 GRAMMAR Category Inheritance Path CORNFLOWER LIBRARY Class Definition File grammar h Include File structs h Constructor Summary public grammar string inputfile Method Summary public bool getStatus public int getNumProductions public int getNumTerminals public int getNumNonTerminals public string getTerminal string s public string getDomain int i public string getStartSymbol public void setStartSymbol string s Description This class is used to create an instance from user s grammar input It provides pointers to initialize domains of lloAny variables Page 21 Constructor Methods CORNFLOWER LIBRARY grammar string inputfile This constructor creates an instance of grammar given the input fi
14. e To initialize an instance of the KPF filtering class the constructor needs to be passed information specifying the knapsack problem being solved To describe the knapsack problem the user must specify the number of items an array of weights and profits of each item the maximum allowed weight and the minimum allowed profit The example bellow generates a random knapsack problem and then initializes the KPF instance with this information Page 26 CORNFLOWER LIBRARY set the number of items to be a random value between 20 and 40 int numItems rand 20 20 set the maximum weight threshold to be between 100 and 200 int C 100 100 set the minimum profit threshold int B 0 allocate memory for the weight and profit arrays respectively long long w long long malloc numItems sizeof long long long long p long long malloc numItems sizeof long long generate items randomly where the weights and profits are between 100 and 100 for int 0 ii lt numItems p ii rand 200 100 w ii rand 200 100 initialize KPF KPF kp new KPF numItems w p 3 2 2 Filtering Items and Updating Once the KPF instance is initialized it has all the information about the knapsack problem and calling the filter method will set the passed in arrays to the items that
15. e They can be a smaller subset too IloArray IloIntVarArray gt variables env numVarPartitions for i 0 i lt numVarPartitions i for i 0 lt g getNumTerminals i variables 1 loIntVarArray env partitionSize i minValue maxValue You can decide the order of variable partitions in the value signatures vector lt int gt signatureOrder numVarPartitions signatureOrder 0 signatureOrder 1 Page 38 CORNFLOWER LIBRARY Now you can use static structural symmetry breaking staticSSB env model variables minValue maxValue valPartitionSize SignatureOrder Page 39 CORNFLOWER LIBRARY 1 Daniel Heller Aurojit Panda Meinolf Sellmann Justin Yip Model Restarts for Structural Symmetry Breaking Proceedings of the 14 intern Conference on the Principles nad Prctice of Constraint Programming Springer LNCS 5202 pp 539 544 2008 2 Meinolf Sellmann and Pascal Van Hentenryck Structural Symmetry Breaking Nineteenth International Joint Conference on Artificial Intelligence IJCAI 2005 3 Pierre Flener Justin Pearson Meinolf Sellmann Pascal Van Hentenryck Static and Dynamic Structural Symmetry Breaking Proceedings of he 12 intern Conference on the Principles and Practice of Constraint Programming Springer LNCS 4204 pp 695 699 206 4 Torsten Fahle Stefan Schamberger Meinolf Sell
16. ed documentation the Software be used in a commercial endeavour without the prior expressed permission of Prof Meinolf Sellmann Meinolf_Sellmann brown edu Excluding the above provision permission is hereby granted free of charge to any person obtaining a copy of the Software to deal in the Software for non commercial applications without restriction including without limitation the rights to use copy modify merge publish and to distribute THE SOFTWARE IS PROVIDED AS IS WITHOUT WARRANTY OF ANY KIND EXPRESS OR IMPLIED INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMEN IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM DAMAGES OR OTHER LIABILITY WHETHER IN AN ACTION OF CONTRACT TORT OR OTHERWISE ARISING FROM OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER EALINGS IN THE SOFTWARE I Er Contact You can share your development experience with us through serdark cs brown edu Please let us know for any suggestions and or bug reports Page 4 CORNFLOWER LIBRARY Part CONTEXT FREE GRAMMAR CONSTRAINTS Page 5 CORNFLOWER LIBRARY A major strength of constraint programming is its ability to provide the user with high
17. es in an array of the items to be committed the size of this array and the new statuses of the items The status of the item is set to 1 if the item is being included O if it is being excluded and 1 if the status of the item is undetermined Therefore once we know which items can be filtered by using the above code we can commit these changes by calling update as in the example bellow array of items to be filtered long long filter long long malloc numFilter sizeof long long array of the statuses of the filtered items long long status char malloc numFilter sizeof char record the items that need to be included for int 0 ii lt numInclude filter ii fInclude ii status ii 1 record the items that need to be excluded for int jj 0 jj lt numExclude jjtt filter jj numInclude fExclude jjl status jj numInclude 0 update the kp solver to register the changes kp gt update filter numFilter status Page 28 CORNFLOWER LIBRARY Once the status of an item is set using the above code it can be reverted back to its original undefined status by calling update again this time setting the status to 1 It is therefore important for the user to manually keep a history of all the changes if they want to backtrack as is the case in a branch and bound search 3 2 3 Bounds and Thresholds In addition to maintaining an internal
18. filtering algorithm for CFGCgc which is based on the Cooke Younger Kasami CYK parsing algorithm Given a word of size n let wi denote the sub sequence of letters starting at position i with length j Based on a grammar P So in Chomsky Normal Form CYK determines iteratively the set of all non terminals from where we can derive wi for all 1 lt i n and 1 lt n i It is easy to initialize the sets S just based on w and all productions A wi P Then for from 2 to n and from 1 ton j 1 we have that 5 A gt BC P with B Sik and C Si k j Then a word is in a language if and only if So S1n The algorithm works bottom up by computing sets 5 for increasing after initializing Si with all non terminals that can produce in one step a terminal in the domains of Then the algorithm works top down by removing all non terminals from each set 5 which cannot be reached from So Sin We refer the interested reader to 1 and 7 for many details that are omitted here Assume that we are given a context free normal form grammar and decision variables 2 4 with initial domains D as shown below In Figure 1 we illustrate how our filtering algorithm works First we work bottom up adding non terminals to the sets 5 if they allow generating a word in Di x x Di j 1 Then in the second step we work top down and remove all non terminals that cannot be reached fro
19. gorithm computes which items must be included or excluded in order to satisfy the given constraints A simple example of this would be the algorithm finding that an item is too heavy to be included in any solution or that another item must be included because even combined all other items would not exceed the profit bound Performing this type of filtering can often simplify the problem that needs to be solved by shrinking the number of variables and constraints that need to be considered si An example program that uses the kpf library is provided in the kp tar gz This program creates a small random knapsack problem and solves it using a standard branch and bound approach The following section describe how to set up this example and goes over the main functions explaining how the kpf library can be used Download kp tar gz file from the webpage and unzip it The package includes a precompiled library a file necessary header files kpf h kp h general includes h and a sample solver cpp solver h and main cpp together with a make file to compile them all All source codes are compiled using g 3 3 on a Linux machine Compilation and Linking Inside the unzipped package type make main to compile In order to link your source codes to our library you can use L option of g compiler If you are using another compiler please refer to its manual This section describes the functionality of the methods in the KPF class and their usag
20. graph Variable array is updated when filterFromScratch is called Backtrack The filterFromUpdate method records the necessary information that will allow backtracking to a previous state A restore point can be created by setMarker method before calling filterFromUpdate method Then you can roll back the changes using backtrack method c setMarker variables 2 erase g getTerminal vector lt pair lt int string gt gt affected affected push_back pair lt int string gt 2 g getlIerminal c filterFromUpdate affected c backtrack Display solution for i 0 lt numVariables itt cout Domain var Wut set lt string gt const_iterator iter for iter variables i begin iter variables i end iter cout out string iter Page 15 CORNFLOWER LIBRARY Y E L pr 7 Writing a Search Goal class provides a sample search goal This goal works as follows it selects the variable with the minimum domain size and assigns it the first value in its domain You may want to implement different search goals for your specific problems by modifying IlcMyBranhing method of class When you are using incremental filtering you should invoke setMarker method of cfgc class as you set or remove a value from a variable and you should invoke backtrack and propagate methods of cfgc class in your IlcPropate and IlcBacktrack funct
21. he language of all correctly bracketed expressions SO SO SO SOAC SOBC B A SO A input txt Page 11 CORNFLOWER LIBRARY Initialize domains The domain size is determined by the number of terminals in the grammar The getDomain function returns a pointer for each terminal value to represented in the domain IloAnyArray domain env g getNumTerminals for i 0 i lt g getNumTerminals i domain i IloAny g getDomain i Create decision variables Decision variables are of the type lloAnyVar and they have a set of pointers in their domain to terminal values of the given grammar IloAnyVarArray variables env numVariables for i 0 i numVariables 1 TloAnyVar anyVar env domain Construct CFGC The parameters are grammar g instance of lloSolver lloAnyVarArray decision variables of size numVariables A boolean flag is used to select between incremental and non incremental propagation The last parameter is the constraint id cfgc cfgcPtr new cfgc g solver variables numVariables incremental correctly bracketed CFGC to problem model We wrap our cfgc instance into an constraint using class model add IloGC env variables cfgcPtr incremental Page 12 CORNFLOWER LIBRARY You can introduce additional constraints using operators and Run solver IlcGCl class implements
22. hod computes which items must be included into or excluded from the knapsack in order to satisfy the defined thresholds This function takes in four input parameters all of which are references to variables that are to be set by the function The first parameter is an allocated array of size 2n which will hold the indices of the items that must be included in the knapsack The second parameter is another pre allocated array of size 2n which will hold the indices of the items that cannot be part of a satisfying solution The third and fourth parameters should be set to O and are then set to the number of items in the respective arrays by the function The fifth optional parameter is a Boolean which states whether the found item changes should be automatically committed By default this is set to false The function returns the total number of filtered items or 1 if a feasible solution can t be attained public bool update long long filter long long n char newStatus bool dive false This function changes the status of items of the problem The first parameter is an array of indices of the items whose status needs to be changed The second parameter defines the number of items that need to be changed while the third is a character array that states the new status of the items 1 for inclusion O for exclusion and 1 for undecided The fourth is an optional Boolean parameter meant to be a safety feature that prevents changing the status of ite
23. in size is determined by the number of terminals in the grammar The getDomain function returns a pointer for each terminal value to be represented in the domain set lt string gt domain for i 0 i lt g getNumTerminals i domain insert g getDomain Create decision variables Decision variables are of type STL set which have string values in their domains Precondition The string values in the domains must be terminal values in input the grammar as initialized above vector lt set lt string gt gt variables numVariables domain Construct CFGC The parameters are grammar g number of variables a pointer to the variables and an id for the constraint cfgc c g numVariables amp variables correctly bracketed Page 14 CORNFLOWER LIBRARY Non incremental filtering This method is used to generate the graph in the Figure Whenever a variable is modified you can re call the method again Variable array is updated when filterFromScratch is called c filterFromScratch variables 2 erase g getTerminal c filterFromScratch Incremental filtering You should invoke filterFromScratch method as the first filtering in order to generate the initial graph in the Figurel Then whenever a variable is updated you can store its domain delta and call filterFromUpdate method Here we do not generate a graph again instead we update only the necessary parts of the initial
24. ions Please refer user s manual for details about search goal Page 16 CORNFLOWER LIBRARY 8 References 1 Meinolf Sellmann The Theory of Grammar Constraints Proceedings of the 12th intern Conference on the Principles and Practice of Constraint Programming CP Springer LNCS 4204 pp 530 544 2006 2 Serdar Kadioglu and Meinolf Sellmann Efficient Context Free Grammar Constraints Proceedings of the 23rd National Conference on Artificial Intelligence AAAI pp 310 316 2008 Page 17 CFGC Category Inheritance Path Definition File Include File Class cfgc h grammar h lt il sol ver i losol CORNFLOWER LIBRARY verany h gt lt il sol losol verint h gt ver i Constructor Summary public cfgc grammar g IloSolver s IloAnyVarArray V int n bool incremental string id public cfgc grammar string id Method Summary public bool propagate public void setMarker public void backtrack public void filterFromScratch public void filterFromUpdate public void filterFromUpdate vector pair lt int string gt gt affected Description The class cfgc is at the core of grammar constraints It implements both incremental and non incremental filtering algorithms An instance from grammar class is used as a private member to enforce the production rules
25. ions with four variables each with a domain Below we show how the filtering algorithms construct and maintain the necessary data structures The algorithms differ when an update occurs in one of the variable s domain While non incremental filtering disregards the previous structure and creates new structure from scratch incremental filtering updates only the necessary parts of the initial structure kira As the data structure is created again and again for every decision point in the non incremental algorithm we do not need an explicit backtrack operation However in the incremental case only a subpart of the original structures is changed hence we need a way to undo the changes that we have committed and to restore back to a previous state This is possible by storing extra information whenever a node is removed from any Si notice that that domain filtering monotonically decreases the number of nodes in S A node can be created given its position i j and the production rules that were supporting it from above and below along with their splitting indices Therefore to save space we do not store a node as a whole but only the enough information to create it again This information is stored in a array called Tracer see below A pointer called marker is used to refer the most recent backups in the Tracer Each time a branching decision is made the marker is increased The backtrack method operates on the Page 8 CORNFLOWER LI
26. le The file must contain one production per line The grammar must be context free and in Chomsky Normal Form See sample grammar in the package public bool getStatus Returns true if the grammar object is successfully created public int getNumProdcutions Returns the number of productions in the given grammar public int getNumTerminals Returns the number of terminals alphabet gt in the input grammar The initial domain size for lloAny variables is equal to that number public int getNumNonTerminals Returns the number of non terminal in the input grammar public string getTerminal string s Returns a pointer to the terminal string s in the grammar This member is used when adding extra constraints to problem See the example in section 4 Precondition s is a terminal in the input grammar public string getDomain int i Returns a pointer for the i terminal This member is used to initialize variable domains See the example in section 4 public string getStartSymbol Returns the start symbol So of the grammar The default start symbol is the left hand side production in first line of the input file public void setStartSymbol string s This method can be used to change start symbol if needed Precondition s is a left hand side terminal in the given grammar Page 22 ILCGCI Category Inheritance Path Definition File Include File Description Constructor CORNFLOWER LIBRARY Clas
27. m S Sin We see that the constraint filtering algorithm determines the only word and the domains of the decision variables are filtered accordingly Page 6 CORNFLOWER LIBRARY Language of all correctly bracketed expressions Context Free Grammar G Decision Variables X1 2 3 4 Xi X2 Initial domains 1 The filtering algorithm first works bottom up by computing Da sets 5 for increasing after P initializing Sirwith all non 1G NI terminals that can produce in PN XN one step a terminal in the TY i IN AN T copa 2 3 4 2 Then the algorithm works top down removing all non terminals from each set 5 which cannot be reached from So F e pae 1 2 3 4 i Kadioglu Sellmann AAAI 08 Figure NUNT 7 CORNFLOWER LIBRARY i on 4 L One way to speed up filtering algorithms is to incorporate mechanism for incremental update of important data structures In fact the filtering algorithm is often applied with slightly changed domain information Therefore it is desirable that the data structures built during the first filtering operation are maintained dynamically without building them again for each subsequent run Specifically we consider the incremental grammar constraint filtering in this section In Figure 1 we observe that the algorithm first works bottom up determining from which non terminals of
28. mann Symmetry Breaking Proceedings of the 7 intern Conference on the Principles and Practice of Constraint Programming CP Springer LNCS 2239 pp 93 107 2001 Page 40 staticSSB Category Inheritance Path Definition File Include File CORNFLOWER LIBRARY Class staticSSB h lt ilsolver ilosolverint h gt Method Summary public void staticSSB amp IloEnv amp lIloModel IloArray IloIntVarArray variables int minValues int maxValues vector lt int gt valPartitionSize signatureOrder Description Methods d T 558 method MET INNER public void staticSSB amp IloEnv amp lloModel IloArray IloIntVarArray variables int minValue int maxValue vector lt int gt valPartitionSize signatureOrder This method modifies a given llog Environment and Model based on the provided variable and value partitions The method starts by updating the model with static less than or equal constraints within each variable partition to break variable symmetries Then it uses global cardinality constraint GCC to obtain the cardinality information of the each value within each variable partition Signatures are formed for each value using the cardinalities and finally lexicographic constraints are added to the model for each value partition to break value symmetries The user has the option to decide on the ordering of variable partition in
29. ms that have already been set to be either included or excluded By default this parameter is set to false The update functions returns true if all updates were successful and false otherwise Setting an item to a state it s already in does not change the state of the problem Page 32 CORNFLOWER LIBRARY public bool upperBoundProfit void Returns true if the relaxed solution is integer public double getLowerBoundWeight void Returns the lower bound on the weight for the current partial assignment public double getUpperBoundProfit void Returns the upper bound on the profit on the current partial assignment public void setNewThreshold long long t Sets the new threshold on the knapsack such that the gained profit is greater or equal to the passed in variable public void setNewCapacity long long t Sets the new capacity on the knapsack such that the accumulated weight is smaller or equal to the passed in variable public long long getTotalWeight void Returns the total accumulated weight of the items included in the current partial assignment public long long getTotalProfit void Returns the sum profit of the included items in the current partial assignment Page 33 CORNFLOWER LIBRARY Part Ill SYMMETRY BREAKING Page 34 CORNFLOWER LIBRARY Symmetries occur naturally in many problems i e two identical flights to operate or rotation and reflection symmetries in magic square problem and
30. opagates the effect of this removal up the nodes in blue circle and down the nodes in green circle As the nodes are removed backup information is stored in Tracer At each decision point the marker is shifted to right When backtrack is invoked the nodes in Tracer marker is re created and marker is shifted to left G B A Marker 1 Page 10 CORNFLOWER LIBRARY Building the example 6 1 llog Solver Extension Download cfgc tar gz file from the webpage and unzip it The package includes a precompiled library a file necessary header files cfgc h grammar h IlcGCl h and a sample main cpp together with a make file to compile them all All source codes are compiled using g 4 1 and llog Solver 6 4 on a Linux machine Compilation and Linking Inside the unzipped package type make main to compile You have to change SOLVERDIR parameter in the make file to your own llog Solver directory In order to link your source codes to our library you can use L option of g compiler If you are using another compiler please refer to its manual Implementation Include the necessary header files grammar h Vein Cie bi T1lcGCI h lt ilsolver ilosolverany h gt Construct a grammar The input grammar file must have one production per line and must be in Chomsky Normal Form grammar g input txt Example input file for t
31. s IlcGCI h lt ilsolver ilosolverint h gt lt ilsolver ilosolverany h gt Constructor Summary public IloGC IloSolver s IloAnyVarArray V cfgc c bool incremental Method Summary public void propagate ILCGOAL2 backtrack This class is used to convert a grammar constraint into an llog grammar constraint IloSolver s IloAnyVarArray V cfgc c bool incremental This constructor creates an instance of llog grammar constraint given an llog solver decision variables actual grammar constraint and a flag to filter incremental or not lloGC is a wrapper used around class Page 23 CORNFLOWER LIBRARY Methods public void propagate This method invokes an llog fail if grammar constraint filtering returns failure ILCGOAL2 backtrack This method invokes an llog fail If you choose to filer incrementally it makes a call to backtrack method of cfgc class Page 24 CORNFLOWER LIBRARY Part 11 KNAPSACK CONSTRAINT Page 25 CORNFLOWER LIBRARY Definition For a given set of items each with a weight and a profit pi find the subgroup SC such that the total profit of the included items is greater than some threshold B and the accumulated weight of the included items is less than or equal to another threshold C Given the knapsack problem and the thresholds the filtering al
32. the grammar we derive a legal word Then it works top down determining which non terminal nodes can be used in a derivation that begins with start symbol So Sin In order to save both space and time we will modify these two steps such that every non terminal in each set Sij will perform just enough work to determine whether its respective node will remain in the shrunken graph To this end in the first step that works bottom up we will need a routine that determines whether there exists a support from below That is this routine determines whether a node has any outgoing arcs Analogously in the second step that works top down we will rely on a procedure that checks whether there exists a support from above Formally this procedure determines whether a node has any incoming arcs The challenge is to avoid having to pay with time what we save in space To this end we need a methodology which prevents us from searching for supports from above or below that have been checked unsuccessfully before Very much like the well known arc consistency algorithm AC 6 for binary constraint problems we achieve this goal by ordering potential supports so that when a support is lost the search for a new support can start right after the last support in the respective ordering We refer the interested reader to Sellmann 2006 and Kadioglu and Sellmann 2008 for many details that are omitted here Consider our previous example of correctly bracketed express
33. the signatures Page 41 he variak
34. thms implemented in Cornflower Library Each part is build around a sample problem and a user works on partially completed code examples Then you can compile the final code and run and analyze the results At the end of each part there is a reference manual for the available methods The manual is designed to be used by C programmers who may or may not have any knowledge of high level constraints hybrid methods and symmetry breaking The ideal usage context for this manual is to work through the examples step by step with Cornflower Library downloaded in your computer This manual is divided into three parts Part Context Free Grammar Constraints Part Il Knapsack Constraint Part Ill Symmetry Breaking Page 3 CORNFLOWER LIBRARY Prerequisites The Cornflower library requires knowledge of C without exposing any syntactic extension You should have required header files and libraries downloaded before using the manual Website http cs brown edu research cornflower Terms of Use You may use the available software without limitation for academic purposes We kindly request you to cite our related publication s if you use Cornflower in your research If you wish to use the software for commercial applications please obtain the prior permission of Prof Meinolf Sellmann License Information LICENSE Copyright c 2008 Brown University Under no circumstances shall this software and associat
35. traint Programming CP Springer LNCS 5202 pp 266 281 2008 Page 30 KPF Category Inheritance Path Definition File Include File CORNFLOWER LIBRARY Class kpf h kp h Constructor Summary public KPF long long n long long weight long long profit long long C long long B Method Summary public long long filter long long filterl long long filter long long amp filteredAlreadyl long long amp filteredAlreadyO bool noCommit true public bool update long long filter long long n char newStatus bool dive false public bool upperBoundProfit void public double getLowerBoundWeight void public double getUpperBoundProfit void public void setNewThreshold long long t public void setNewCapacity long long c public long long getTotalWeight void public long long getTotalProfit void Page 31 Description Constructor Methods CORNFLOWER LIBRARY The KPF class provides the interface to the KP class enforcing all the production filtering and bounding rules KPF long long n long long weight long long profit long long C long long B This constructor creates an instance of the knapsack problem public long long filter long long filterl long long filter0 long long amp filteredAlreadyl long long filteredAlreadyO bool noCommit true The met
36. ure 1 1 4 Static SSB As shown in Flener et al 2006 we can use the signature abstraction to devise a linear set of constraints which provably leaves only one solution in each equivalence class of solutions We break the symmetries as follows l break variable symmetry we force the variables with smaller indices to take smaller or equal values within each variable partition ll To break value symmetry we use the signature of values in complete assignments Within each value partition we require that smaller values have lexicographically larger or equal signatures than larger values This is accomplished by using the global cardinality constraint GCC which counts how many times a value is taken by a given set of variables Page 36 CORNFLOWER LIBRARY For the example above we introduce constraints 1 11 to break variable symmetry and constraints III VI to break value symmetry l Il Il IV V VI Xi X2 X3 Xa X5 Xe X7 GCC X1 X2 vi v2 V4 V5 Ve cardvi cardv2 cardy3 cardy4 cards cardye GCC Xs Xe X7 v1 v2 Va v5 ve Cardy12 cardy22 cardy32 cardy4 cardys2 2 card i Zex cardy 22 S1ex cardys card cardy4 cardy42 Zigx cardys cardys2 Zex cardys 62 5 Building the example using llog Solver Download ssbb tar gz file from the
37. webpage and unzip it The package includes a precompiled library a file necessary header files staticSSB h and a sample main cpp together with a make file to compile them all All source codes are compiled using g 4 1 and Solver 6 4 on a Linux machine Compilation and Linking Inside the unzipped package type make main to compile You have to change SOLVERDIR parameter in the make file to your own llog Solver directory In order to link your source codes to our library you can use L option of g compiler If you are using another compiler please refer to its manual Implementation Include the necessary header files include staticSSB h Declare the size of variable partitions int numVarPartitions 2 vector lt int gt varPartitionSize numVarPartitions varPartitionSize 0 varPartitionSize 1 Declare the size of value partitions Page 37 CORNFLOWER LIBRARY int numValPartitions 2 vector lt int gt valPartitionSize numValPartitions valPartitionSize 0 3 valPartitionSize 1 Declare the minimum and the maximum value that is possible among the domains of all variables int minVa int maxVal Define an llog environment model and solver loEnv env loModel model loSolver solver model Create decision variables The domains of the variables not necessarily have to be between the minimum and the maximum valu
Download Pdf Manuals
Related Search