BTW, could you explain: term_variables(States,StatesList), % I should not do that, but I'm too lazy to do it better ;-) On Thu, Oct 6, 2011 at 10:41 PM, Sergey Dymchenko <kit1980_at_...6...> wrote: > Thank you for your program, Marco! > > I was thinking about integer programming, but I couldn't come up with > the way to model the problem. > > Sergey. > > On Thu, Oct 6, 2011 at 4:40 PM, Marco Gavanelli > <marco.gavanelli_at_...17...> wrote: >> Hi, >> >> On 01/10/11 21:11, Sergey Dymchenko wrote: >>> >>> Hello! >>> >>> I have the following problem: >>> >>> There is a system. There is an array of queries to the system - array >>> of integers :: 1..S, probably with repetitions, one integer for each >>> step. >>> On each step the system can have an integer state :: 1..S, and state >>> must not be equal to the query for this step. >>> We need to find a list of feasible states, such as number of switches >>> of the system states is minimal. >>> >>> For example, if S = 2, and Queries = [1, 2, 1], the answer is States = >>> [2, 1, 2], number of switches is 2 (from 2 to 1 and from 1 to 2). >>> If S = 3 and Queries = [1, 2, 1], the answer is States = [3, 3, 3], >>> number of switches is 0. >>> >>> I know a simple algorithmic solution for the problem, but I want to >>> solve it with CLP. >>> >>> I wrote a program, which works perfectly for small inputs but it takes >>> forever on large inputs when length on Queries is around 100 or more >>> (because number of possible solutions is huge and there is almost no >>> pruning). >>> >>> Any ideas how to speed it up? >> >> This particular problem is probably solved faster with an integer >> programming model. >> >> *With IC:* >> >> [eclipse 5]: solve(3, [](1, 2, >> 1,1,2,1,3,3,2,3,1,2,1,2,3,1,3,2,1,3,1,2,3,3,1,1,2,1,3,1,2,3,1,2,3,1,2,3), >> S). >> Found a solution with cost 25 >> Found a solution with cost 24 >> ... >> Found a solution with cost 12 >> Found no solution with cost 0.0 .. 11.0 >> >> S = [](3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 3, 3, 3, 3, 2, 2, 1, 1, 2, 2, 2, 1, 1, >> 1, 3, 3, 3, 2, 2, 2, 1, 1, 3, 3, 2, 2, 1, 1) >> Yes (52.06s cpu) >> >> *With Eplex:* >> >> [eclipse 16]: solve(3, [](1, 2, >> 1,1,2,1,3,3,2,3,1,2,1,2,3,1,3,2,1,3,1,2,3,3,1,1,2,1,3,1,2,3,1,2,3,1,2,3), >> S). >> >> S = [](_864{1.0 .. 3.0 _at_ 3.0}, _881{1.0 .. 3.0 @ 3.0000000000000009}, >> _898{1.0 .. 3.0 _at_ 3.0}, _915{1.0 .. 3.0 @ 3.0}, _932{1.0 .. 3.0 @ >> 3.0000000000000009}, _949{1.0 .. 3.0 _at_ 2.9999999999999991}, _966{1.0 .. 3.0 >> _at_ 1.0}, _983{1.0 .. 3.0 @ 1.0}, _1000{1.0 .. 3.0 @ 1.0}, _1017{1.0 .. 3.0 @ >> 1.0}, _1034{1.0 .. 3.0 _at_ 3.0}, _1051{1.0 .. 3.0 @ 3.0000000000000009}, >> _1068{1.0 .. 3.0 _at_ 3.0}, _1085{1.0 .. 3.0 @ 3.0000000000000009}, _1102{1.0 >> .. 3.0 _at_ 2.0}, _1119{1.0 .. 3.0 @ 2.0}, _1136{1.0 .. 3.0 @ 2.0}, _1153{1.0 >> .. 3.0 _at_ 3.0000000000000009}, _1170{1.0 .. 3.0 @ 2.0}, _1187{1.0 .. 3.0 @ >> 2.0}, _1204{1.0 .. 3.0 _at_ 2.0}, _1221{1.0 .. 3.0 @ 1.0}, _1238{1.0 .. 3.0 @ >> 1.0}, _1255{1.0 .. 3.0 _at_ 1.0}, _1272{1.0 .. 3.0 @ 3.0}, _1289{1.0 .. 3.0 @ >> 3.0}, _1306{1.0 .. 3.0 _at_ 3.0000000000000009}, _1323{1.0 .. 3.0 @ 3.0}, >> _1340{1.0 .. 3.0 _at_ 2.0}, _1357{1.0 .. 3.0 @ 2.0}, _1374{1.0 .. 3.0 @ 1.0}, >> _1391{1.0 .. 3.0 _at_ 0.99999999999999989}, _1408{1.0 .. 3.0 @ 3.0}, _1425{1.0 >> .. 3.0 _at_ 3.0000000000000009}, _1442{1.0 .. 3.0 @ 2.0}, _1459{1.0 .. 3.0 @ >> 2.0}, _1476{1.0 .. 3.0 _at_ 1.0}, _1493{1.0 .. 3.0 @ 1.0}) >> Yes (0.05s cpu) >> >> Cheers, >> Marco >> -- >> Marco Gavanelli, Ph.D. in Computer Science >> Dept of Engineering >> University of Ferrara >> Tel/Fax +39-0532-97-4833 >> http://www.ing.unife.it/docenti/MarcoGavanelli/ >> >> ------------------------------------------------------------------------------ >> All the data continuously generated in your IT infrastructure contains a >> definitive record of customers, application performance, security >> threats, fraudulent activity and more. Splunk takes this data and makes >> sense of it. Business sense. IT sense. Common sense. >> http://p.sf.net/sfu/splunk-d2dcopy1 >> _______________________________________________ >> ECLiPSe-CLP-Users mailing list >> ECLiPSe-CLP-Users_at_lists.sourceforge.net >> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users >> >> >Received on Thu Oct 06 2011 - 19:48:13 CEST
This archive was generated by hypermail 2.3.0 : Tue Apr 16 2024 - 09:13:20 CEST