I use a lot of intermediary IntVar ( like a * a ) in my model and I don't care about their values ( of course, they are added to the store).
Do I need / should I present these to DepthFirstSearch call anyway ? I seem to get correct results either way, but I was wondering if the choice to include/not to include intermediary vars in the search has any consequence ( including performance-wise).
Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Formally, you csan only be sure that the result is correct if all FDVs get a single value but ... in many pratcial cases intermediate variables get values by propagation. This is probably the case for your exasmple. If you give a value to a then a * a will propagate. I think a good idea is to print the store when you get a solution and check if all variables get a value. Alternatively you can add a slave search that gives values to all intermediate variables.
Best,
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
In general, the search will take longer time since we need to label more variables. This "overhead" is problem specific and it might be very small or very large.
Note, however, that in special situations, when the solution found by labeling variables specified by the programmer is not part of the correct solution, the additional search might be long to find this situation and return to the original search.
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hi Kris, thank you
I don't quite understand the second paragraph in your reply.
"when the solution found by labeling variables specified by the programmer is not part of the correct solution.. "
How can that happen. I would have thought, that the variables that I submit to the search like this:
SelectChoicePoint<IntVar> select = new InputOrderSelect<IntVar>(s, toArray(ivs), new IndomainMin<IntVar>());
will always contain the correct solution after the search (by correct I understand not necessarily the optimal solution but at least one coherent solution )
Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
In this paragraph I talk on possible situation that might happen for not very careful programmers. Regarding your example, it depends what you will include in vector s. If you only, for example, include only part of decision variables it might happen that other decision variables do not get a single value (by propagation) and even worse, the other variables might not have in their domains possible correct values.
Best,
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
So to resume: If I want to be sure that the result I get is a coherent solution, I need to include all FDVs in the search, even if this might increase the search time.
If this turns out to be too much overhead, I must check after the search if constraint propagation has reached all variables to make sure that the result is correct.
And to resume even more: always include all FDVs in the search unless the performance hit is not acceptable.
Is this correct ?
Thanks, Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
The performance overhead will not be so high if all FDVs in the "additional" search are ground (got a value by propagation). In this case we basically check them and skip them in search.
Good luck with your problem,
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Might I suggest one thing: When using a custom CostListener as explained on pp. 51 of the guide, I found it confusing that the returnCode is not honoured unless I say:
search.respectSolutionListenerAdvice = true;
First, this is a public field while most other fields have their setters. Second its not on the Search interface but only in its subclass DepthFirstSearch. In my problem, the best ( minimal cost) solution is often not the first one, but rather the fifth or six one. So, I find it important to be able to say:
get me 6 solutions or timeout.
For this , the returnCode must be honoured.
Maybe something for the guide ?
Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Thanks for your comment. We have introduced this boolean variable to limit number of the solutions, specially for sequence of searches. It is not really reflected in the Guide. Thanks.
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
In the meantime I have refactored and all vars are presented to the SelectChoicePoint. Now I have noticed that apparently the order in which vars are presented does matter. For example:
(a1, a2, ,,, an, b1, b2, ... bn)
has a solution but:
(b1, b2, ,,, bn, a1, a2, ... an)
has not. Is this possible ?
Thanks, Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Yes, the order matters, specially if you use InputOrder variable selection heuristic. Try other heuristics, such as SmallestDomain or MostConstrainedStatic. Since the variable are selected based on specific criteria during search they are less dependent by the orde rof variables.
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Only InputOrderSelect works on all my problems, provided that I present the vars in the "right" order. Is there some theory / paper that I could read to better understand that, since this seems to be a killer problem ? Also, I feel that this problem should appear big in the guide. I only discovered this by chance because the first ordering I used happened to work and I already had unit tests in place. Otherwise I would have put the validity of my model in doubt, rather than choosing different parameters for the search operation itself. Maybe a newbie trap ?
Thanks, Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I just put one longer response concerning your questions Peter.
First, CP is often used to model and solve NP-complete and NP-hard problems. I assume your problem belongs to one of these. For those classes of problems finding the right search approach is something that even CP experts after years of experience will need to apply trial and see approach.We will have some hunches when we see actual problem but the only way to get good at it is to see existing solutions to similar problems and try different searches for your own problem.
There are no good answers to your question of what is a good search and why you see the difference in search performance except generic ones that Kris tried to provide. Yes the order does matter and if you get the best order you can find solutions in seconds provided you have a good model too and if you have bad search order a good model may still not be enough to find answer in days or longer. Sorry, this comes with a territory of NP-complete and NP-hard problems. This is why we tried to provide some means to tailor your own search. I really recommend looking into master-slave search examples as often for serious applications of CP (larger problems, more difficult domain) we need to apply this approach.
If one could come up with a method to find the best search approach for any problem from any of these classes would probably get Alan Turing award if not Nobel price in math. No kidding.
You asked a question is it possible to have a solution for one search and no solution for the other search. Actually, the answer needs to be made more precise. If both searches are complete (namely they explore the whole depth-first-search tree) and both use the same complete set of variables then it is NOT possible. Only, if at least one of the searches is incomplete (e.g. LDS) then it is possible.
CP main feature is to apply incomplete consistency algorithms ( here incomplete meaning that there may be no solution but CP solver will not be able to tell you unless you have grounded all variables). This feature is one of the main reasons for CP to exist and flourish. The effect that you may get "solution" because you forgot to ground all variables is common mistake even among experts because they were not aware that solver has created some extra variables behind the scene. This is why it is good to print store during your adventure ;D with figuring out the right model and search for your problem to make sure that you are not sent in a wrong direction because you think you have a quick search for finding a solution but it is actually not a solution.
Hope that my different take at your question will help you. Thank you for your remarks how we can improve JaCoP.
all the best,
Radek
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I just realized that you have two "types" of variables. Variables a_i and b_i. It might be good to use in such case sequence of searches. First on varibales a and then on variables b. For example, the search can be defined as below.
Search<IntVar> slave = new DepthFirstSearch<IntVar>();
SelectChoicePoint<IntVar> selectSlave =
new SimpleSelect<IntVar>(varsB,
new SmallestMin<IntVar>(),
new SmallestDomain<IntVar>(),
new IndomainMin<IntVar>());
slave.setSelectChoicePoint(selectSlave);
Search<IntVar> master = new DepthFirstSearch<IntVar>();
SelectChoicePoint<IntVar> selectMaster =
new SimpleSelect<IntVar>(varsA,
new SmallestMin<IntVar>(),
new SmallestDomain<IntVar>(),
new IndomainMin<IntVar>());
master.addChildSearch(slave);
boolean result = master.labeling(store, selectMaster);
Of course, the variable selection heurostocs are only an example of possible methods.
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Rado, Kris
Thank you very much for your detailed comments and suggestions. For me, they greatly simplify the first steps in the realms of CP. I initially thought that CP is all about modelling your problem in terms of constraints (drawing from the nice "library" that Jacop offers) and that the search part - at least for "small" problems - is an afterthought, much like when you use a SQL database. In traditional SQL (or no-sql), once your problem is modelled in terms of entities and relationships (or objects), you are garanteed to get an answer "immediately" ( at least for small problems). The answer is always either wrong of right, depending solely on your model.
I now understand that this is different in CP, and the reason is that we are addressing a different set of problems ( NP ). Therefore, at least two steps are involved:
. modelling the problem in terms of constraints , this is what most books I have seen are focusing on,
. defining an appropriate search strategy, this in turn might have an impact on the model itself.
For the latter part, I will certainly follow your advice to analyze master-slave strategies and I will have a look at code.
By the way, what I try to build is an automatic placement and routing system for electronic circuits. The task consists in placing components ( rectangles ) and wires (lines) such as there are no overlaps and crossings. Also, components should be nicely aligned. The cost function is a weighted sum of required board space and total wire length. Very exciting !
Again thanks for your help
Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
You may also check SimpleMatrixSelect where you can specify an array of variables (vector of vectors) and select the whole sub-vector for labeling.
Your problem conatin symmetries that you may eliminate to get faster proof of optimality. There is several methods to do that. A simple one fixes, for example, one rectangle, into left top "quarter" of the ålacement space.
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Kris, I will checkout the example that uses SimpleMatrixSelect. And yes, I get faster results when I restrict the placement space like you suggested.
I think that the main problem for the moment is the way I detect overlaps and crossings.
There are at least two strategies:
. use a pairing function (Matthew Szudzik Wolfram Research, Inc) to get a unique hash for every coordinate on the rectangle borders and for each point of each wire. Then I can say AllDistinct. The problem is that I get into thousands of vars even for small problems. This is what I have currently. It works for small settings ( up to 10 components, for the moment I have no wires) but I am afraid it could blow up when I add wires. The problem size will never be much more than 10 components, because I group them into modules and treat each module as a black box in the next step. So it still seems a realistic approach, especially once I better understand how search is done. Computation time is less than 10 secs.
. use a try and error strategy.: get a first solution and allow crossings, detect the crossing and iteratively add constraints ( XneqY), restart search until there are no more crossings. The example of p.51 of the guide seems to be suitable for this. From other threads I read on this group, I got the impression though that this strategy is a bit "un-CP" , but maybe I misunderstood. Anyway, will give it a shot.
Thanks
Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Please use Alldiff instead of Alldistinct. Alldistinct is usable only for specific tailored problems like larger Sudoku etc, but too often gives too little for the extra amount of work it requires. 95% of the cases Alldiff will be more than enough.
best,
Radek
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
The impact depends on the problem but Alldistinct requires more computations and the complexity of the involved algorithms is higher. Alldistinct has complexity O(n^2.5) since it involves bipartite graph matching and Alldiff compxity of our impelemntation is O(n^2). Of course, there are some constants involved that for small lists of variables plays a significant role ;)
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
What would be the appropriate way to incrementally add constraints after each depth-first-search ? Is p.51 (restart search) the way to go, or is this done with the master-slave setting ? I couldn't find such a process in the examples.
Thanks, Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
First of all adding constraints incrementally is not typical way to model CP propblems ;) Saying that I can add that it is possible to add constraints before and under search. The method you refer to addresses the first case. You add new constraint and all the added constraints are considered by the solver. The second method, adding constraints, under search, is more complicated. Basically in each decision point you can add constraints. They will be valid on higher search levels and will disappear on lower levels of search (when backtracking to previous decisions). In fact one can organize the search using this method. Practially, the easiest way to do it is to use search plug-ins, I think.
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
First of all adding constraints incrementally is not typical way to model CP propblems
This is indeed what I read in another thread. Why is that so ? I think the guide explains that for example minimization is achieved by adding a new constraint after each seach:
Each time a solution with cost costValue is found a constraint cost < costV aluei is imposed.
Peter
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
The typical way to model CP problems is to define all constraints and find a slution or solutions. The definition of restart search does not change the model, it only constraints the cost.
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I use a lot of intermediary IntVar ( like a * a ) in my model and I don't care about their values ( of course, they are added to the store).
Do I need / should I present these to DepthFirstSearch call anyway ? I seem to get correct results either way, but I was wondering if the choice to include/not to include intermediary vars in the search has any consequence ( including performance-wise).
Peter
Formally, you csan only be sure that the result is correct if all FDVs get a single value but ... in many pratcial cases intermediate variables get values by propagation. This is probably the case for your exasmple. If you give a value to a then a * a will propagate. I think a good idea is to print the store when you get a solution and check if all variables get a value. Alternatively you can add a slave search that gives values to all intermediate variables.
Best,
/Kris
So, is there any downside in systematically including all vars ( including intermediate ones) in the search ?
Peter
In general, the search will take longer time since we need to label more variables. This "overhead" is problem specific and it might be very small or very large.
Note, however, that in special situations, when the solution found by labeling variables specified by the programmer is not part of the correct solution, the additional search might be long to find this situation and return to the original search.
/Kris
Hi Kris, thank you
I don't quite understand the second paragraph in your reply.
"when the solution found by labeling variables specified by the programmer is not part of the correct solution.. "
How can that happen. I would have thought, that the variables that I submit to the search like this:
SelectChoicePoint<IntVar> select = new InputOrderSelect<IntVar>(s, toArray(ivs), new IndomainMin<IntVar>());will always contain the correct solution after the search (by correct I understand not necessarily the optimal solution but at least one coherent solution )
Peter
Hi Peter,
In this paragraph I talk on possible situation that might happen for not very careful programmers. Regarding your example, it depends what you will include in vector s. If you only, for example, include only part of decision variables it might happen that other decision variables do not get a single value (by propagation) and even worse, the other variables might not have in their domains possible correct values.
Best,
/Kris
So to resume: If I want to be sure that the result I get is a coherent solution, I need to include all FDVs in the search, even if this might increase the search time.
If this turns out to be too much overhead, I must check after the search if constraint propagation has reached all variables to make sure that the result is correct.
And to resume even more: always include all FDVs in the search unless the performance hit is not acceptable.
Is this correct ?
Thanks, Peter
Right!
The performance overhead will not be so high if all FDVs in the "additional" search are ground (got a value by propagation). In this case we basically check them and skip them in search.
Good luck with your problem,
/Kris
Thanks Kris, I appreciate your help.
Might I suggest one thing: When using a custom CostListener as explained on pp. 51 of the guide, I found it confusing that the returnCode is not honoured unless I say:
First, this is a public field while most other fields have their setters. Second its not on the Search interface but only in its subclass DepthFirstSearch. In my problem, the best ( minimal cost) solution is often not the first one, but rather the fifth or six one. So, I find it important to be able to say:
Peter
Thanks for your comment. We have introduced this boolean variable to limit number of the solutions, specially for sequence of searches. It is not really reflected in the Guide. Thanks.
/Kris
In the meantime I have refactored and all vars are presented to the SelectChoicePoint. Now I have noticed that apparently the order in which vars are presented does matter. For example:
(a1, a2, ,,, an, b1, b2, ... bn)has a solution but:
(b1, b2, ,,, bn, a1, a2, ... an)has not. Is this possible ?
Thanks, Peter
Yes, the order matters, specially if you use InputOrder variable selection heuristic. Try other heuristics, such as SmallestDomain or MostConstrainedStatic. Since the variable are selected based on specific criteria during search they are less dependent by the orde rof variables.
/Kris
Only InputOrderSelect works on all my problems, provided that I present the vars in the "right" order. Is there some theory / paper that I could read to better understand that, since this seems to be a killer problem ? Also, I feel that this problem should appear big in the guide. I only discovered this by chance because the first ordering I used happened to work and I already had unit tests in place. Otherwise I would have put the validity of my model in doubt, rather than choosing different parameters for the search operation itself. Maybe a newbie trap ?
Thanks, Peter
Hi,
I just put one longer response concerning your questions Peter.
First, CP is often used to model and solve NP-complete and NP-hard problems. I assume your problem belongs to one of these. For those classes of problems finding the right search approach is something that even CP experts after years of experience will need to apply trial and see approach.We will have some hunches when we see actual problem but the only way to get good at it is to see existing solutions to similar problems and try different searches for your own problem.
There are no good answers to your question of what is a good search and why you see the difference in search performance except generic ones that Kris tried to provide. Yes the order does matter and if you get the best order you can find solutions in seconds provided you have a good model too and if you have bad search order a good model may still not be enough to find answer in days or longer. Sorry, this comes with a territory of NP-complete and NP-hard problems. This is why we tried to provide some means to tailor your own search. I really recommend looking into master-slave search examples as often for serious applications of CP (larger problems, more difficult domain) we need to apply this approach.
If one could come up with a method to find the best search approach for any problem from any of these classes would probably get Alan Turing award if not Nobel price in math. No kidding.
You asked a question is it possible to have a solution for one search and no solution for the other search. Actually, the answer needs to be made more precise. If both searches are complete (namely they explore the whole depth-first-search tree) and both use the same complete set of variables then it is NOT possible. Only, if at least one of the searches is incomplete (e.g. LDS) then it is possible.
CP main feature is to apply incomplete consistency algorithms ( here incomplete meaning that there may be no solution but CP solver will not be able to tell you unless you have grounded all variables). This feature is one of the main reasons for CP to exist and flourish. The effect that you may get "solution" because you forgot to ground all variables is common mistake even among experts because they were not aware that solver has created some extra variables behind the scene. This is why it is good to print store during your adventure ;D with figuring out the right model and search for your problem to make sure that you are not sent in a wrong direction because you think you have a quick search for finding a solution but it is actually not a solution.
Hope that my different take at your question will help you. Thank you for your remarks how we can improve JaCoP.
all the best,
Radek
Hi!
I just realized that you have two "types" of variables. Variables a_i and b_i. It might be good to use in such case sequence of searches. First on varibales a and then on variables b. For example, the search can be defined as below.
Search<IntVar> slave = new DepthFirstSearch<IntVar>();
SelectChoicePoint<IntVar> selectSlave =
new SimpleSelect<IntVar>(varsB,
new SmallestMin<IntVar>(),
new SmallestDomain<IntVar>(),
new IndomainMin<IntVar>());
slave.setSelectChoicePoint(selectSlave);
Search<IntVar> master = new DepthFirstSearch<IntVar>();
SelectChoicePoint<IntVar> selectMaster =
new SimpleSelect<IntVar>(varsA,
new SmallestMin<IntVar>(),
new SmallestDomain<IntVar>(),
new IndomainMin<IntVar>());
master.addChildSearch(slave);
boolean result = master.labeling(store, selectMaster);
Of course, the variable selection heurostocs are only an example of possible methods.
/Kris
Rado, Kris
Thank you very much for your detailed comments and suggestions. For me, they greatly simplify the first steps in the realms of CP. I initially thought that CP is all about modelling your problem in terms of constraints (drawing from the nice "library" that Jacop offers) and that the search part - at least for "small" problems - is an afterthought, much like when you use a SQL database. In traditional SQL (or no-sql), once your problem is modelled in terms of entities and relationships (or objects), you are garanteed to get an answer "immediately" ( at least for small problems). The answer is always either wrong of right, depending solely on your model.
I now understand that this is different in CP, and the reason is that we are addressing a different set of problems ( NP ). Therefore, at least two steps are involved:
. modelling the problem in terms of constraints , this is what most books I have seen are focusing on,
. defining an appropriate search strategy, this in turn might have an impact on the model itself.
For the latter part, I will certainly follow your advice to analyze master-slave strategies and I will have a look at code.
By the way, what I try to build is an automatic placement and routing system for electronic circuits. The task consists in placing components ( rectangles ) and wires (lines) such as there are no overlaps and crossings. Also, components should be nicely aligned. The cost function is a weighted sum of required board space and total wire length. Very exciting !
Again thanks for your help
Peter
Two more comments.
You may also check SimpleMatrixSelect where you can specify an array of variables (vector of vectors) and select the whole sub-vector for labeling.
Your problem conatin symmetries that you may eliminate to get faster proof of optimality. There is several methods to do that. A simple one fixes, for example, one rectangle, into left top "quarter" of the ålacement space.
/Kris
Kris, I will checkout the example that uses SimpleMatrixSelect. And yes, I get faster results when I restrict the placement space like you suggested.
I think that the main problem for the moment is the way I detect overlaps and crossings.
There are at least two strategies:
. use a pairing function (Matthew Szudzik Wolfram Research, Inc) to get a unique hash for every coordinate on the rectangle borders and for each point of each wire. Then I can say AllDistinct. The problem is that I get into thousands of vars even for small problems. This is what I have currently. It works for small settings ( up to 10 components, for the moment I have no wires) but I am afraid it could blow up when I add wires. The problem size will never be much more than 10 components, because I group them into modules and treat each module as a black box in the next step. So it still seems a realistic approach, especially once I better understand how search is done. Computation time is less than 10 secs.
. use a try and error strategy.: get a first solution and allow crossings, detect the crossing and iteratively add constraints ( XneqY), restart search until there are no more crossings. The example of p.51 of the guide seems to be suitable for this. From other threads I read on this group, I got the impression though that this strategy is a bit "un-CP" , but maybe I misunderstood. Anyway, will give it a shot.
Thanks
Peter
Hi,
Please use Alldiff instead of Alldistinct. Alldistinct is usable only for specific tailored problems like larger Sudoku etc, but too often gives too little for the extra amount of work it requires. 95% of the cases Alldiff will be more than enough.
best,
Radek
Thanks for the advice, Radek, changed that , no notable impact on performance for the moment, though.
The impact depends on the problem but Alldistinct requires more computations and the complexity of the involved algorithms is higher. Alldistinct has complexity O(n^2.5) since it involves bipartite graph matching and Alldiff compxity of our impelemntation is O(n^2). Of course, there are some constants involved that for small lists of variables plays a significant role ;)
/Kris
What would be the appropriate way to incrementally add constraints after each depth-first-search ? Is p.51 (restart search) the way to go, or is this done with the master-slave setting ? I couldn't find such a process in the examples.
Thanks, Peter
First of all adding constraints incrementally is not typical way to model CP propblems ;) Saying that I can add that it is possible to add constraints before and under search. The method you refer to addresses the first case. You add new constraint and all the added constraints are considered by the solver. The second method, adding constraints, under search, is more complicated. Basically in each decision point you can add constraints. They will be valid on higher search levels and will disappear on lower levels of search (when backtracking to previous decisions). In fact one can organize the search using this method. Practially, the easiest way to do it is to use search plug-ins, I think.
/Kris
This is indeed what I read in another thread. Why is that so ? I think the guide explains that for example minimization is achieved by adding a new constraint after each seach:
Peter
The typical way to model CP problems is to define all constraints and find a slution or solutions. The definition of restart search does not change the model, it only constraints the cost.
/Kris