From: Rehan Aziz <raziz@st...>  20120703 11:14:31
Attachments:
Message as HTML

Hi, If I use $maximize statements in clingcon programs, it seems that the solver doesn't provide the actual optimum solution. Consider the following example: number(1..5). $domain(1..100). profit(1) $<= 2. profit(2) $<= 3. profit(3) $<= 25. profit(4) $<= 5. profit(5) $<= 6. 2{knapsack(N) : number(N)}2. $maximize{profit(N) : knapsack(N)}. %(use taken from http://www.cs.unipotsdam.de/clingcon/doc/) The actual optimum solution is to pick knapsack(3) and knapsack(5), and assign profit(3)=25 and profit(5)=6. What I get is knapsack(1), knapsack(2), profit(1)=[1..2], and profit(2)=[1..3] (with cspnumas=1, I get profit(1)=1 and profit(2)=1). Even if we fix the boolean variables knapsack 1 and 2, shouldn't at least the constraint variables profits be maximized? Is there a way to get the optimum constraint answer set, i.e., the optimum answer over boolean as well as constraint domain? Thank you, Rehan. 
From: Max Ostrowski <ostrowsk@cs...>  20120703 11:23:51
Attachments:
Message as HTML

Hi Rehan, currently clingcon does not provide the actual optimal value, but cou can simply introduce a variable for this. Furthermore, for your example you have to call clingcon with "0" for enumerating all models and "cspnumas=0" for enumerating all csp models. The call "clingcon your_problem cspnumas=0 0" gives me the solution knapsack(2) knapsack(1) profit(1)=2 profit(2)=3 profit(3)=25 profit(4)=5 profit(5)=6 To get the final score you could introduce something like max $== $sum{profit(N) : knapsack(N)}. If you have any further questions, just ask. Best, Max On 07/03/2012 01:08 PM, Rehan Aziz wrote: > Hi, > > If I use $maximize statements in clingcon programs, it seems that the > solver doesn't provide the actual optimum solution. Consider the > following example: > > number(1..5). > $domain(1..100). > > profit(1) $<= 2. profit(2) $<= 3. profit(3) $<= 25. profit(4) $<= 5. > profit(5) $<= 6. > > 2{knapsack(N) : number(N)}2. > > $maximize{profit(N) : knapsack(N)}. %(use taken > from http://www.cs.unipotsdam.de/clingcon/doc/) > > The actual optimum solution is to pick knapsack(3) and knapsack(5), > and assign profit(3)=25 and profit(5)=6. What I get is knapsack(1), > knapsack(2), profit(1)=[1..2], and profit(2)=[1..3] (with > cspnumas=1, I get profit(1)=1 and profit(2)=1). Even if we fix the > boolean variables knapsack 1 and 2, shouldn't at least the constraint > variables profits be maximized? > > Is there a way to get the optimum constraint answer set, i.e., the > optimum answer over boolean as well as constraint domain? > > Thank you, > Rehan. > > >  > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > > > _______________________________________________ > Potasscousers mailing list > Potasscousers@... > https://lists.sourceforge.net/lists/listinfo/potasscousers > 
From: Max Ostrowski <ostrowsk@cs...>  20120703 11:37:04
Attachments:
Message as HTML

Actually, there seems to be a bug in clingcon for your problem. (this should not change anything for your specific problem) The grounding of your example results in: $maximize{profit(1)@0,profit(2)@0,profit(3)@0,profit(4)@0,profit(5)@0}. Actually, clingcon should only allow expansion with facts, and give an error on this. Once we a have a new grounder (gringo4) this will hopefully be fixed by me :) Best, Max On 07/03/2012 01:23 PM, Max Ostrowski wrote: > Hi Rehan, > currently clingcon does not provide the actual optimal value, but cou > can simply introduce a variable for this. > Furthermore, for your example you have to call clingcon with "0" for > enumerating all models and "cspnumas=0" for enumerating all csp > models. > The call "clingcon your_problem cspnumas=0 0" gives me the > solution knapsack(2) knapsack(1) profit(1)=2 profit(2)=3 profit(3)=25 > profit(4)=5 profit(5)=6 > > To get the final score you could introduce something like > max $== $sum{profit(N) : knapsack(N)}. > > If you have any further questions, just ask. > > Best, > Max > > On 07/03/2012 01:08 PM, Rehan Aziz wrote: >> Hi, >> >> If I use $maximize statements in clingcon programs, it seems that the >> solver doesn't provide the actual optimum solution. Consider the >> following example: >> >> number(1..5). >> $domain(1..100). >> >> profit(1) $<= 2. profit(2) $<= 3. profit(3) $<= 25. profit(4) $<= 5. >> profit(5) $<= 6. >> >> 2{knapsack(N) : number(N)}2. >> >> $maximize{profit(N) : knapsack(N)}. %(use taken >> from http://www.cs.unipotsdam.de/clingcon/doc/) >> >> The actual optimum solution is to pick knapsack(3) and knapsack(5), >> and assign profit(3)=25 and profit(5)=6. What I get is knapsack(1), >> knapsack(2), profit(1)=[1..2], and profit(2)=[1..3] (with >> cspnumas=1, I get profit(1)=1 and profit(2)=1). Even if we fix >> the boolean variables knapsack 1 and 2, shouldn't at least the >> constraint variables profits be maximized? >> >> Is there a way to get the optimum constraint answer set, i.e., the >> optimum answer over boolean as well as constraint domain? >> >> Thank you, >> Rehan. >> >> >>  >> Live Security Virtual Conference >> Exclusive live event will cover all the ways today's security and >> threat landscape has changed and how IT managers can respond. Discussions >> will include endpoint security, mobile security and the latest in malware >> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >> >> >> _______________________________________________ >> Potasscousers mailing list >> Potasscousers@... >> https://lists.sourceforge.net/lists/listinfo/potasscousers >> > > >  > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > > > _______________________________________________ > Potasscousers mailing list > Potasscousers@... > https://lists.sourceforge.net/lists/listinfo/potasscousers > 
From: Rehan Aziz <raziz@st...>  20120703 12:23:55
Attachments:
Message as HTML

Hi Max, Thank you for your prompt reply. Lets work with a new example which uses facts in the maximize statement: number(1..5). $domain(0..100). 2{knapsack(N) : number(N)}2. profit(1) $<= 2 : knapsack(1). profit(2) $<= 3 : knapsack(2). profit(3) $<= 25 : knapsack(3). profit(4) $<= 5 : knapsack(4). profit(5) $<= 6 : knapsack(5). profit(1) $== 0 : not knapsack(1). profit(2) $== 0 : not knapsack(2). profit(3) $== 0 : not knapsack(3). profit(4) $== 0 : not knapsack(4). profit(5) $== 0 : not knapsack(5). $maximize{profit(N) : number(N)}. With clingcon above_program (same result with using cspnumas=0), I get: ...knapsack(2) knapsack(1)...profit(1)=0 profit(2)=0.. However, if I do clingcon above_program 0, I get the best solution at the end (not sure if this is a coincidence). On Tue, Jul 3, 2012 at 9:23 PM, Max Ostrowski <ostrowsk@...>wrote: > ** > Hi Rehan, > currently clingcon does not provide the actual optimal value, but cou can > simply introduce a variable for this. > Could you please explain this a little more using the example above? > Furthermore, for your example you have to call clingcon with "0" for > enumerating all models and "cspnumas=0" for enumerating all csp models. > Makes no difference on my side. I guess its due to the error you have pointed out in your next email. > The call "clingcon your_problem cspnumas=0 0" gives me the solution > knapsack(2) knapsack(1) profit(1)=2 profit(2)=3 profit(3)=25 profit(4)=5 > profit(5)=6 > > To get the final score you could introduce something like > max $== $sum{profit(N) : knapsack(N)}. > > If I understand it correctly, max is still a constraint variable and (assuming knapsack is a fact) will only give the optimum in the constraint domain. Will this actually help in getting the globally optimum (best in boolean+cp) solution? > If you have any further questions, just ask. > > Best, > Max > > > On 07/03/2012 01:08 PM, Rehan Aziz wrote: > > Hi, > > If I use $maximize statements in clingcon programs, it seems that the > solver doesn't provide the actual optimum solution. Consider the following > example: > > number(1..5). > $domain(1..100). > > profit(1) $<= 2. profit(2) $<= 3. profit(3) $<= 25. profit(4) $<= 5. > profit(5) $<= 6. > > 2{knapsack(N) : number(N)}2. > > $maximize{profit(N) : knapsack(N)}. %(use taken from > http://www.cs.unipotsdam.de/clingcon/doc/) > > The actual optimum solution is to pick knapsack(3) and knapsack(5), and > assign profit(3)=25 and profit(5)=6. What I get is knapsack(1), > knapsack(2), profit(1)=[1..2], and profit(2)=[1..3] (with cspnumas=1, I > get profit(1)=1 and profit(2)=1). Even if we fix the boolean variables > knapsack 1 and 2, shouldn't at least the constraint variables profits be > maximized? > > Is there a way to get the optimum constraint answer set, i.e., the > optimum answer over boolean as well as constraint domain? > > Thank you, > Rehan. > > >  > Live Security Virtual Conference > Exclusive live event will cover all the ways today's security and > threat landscape has changed and how IT managers can respond. Discussions > will include endpoint security, mobile security and the latest in malware > threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ > > > _______________________________________________ > Potasscousers mailing listPotasscousers@...nethttps://lists.sourceforge.net/lists/listinfo/potasscousers > > > Regards, Rehan. 
From: Max Ostrowski <ostrowsk@cs...>  20120703 13:14:27
Attachments:
Message as HTML

On 07/03/2012 02:23 PM, Rehan Aziz wrote: > Hi Max, > > Thank you for your prompt reply. Lets work with a new example which > uses facts in the maximize statement: > > number(1..5). > $domain(0..100). > > 2{knapsack(N) : number(N)}2. > > profit(1) $<= 2 : knapsack(1). > profit(2) $<= 3 : knapsack(2). > profit(3) $<= 25 : knapsack(3). > profit(4) $<= 5 : knapsack(4). > profit(5) $<= 6 : knapsack(5). > > profit(1) $== 0 : not knapsack(1). > profit(2) $== 0 : not knapsack(2). > profit(3) $== 0 : not knapsack(3). > profit(4) $== 0 : not knapsack(4). > profit(5) $== 0 : not knapsack(5). > > $maximize{profit(N) : number(N)}. > > With clingcon above_program (same result with using cspnumas=0), I > get: > > ...knapsack(2) knapsack(1)...profit(1)=0 profit(2)=0.. > > However, if I do clingcon above_program 0, I get the best solution at > the end (not sure if this is a coincidence). This is not a coincidence, this is intention. You need to use both "cspnumas=0" and "0". The first one states, that, IF you have found a total boolean assignment, enumerate all constraint answers that fit to this boolean assignment. The second one restricts the total number of models. So if you enumerate all csp models but restrict the total number of models to "1" (default) you will only get one model (the first one that is found). For optimization you need to enumerate all models, as you will first find a model and afterwards try to find a better one until no better exists. Does this become clear now? Maybe not, i will another example. $domain(1..5). 1{a,b}1. x $<3. This will give you two boolean answers {a}{b} Both can be extended by x=1 and x=2 So, calling this with "0" and "cspnumas=1" only will give you all boolean answers with 1 extension (For example {a,x=2}{b,x=2}) With "2" and "cspnumas=0" this will give you 2 answers only. It first finds for example boolean assignment {a} and extends this then with all csp answers, so {a,x=1} and {a,x=2} To find an optimal answer you therefore have to enumerate all models, "0" and "cspnumas=0". Questions? > > On Tue, Jul 3, 2012 at 9:23 PM, Max Ostrowski > <ostrowsk@... <mailto:ostrowsk@...>> wrote: > > Hi Rehan, > currently clingcon does not provide the actual optimal value, but > cou can simply introduce a variable for this. > > > Could you please explain this a little more using the example above? max $== $sum{profit(N) : number(N)}. $maximize{max}. > > > Furthermore, for your example you have to call clingcon with "0" > for enumerating all models and "cspnumas=0" for enumerating > all csp models. > > > Makes no difference on my side. I guess its due to the error you have > pointed out in your next email. > > > The call "clingcon your_problem cspnumas=0 0" gives me the > solution knapsack(2) knapsack(1) profit(1)=2 profit(2)=3 > profit(3)=25 profit(4)=5 profit(5)=6 > > To get the final score you could introduce something like > max $== $sum{profit(N) : knapsack(N)}. > > > If I understand it correctly, max is still a constraint variable and > (assuming knapsack is a fact) will only give the optimum in the > constraint domain. Will this actually help in getting the globally > optimum (best in boolean+cp) solution? Right, max is a constraint variable (assuming knapsack is a fact, but this works for your example even if it is not a fact). "max" only helps you to read out the maximum value (as it is "max" ;) ) But i'm confused: " (best in boolean+cp)" There is no optimization statement over boolean variables. But it will find you the best overall answer for your csp optimize statement. (this includes that the boolean variables are set accordingly, so this is really a global optimum). I hope things are a bit more clear now, if not, simply ask :D Best, Max > > > If you have any further questions, just ask. > > Best, > Max > > > On 07/03/2012 01:08 PM, Rehan Aziz wrote: >> Hi, >> >> If I use $maximize statements in clingcon programs, it seems that >> the solver doesn't provide the actual optimum solution. Consider >> the following example: >> >> number(1..5). >> $domain(1..100). >> >> profit(1) $<= 2. profit(2) $<= 3. profit(3) $<= 25. profit(4) $<= >> 5. profit(5) $<= 6. >> >> 2{knapsack(N) : number(N)}2. >> >> $maximize{profit(N) : knapsack(N)}. %(use taken >> from http://www.cs.unipotsdam.de/clingcon/doc/) >> >> The actual optimum solution is to pick knapsack(3) and >> knapsack(5), and assign profit(3)=25 and profit(5)=6. What I get >> is knapsack(1), knapsack(2), profit(1)=[1..2], and >> profit(2)=[1..3] (with cspnumas=1, I get profit(1)=1 and >> profit(2)=1). Even if we fix the boolean variables knapsack 1 and >> 2, shouldn't at least the constraint variables profits be maximized? >> >> Is there a way to get the optimum constraint answer set, i.e., >> the optimum answer over boolean as well as constraint domain? >> >> Thank you, >> Rehan. >> >> >>  >> Live Security Virtual Conference >> Exclusive live event will cover all the ways today's security and >> threat landscape has changed and how IT managers can respond. Discussions >> will include endpoint security, mobile security and the latest in malware >> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >> >> >> _______________________________________________ >> Potasscousers mailing list >> Potasscousers@... <mailto:Potasscousers@...> >> https://lists.sourceforge.net/lists/listinfo/potasscousers >> > > > Regards, > Rehan. 
From: Rehan Aziz <raziz@st...>  20120703 14:34:53
Attachments:
Message as HTML

Thank you for the detailed explanation, it is helpful. :) On Tue, Jul 3, 2012 at 11:14 PM, Max Ostrowski <ostrowsk@...>wrote: > ** > On 07/03/2012 02:23 PM, Rehan Aziz wrote: > > Hi Max, > > Thank you for your prompt reply. Lets work with a new example which uses > facts in the maximize statement: > > number(1..5). > $domain(0..100). > > 2{knapsack(N) : number(N)}2. > > profit(1) $<= 2 : knapsack(1). > profit(2) $<= 3 : knapsack(2). > profit(3) $<= 25 : knapsack(3). > profit(4) $<= 5 : knapsack(4). > profit(5) $<= 6 : knapsack(5). > > profit(1) $== 0 : not knapsack(1). > profit(2) $== 0 : not knapsack(2). > profit(3) $== 0 : not knapsack(3). > profit(4) $== 0 : not knapsack(4). > profit(5) $== 0 : not knapsack(5). > > $maximize{profit(N) : number(N)}. > > With clingcon above_program (same result with using cspnumas=0), I > get: > > ...knapsack(2) knapsack(1)...profit(1)=0 profit(2)=0.. > > However, if I do clingcon above_program 0, I get the best solution at > the end (not sure if this is a coincidence). > > This is not a coincidence, this is intention. You need to use both > "cspnumas=0" and "0". > Great. This could be slightly confusing for the programmer, since maximize or minimize, usually mean that search will continue finding better solutions until the whole tree has been explored. > The first one states, that, IF you have found a total boolean assignment, > enumerate all constraint answers that fit to this boolean assignment. > And I'm assuming if there is an optimize statement over csp variables, then the last solution printed will be the optimum csp solution (for the given total boolean assignment), right? If not, please ignore the following paragraph. :) For the program above, the first total boolean assignment that clingcon finds is knapsack(1) and knapsack(2). We get this by clingcon above_program cspnumas=0. This enforces profit(1) $<= 2 and profit(2) $<= 3. The optimum value should be profit(1)=2 and profit(2)=3. Yet, I get profit(1)=0 and profit(2)=0. > The second one restricts the total number of models. > So if you enumerate all csp models but restrict the total number of models > to "1" (default) you will only get one model (the first one that is found). > For optimization you need to enumerate all models, as you will first find > a model and afterwards try to find a better one until no better exists. > Does this become clear now? > Maybe not, i will another example. > > $domain(1..5). > 1{a,b}1. > x $<3. > > This will give you two boolean answers {a}{b} > Both can be extended by x=1 and x=2 > So, calling this with "0" and "cspnumas=1" only will give you all > boolean answers with 1 extension > (For example {a,x=2}{b,x=2}) > With "2" and "cspnumas=0" this will give you 2 answers only. > It first finds for example boolean assignment {a} and extends this then > with all csp answers, so {a,x=1} and {a,x=2} > > To find an optimal answer you therefore have to enumerate all models, "0" > and "cspnumas=0". > Questions? > *Thums up*. > > > On Tue, Jul 3, 2012 at 9:23 PM, Max Ostrowski <ostrowsk@...>wrote: > >> Hi Rehan, >> currently clingcon does not provide the actual optimal value, but cou can >> simply introduce a variable for this. >> > > Could you please explain this a little more using the example above? > > max $== $sum{profit(N) : number(N)}. > $maximize{max}. > > > >> Furthermore, for your example you have to call clingcon with "0" for >> enumerating all models and "cspnumas=0" for enumerating all csp models. >> > > Makes no difference on my side. I guess its due to the error you have > pointed out in your next email. > > >> The call "clingcon your_problem cspnumas=0 0" gives me the solution >> knapsack(2) knapsack(1) profit(1)=2 profit(2)=3 profit(3)=25 profit(4)=5 >> profit(5)=6 >> >> To get the final score you could introduce something like >> max $== $sum{profit(N) : knapsack(N)}. >> >> > If I understand it correctly, max is still a constraint variable and > (assuming knapsack is a fact) will only give the optimum in the constraint > domain. Will this actually help in getting the globally optimum (best in > boolean+cp) solution? > > Right, max is a constraint variable (assuming knapsack is a fact, but this > works for your example even if it is not a fact). > "max" only helps you to read out the maximum value (as it is "max" ;) ) > > But i'm confused: " (best in boolean+cp)" > I just meant global optimum. > There is no optimization statement over boolean variables. > But it will find you the best overall answer for your csp optimize > statement. > (this includes that the boolean variables are set accordingly, so this is > really a global optimum). > > I hope things are a bit more clear now, > if not, simply ask :D > :) > > Best, > Max > > > >> If you have any further questions, just ask. >> >> Best, >> Max >> >> >> On 07/03/2012 01:08 PM, Rehan Aziz wrote: >> >> Hi, >> >> If I use $maximize statements in clingcon programs, it seems that the >> solver doesn't provide the actual optimum solution. Consider the following >> example: >> >> number(1..5). >> $domain(1..100). >> >> profit(1) $<= 2. profit(2) $<= 3. profit(3) $<= 25. profit(4) $<= 5. >> profit(5) $<= 6. >> >> 2{knapsack(N) : number(N)}2. >> >> $maximize{profit(N) : knapsack(N)}. %(use taken from >> http://www.cs.unipotsdam.de/clingcon/doc/) >> >> The actual optimum solution is to pick knapsack(3) and knapsack(5), and >> assign profit(3)=25 and profit(5)=6. What I get is knapsack(1), >> knapsack(2), profit(1)=[1..2], and profit(2)=[1..3] (with cspnumas=1, I >> get profit(1)=1 and profit(2)=1). Even if we fix the boolean variables >> knapsack 1 and 2, shouldn't at least the constraint variables profits be >> maximized? >> >> Is there a way to get the optimum constraint answer set, i.e., the >> optimum answer over boolean as well as constraint domain? >> >> Thank you, >> Rehan. >> >> >>  >> Live Security Virtual Conference >> Exclusive live event will cover all the ways today's security and >> threat landscape has changed and how IT managers can respond. Discussions >> will include endpoint security, mobile security and the latest in malware >> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >> >> >> _______________________________________________ >> Potasscousers mailing listPotasscousers@...nethttps://lists.sourceforge.net/lists/listinfo/potasscousers >> >> >> > Regards, > Rehan. > > > 
From: Max Ostrowski <ostrowsk@cs...>  20120704 07:44:30
Attachments:
Message as HTML

Comments in mail ... On 07/03/2012 04:34 PM, Rehan Aziz wrote: > Thank you for the detailed explanation, it is helpful. :) > > On Tue, Jul 3, 2012 at 11:14 PM, Max Ostrowski > <ostrowsk@... <mailto:ostrowsk@...>> wrote: > > On 07/03/2012 02:23 PM, Rehan Aziz wrote: >> Hi Max, >> >> Thank you for your prompt reply. Lets work with a new example >> which uses facts in the maximize statement: >> >> number(1..5). >> $domain(0..100). >> >> 2{knapsack(N) : number(N)}2. >> >> profit(1) $<= 2 : knapsack(1). >> profit(2) $<= 3 : knapsack(2). >> profit(3) $<= 25 : knapsack(3). >> profit(4) $<= 5 : knapsack(4). >> profit(5) $<= 6 : knapsack(5). >> >> profit(1) $== 0 : not knapsack(1). >> profit(2) $== 0 : not knapsack(2). >> profit(3) $== 0 : not knapsack(3). >> profit(4) $== 0 : not knapsack(4). >> profit(5) $== 0 : not knapsack(5). >> >> $maximize{profit(N) : number(N)}. >> >> With clingcon above_program (same result with using >> cspnumas=0), I get: >> >> ...knapsack(2) knapsack(1)...profit(1)=0 profit(2)=0.. >> >> However, if I do clingcon above_program 0, I get the best >> solution at the end (not sure if this is a coincidence). > This is not a coincidence, this is intention. You need to use both > "cspnumas=0" and "0". > > > Great. This could be slightly confusing for the programmer, since > maximize or minimize, usually mean that search will continue finding > better solutions until the whole tree has been explored. With clasp, you also had to state to enumerate all solutions in former times. Now this is done implicitly, so whenever a minimize statement occurs it sets the parameter "0". I will write this to my ToDo list also for clingcon minimize statements, ok ? :) > > > The first one states, that, IF you have found a total boolean > assignment, enumerate all constraint answers that fit to this > boolean assignment. > > > And I'm assuming if there is an optimize statement over csp variables, > then the last solution printed will be the optimum csp solution (for > the given total boolean assignment), right? If not, please ignore the > following paragraph. :) This is true ! > > For the program above, the first total boolean assignment that > clingcon finds is knapsack(1) and knapsack(2). We get this by clingcon > above_program cspnumas=0. This enforces profit(1) $<= 2 > and profit(2) $<= 3. The optimum value should be profit(1)=2 and > profit(2)=3. Yet, I get profit(1)=0 and profit(2)=0. Right, and this is intended behavior. With "cspnumas=0" you say that he should enumerate as much as possible constraint extensions to your boolean assignment. BUT the total number of models is stronger than this. with "clingcon cspnumas=0" you implicitly state you want to have just a single model "1". But you have to state that you want all "0". For a better understanding try "clingcon t cspnumas=0 3". The boolean assignment is still fixed and you converge to a local optimum. Hope this helps a bit more, if not, just ask. Best, Max > > > The second one restricts the total number of models. > So if you enumerate all csp models but restrict the total number > of models to "1" (default) you will only get one model (the first > one that is found). > For optimization you need to enumerate all models, as you will > first find a model and afterwards try to find a better one until > no better exists. > Does this become clear now? > Maybe not, i will another example. > > $domain(1..5). > 1{a,b}1. > x $<3. > > This will give you two boolean answers {a}{b} > Both can be extended by x=1 and x=2 > So, calling this with "0" and "cspnumas=1" only will give you > all boolean answers with 1 extension > (For example {a,x=2}{b,x=2}) > With "2" and "cspnumas=0" this will give you 2 answers only. > It first finds for example boolean assignment {a} and extends this > then with all csp answers, so {a,x=1} and {a,x=2} > > To find an optimal answer you therefore have to enumerate all > models, "0" and "cspnumas=0". > > Questions? > > > *Thums up*. > > > >> >> On Tue, Jul 3, 2012 at 9:23 PM, Max Ostrowski >> <ostrowsk@... <mailto:ostrowsk@...>> >> wrote: >> >> Hi Rehan, >> currently clingcon does not provide the actual optimal value, >> but cou can simply introduce a variable for this. >> >> >> Could you please explain this a little more using the example above? > max $== $sum{profit(N) : number(N)}. > $maximize{max}. > >> >> >> Furthermore, for your example you have to call clingcon with >> "0" for enumerating all models and "cspnumas=0" for >> enumerating all csp models. >> >> >> Makes no difference on my side. I guess its due to the error you >> have pointed out in your next email. >> >> >> The call "clingcon your_problem cspnumas=0 0" gives me >> the solution knapsack(2) knapsack(1) profit(1)=2 profit(2)=3 >> profit(3)=25 profit(4)=5 profit(5)=6 >> >> To get the final score you could introduce something like >> max $== $sum{profit(N) : knapsack(N)}. >> >> >> If I understand it correctly, max is still a constraint variable >> and (assuming knapsack is a fact) will only give the optimum in >> the constraint domain. Will this actually help in getting the >> globally optimum (best in boolean+cp) solution? > Right, max is a constraint variable (assuming knapsack is a fact, > but this works for your example even if it is not a fact). > "max" only helps you to read out the maximum value (as it is "max" > ;) ) > > But i'm confused: " (best in boolean+cp)" > > > I just meant global optimum. > > > There is no optimization statement over boolean variables. > But it will find you the best overall answer for your csp optimize > statement. > (this includes that the boolean variables are set accordingly, so > this is really a global optimum). > > I hope things are a bit more clear now, > if not, simply ask :D > > > :) > > > > Best, > Max > >> >> >> If you have any further questions, just ask. >> >> Best, >> Max >> >> >> On 07/03/2012 01:08 PM, Rehan Aziz wrote: >>> Hi, >>> >>> If I use $maximize statements in clingcon programs, it seems >>> that the solver doesn't provide the actual optimum solution. >>> Consider the following example: >>> >>> number(1..5). >>> $domain(1..100). >>> >>> profit(1) $<= 2. profit(2) $<= 3. profit(3) $<= 25. >>> profit(4) $<= 5. profit(5) $<= 6. >>> >>> 2{knapsack(N) : number(N)}2. >>> >>> $maximize{profit(N) : knapsack(N)}. %(use taken >>> from http://www.cs.unipotsdam.de/clingcon/doc/) >>> >>> The actual optimum solution is to pick knapsack(3) and >>> knapsack(5), and assign profit(3)=25 and profit(5)=6. What I >>> get is knapsack(1), knapsack(2), profit(1)=[1..2], and >>> profit(2)=[1..3] (with cspnumas=1, I get profit(1)=1 and >>> profit(2)=1). Even if we fix the boolean variables knapsack >>> 1 and 2, shouldn't at least the constraint variables profits >>> be maximized? >>> >>> Is there a way to get the optimum constraint answer set, >>> i.e., the optimum answer over boolean as well as constraint >>> domain? >>> >>> Thank you, >>> Rehan. >>> >>> >>>  >>> Live Security Virtual Conference >>> Exclusive live event will cover all the ways today's security and >>> threat landscape has changed and how IT managers can respond. Discussions >>> will include endpoint security, mobile security and the latest in malware >>> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >>> >>> >>> _______________________________________________ >>> Potasscousers mailing list >>> Potasscousers@... <mailto:Potasscousers@...> >>> https://lists.sourceforge.net/lists/listinfo/potasscousers >>> >> >> >> Regards, >> Rehan. > > 
From: Rehan Aziz <raziz@st...>  20120704 08:21:54
Attachments:
Message as HTML

Totally clear now, thanks a bunch! :) On Wed, Jul 4, 2012 at 5:44 PM, Max Ostrowski <ostrowsk@...>wrote: > ** > Comments in mail ... > > On 07/03/2012 04:34 PM, Rehan Aziz wrote: > > Thank you for the detailed explanation, it is helpful. :) > > On Tue, Jul 3, 2012 at 11:14 PM, Max Ostrowski <ostrowsk@... > > wrote: > >> On 07/03/2012 02:23 PM, Rehan Aziz wrote: >> >> Hi Max, >> >> Thank you for your prompt reply. Lets work with a new example which >> uses facts in the maximize statement: >> >> number(1..5). >> $domain(0..100). >> >> 2{knapsack(N) : number(N)}2. >> >> profit(1) $<= 2 : knapsack(1). >> profit(2) $<= 3 : knapsack(2). >> profit(3) $<= 25 : knapsack(3). >> profit(4) $<= 5 : knapsack(4). >> profit(5) $<= 6 : knapsack(5). >> >> profit(1) $== 0 : not knapsack(1). >> profit(2) $== 0 : not knapsack(2). >> profit(3) $== 0 : not knapsack(3). >> profit(4) $== 0 : not knapsack(4). >> profit(5) $== 0 : not knapsack(5). >> >> $maximize{profit(N) : number(N)}. >> >> With clingcon above_program (same result with using cspnumas=0), I >> get: >> >> ...knapsack(2) knapsack(1)...profit(1)=0 profit(2)=0.. >> >> However, if I do clingcon above_program 0, I get the best solution at >> the end (not sure if this is a coincidence). >> >> This is not a coincidence, this is intention. You need to use both >> "cspnumas=0" and "0". >> > > Great. This could be slightly confusing for the programmer, since > maximize or minimize, usually mean that search will continue finding better > solutions until the whole tree has been explored. > > With clasp, you also had to state to enumerate all solutions in former > times. > Now this is done implicitly, so whenever a minimize statement occurs it > sets the parameter "0". > I will write this to my ToDo list also for clingcon minimize statements, > ok ? :) > > > >> The first one states, that, IF you have found a total boolean assignment, >> enumerate all constraint answers that fit to this boolean assignment. >> > > And I'm assuming if there is an optimize statement over csp variables, > then the last solution printed will be the optimum csp solution (for the > given total boolean assignment), right? If not, please ignore the following > paragraph. :) > > This is true ! > > > For the program above, the first total boolean assignment that clingcon > finds is knapsack(1) and knapsack(2). We get this by clingcon above_program > cspnumas=0. This enforces profit(1) $<= 2 and profit(2) $<= 3. The > optimum value should be profit(1)=2 and profit(2)=3. Yet, I get profit(1)=0 > and profit(2)=0. > > Right, and this is intended behavior. With "cspnumas=0" you say that > he should enumerate as much as possible constraint extensions to your > boolean assignment. BUT > the total number of models is stronger than this. with "clingcon > cspnumas=0" you implicitly state you want to have just a single model > "1". But you have to state that you want all "0". > For a better understanding try "clingcon t cspnumas=0 3". > The boolean assignment is still fixed and you converge to a local optimum. > > Hope this helps a bit more, if not, just ask. > > Best, > Max > > > >> The second one restricts the total number of models. >> So if you enumerate all csp models but restrict the total number of >> models to "1" (default) you will only get one model (the first one that is >> found). >> For optimization you need to enumerate all models, as you will first find >> a model and afterwards try to find a better one until no better exists. >> Does this become clear now? >> Maybe not, i will another example. >> >> $domain(1..5). >> 1{a,b}1. >> x $<3. >> >> This will give you two boolean answers {a}{b} >> Both can be extended by x=1 and x=2 >> So, calling this with "0" and "cspnumas=1" only will give you all >> boolean answers with 1 extension >> (For example {a,x=2}{b,x=2}) >> With "2" and "cspnumas=0" this will give you 2 answers only. >> It first finds for example boolean assignment {a} and extends this then >> with all csp answers, so {a,x=1} and {a,x=2} >> >> To find an optimal answer you therefore have to enumerate all models, "0" >> and "cspnumas=0". >> > Questions? >> > > *Thums up*. > > >> >> >> On Tue, Jul 3, 2012 at 9:23 PM, Max Ostrowski <ostrowsk@... >> > wrote: >> >>> Hi Rehan, >>> currently clingcon does not provide the actual optimal value, but cou >>> can simply introduce a variable for this. >>> >> >> Could you please explain this a little more using the example above? >> >> max $== $sum{profit(N) : number(N)}. >> $maximize{max}. >> >> >> >>> Furthermore, for your example you have to call clingcon with "0" for >>> enumerating all models and "cspnumas=0" for enumerating all csp models. >>> >> >> Makes no difference on my side. I guess its due to the error you have >> pointed out in your next email. >> >> >>> The call "clingcon your_problem cspnumas=0 0" gives me the solution >>> knapsack(2) knapsack(1) profit(1)=2 profit(2)=3 profit(3)=25 profit(4)=5 >>> profit(5)=6 >>> >>> To get the final score you could introduce something like >>> max $== $sum{profit(N) : knapsack(N)}. >>> >>> >> If I understand it correctly, max is still a constraint variable and >> (assuming knapsack is a fact) will only give the optimum in the constraint >> domain. Will this actually help in getting the globally optimum (best in >> boolean+cp) solution? >> >> Right, max is a constraint variable (assuming knapsack is a fact, but >> this works for your example even if it is not a fact). >> "max" only helps you to read out the maximum value (as it is "max" ;) ) >> >> But i'm confused: " (best in boolean+cp)" >> > > I just meant global optimum. > > >> There is no optimization statement over boolean variables. >> But it will find you the best overall answer for your csp optimize >> statement. >> (this includes that the boolean variables are set accordingly, so this is >> really a global optimum). >> >> I hope things are a bit more clear now, >> if not, simply ask :D >> > > :) > > >> >> Best, >> Max >> >> >> >>> If you have any further questions, just ask. >>> >>> Best, >>> Max >>> >>> >>> On 07/03/2012 01:08 PM, Rehan Aziz wrote: >>> >>> Hi, >>> >>> If I use $maximize statements in clingcon programs, it seems that the >>> solver doesn't provide the actual optimum solution. Consider the following >>> example: >>> >>> number(1..5). >>> $domain(1..100). >>> >>> profit(1) $<= 2. profit(2) $<= 3. profit(3) $<= 25. profit(4) $<= 5. >>> profit(5) $<= 6. >>> >>> 2{knapsack(N) : number(N)}2. >>> >>> $maximize{profit(N) : knapsack(N)}. %(use taken from >>> http://www.cs.unipotsdam.de/clingcon/doc/) >>> >>> The actual optimum solution is to pick knapsack(3) and knapsack(5), and >>> assign profit(3)=25 and profit(5)=6. What I get is knapsack(1), >>> knapsack(2), profit(1)=[1..2], and profit(2)=[1..3] (with cspnumas=1, I >>> get profit(1)=1 and profit(2)=1). Even if we fix the boolean variables >>> knapsack 1 and 2, shouldn't at least the constraint variables profits be >>> maximized? >>> >>> Is there a way to get the optimum constraint answer set, i.e., the >>> optimum answer over boolean as well as constraint domain? >>> >>> Thank you, >>> Rehan. >>> >>> >>>  >>> Live Security Virtual Conference >>> Exclusive live event will cover all the ways today's security and >>> threat landscape has changed and how IT managers can respond. Discussions >>> will include endpoint security, mobile security and the latest in malware >>> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ >>> >>> >>> _______________________________________________ >>> Potasscousers mailing listPotasscousers@...nethttps://lists.sourceforge.net/lists/listinfo/potasscousers >>> >>> >>> >> Regards, >> Rehan. >> >> >> > > 