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

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 _at_ 1.0}, _1034{1.0 .. 3.0 @ 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 _at_ 2.0}, _1153{1.0 .. 3.0 @ 3.0000000000000009}, 
_1170{1.0 .. 3.0 _at_ 2.0}, _1187{1.0 .. 3.0 @ 2.0}, _1204{1.0 .. 3.0 @ 
2.0}, _1221{1.0 .. 3.0 _at_ 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 @ 
2.0}, _1357{1.0 .. 3.0 _at_ 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 @ 
3.0000000000000009}, _1442{1.0 .. 3.0 _at_ 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/