Re: [eclipse-clp-users] Minimizing a parameter that depends on global state

From: Sergey Dymchenko <kit1980_at_...6...>
Date: Thu, 6 Oct 2011 22:48:07 +0300
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@...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@...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 @ 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:48:13 CEST

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:29 CEST