What is the best way to implement Breadth-First Search (BFS) in JaCoP?
Here is what I would like to do in particular. I have divided my decision variables into groups (or "clusters," or whatever you want to call them): in the first group are high-level decisions, in the second group are slightly lower-level decisions that are constrained by the decisions made for the first group, etc. I would like to first search over the whole search space of the first group, computing for each solution a lower bound and an upper bound on the cost variable. Then I start with the most promising partial solution found (the one with the lowest lower bound on the cost), and start the search on the second group of variables, etc. After completing the search on group i, I would be able to revise the bounds on the corresponding partial solution in the groups j<i.
Am I making sense, and is it possible to achieve this using JaCoP without too much trouble?
Thanks a lot in advance,
Thomas
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Search functionality is one of the strongest aspects in JaCoP (after global constraints), so what you are asking for is possible.
You need to play with nested search. If I remember correctly, MUCA example is using nested search. You may also find usefull different indomains like IndomainList or IndomainHierarchical. Moreover, you may find interesting that you can provide search with your own SelectChoicePoint and return a choice primitive constraint instead of variable value pair. Thus, you branches may be based on any arbitrary primitive constraint not just assignment constraints (e.g. x = 4).
best,
Radek
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
In my opinion it is too much trouble to implement BFS. There is several reasons for that. First, to start several search branches in BFS you need to provide a fresh copy of store for each branch, that means you need to clone the state of the solver for each branch. This copy includes a copy of current domains for all finite domain variables but also a copy of all constraints that have state ( for example, diff2). This means the memory will grow exponentially when search will progress. Moreover, you need to implement correctly all clone methods ;) Second, the result is not clear and it is not sure you will get better results.
If you want to implement stages in you search, that is first assign variables of a special kind and then other variables, you may use sequential search (http://jacopguide.osolpro.com/guideJaCoP.html#x1-480005). This will be still DFS but you may introduce some order in your search. I would propose this solution for you.
Best regards,
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Thanks for your answers.
The reason I am asking this is because I am able to quickly produce a first solution of mediocre cost (which I am currently trying to improve using better value selection heuristics), but after that the DFS search wastes a lot of time deep in the search tree making minor changes that result in only minor cost improvements, or no cost improvements at all.
How can I make sure the search backjumps faster to higher in the tree, where other branches start with higher potential cost gains?
Thanks for your suggestions,
Thomas
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
You can use search methods that are not complete, that is they artificially stop searching after reaching a specific conditions. In section 5.3 (http://jacopguide.osolpro.com/guideJaCoP.html#x1-460003) we describe credit search and in section 5.4 limited discrepancy search (http://jacopguide.osolpro.com/guideJaCoP.html#x1-470004). You can also build your own methods using search plug-ins. For example, you can stop search after number of backtracks.
In this case, however, you will not prove optimality, of course.
Best regards,
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hi,
What is the best way to implement Breadth-First Search (BFS) in JaCoP?
Here is what I would like to do in particular. I have divided my decision variables into groups (or "clusters," or whatever you want to call them): in the first group are high-level decisions, in the second group are slightly lower-level decisions that are constrained by the decisions made for the first group, etc. I would like to first search over the whole search space of the first group, computing for each solution a lower bound and an upper bound on the cost variable. Then I start with the most promising partial solution found (the one with the lowest lower bound on the cost), and start the search on the second group of variables, etc. After completing the search on group i, I would be able to revise the bounds on the corresponding partial solution in the groups j<i.
Am I making sense, and is it possible to achieve this using JaCoP without too much trouble?
Thanks a lot in advance,
Thomas
Hi,
Search functionality is one of the strongest aspects in JaCoP (after global constraints), so what you are asking for is possible.
You need to play with nested search. If I remember correctly, MUCA example is using nested search. You may also find usefull different indomains like IndomainList or IndomainHierarchical. Moreover, you may find interesting that you can provide search with your own SelectChoicePoint and return a choice primitive constraint instead of variable value pair. Thus, you branches may be based on any arbitrary primitive constraint not just assignment constraints (e.g. x = 4).
best,
Radek
Hi,
In my opinion it is too much trouble to implement BFS. There is several reasons for that. First, to start several search branches in BFS you need to provide a fresh copy of store for each branch, that means you need to clone the state of the solver for each branch. This copy includes a copy of current domains for all finite domain variables but also a copy of all constraints that have state ( for example, diff2). This means the memory will grow exponentially when search will progress. Moreover, you need to implement correctly all clone methods ;) Second, the result is not clear and it is not sure you will get better results.
If you want to implement stages in you search, that is first assign variables of a special kind and then other variables, you may use sequential search (http://jacopguide.osolpro.com/guideJaCoP.html#x1-480005). This will be still DFS but you may introduce some order in your search. I would propose this solution for you.
Best regards,
/Kris
Hi Radek and Kris,
Thanks for your answers.
The reason I am asking this is because I am able to quickly produce a first solution of mediocre cost (which I am currently trying to improve using better value selection heuristics), but after that the DFS search wastes a lot of time deep in the search tree making minor changes that result in only minor cost improvements, or no cost improvements at all.
How can I make sure the search backjumps faster to higher in the tree, where other branches start with higher potential cost gains?
Thanks for your suggestions,
Thomas
Hi!
You can use search methods that are not complete, that is they artificially stop searching after reaching a specific conditions. In section 5.3 (http://jacopguide.osolpro.com/guideJaCoP.html#x1-460003) we describe credit search and in section 5.4 limited discrepancy search (http://jacopguide.osolpro.com/guideJaCoP.html#x1-470004). You can also build your own methods using search plug-ins. For example, you can stop search after number of backtracks.
In this case, however, you will not prove optimality, of course.
Best regards,
/Kris