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

From: Sergey Dymchenko <kit1980_at_gmail.com>
Date: Thu, 6 Oct 2011 22:41:48 +0300
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