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_unife.it> 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 @ 3.0}, _881{1.0 .. 3.0 @ 3.0000000000000009}, > _898{1.0 .. 3.0 @ 3.0}, _915{1.0 .. 3.0 @ 3.0}, _932{1.0 .. 3.0 @ > 3.0000000000000009}, _949{1.0 .. 3.0 @ 2.9999999999999991}, _966{1.0 .. 3.0 > @ 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 @ 3.0}, _1051{1.0 .. 3.0 @ 3.0000000000000009}, > _1068{1.0 .. 3.0 @ 3.0}, _1085{1.0 .. 3.0 @ 3.0000000000000009}, _1102{1.0 > .. 3.0 @ 2.0}, _1119{1.0 .. 3.0 @ 2.0}, _1136{1.0 .. 3.0 @ 2.0}, _1153{1.0 > .. 3.0 @ 3.0000000000000009}, _1170{1.0 .. 3.0 @ 2.0}, _1187{1.0 .. 3.0 @ > 2.0}, _1204{1.0 .. 3.0 @ 2.0}, _1221{1.0 .. 3.0 @ 1.0}, _1238{1.0 .. 3.0 @ > 1.0}, _1255{1.0 .. 3.0 @ 1.0}, _1272{1.0 .. 3.0 @ 3.0}, _1289{1.0 .. 3.0 @ > 3.0}, _1306{1.0 .. 3.0 @ 3.0000000000000009}, _1323{1.0 .. 3.0 @ 3.0}, > _1340{1.0 .. 3.0 @ 2.0}, _1357{1.0 .. 3.0 @ 2.0}, _1374{1.0 .. 3.0 @ 1.0}, > _1391{1.0 .. 3.0 @ 0.99999999999999989}, _1408{1.0 .. 3.0 @ 3.0}, _1425{1.0 > .. 3.0 @ 3.0000000000000009}, _1442{1.0 .. 3.0 @ 2.0}, _1459{1.0 .. 3.0 @ > 2.0}, _1476{1.0 .. 3.0 @ 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:41:55 CEST
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET