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

Am 06.10.2011 15:40, schrieb Marco Gavanelli:
> Hi,
>
> [...]
> This particular problem is probably solved faster with an integer 
> programming model.

Hi Marco,

I think you can also do it fast with CLP alone. I had a private email 
exchange with Sergey over the last days, since I wasn't sure I had 
understood the problem correctly, and at the end we had a program that 
ran quite fast.

In order to speed up the CLP program, you should label the binary 
variables that denote whether a state switch happens at a given position 
instead of the variables that denote the state. You can add a sumlist 
constraint on the list of switch variables. Also, I added a new 
constraint that connects switch variables and state variables.

What Sergey then found was that the program would find a solution very 
fast, but proving its optimality was taking a long time. However, with 
labeling the switch variables, trying Switches[I] #= 0 first and thereby 
adding a States[I]#=States[I+1] constraint, the program in a way builds 
sequences of maximal length of states that must have the same value. 
Only if the next state variable can't be added to the sequence, since 
the intersection of its domain with the domains of the other variables 
in the sequence (all connected through #=/2 constraints) will be empty, 
will the program switch the state. You can probably prove that that 
strategy is optimal and do away with branch-and-bound.

The CLP program now takes 0.2 seconds for randomly generated test cases 
for queries of length 1000 and 100 different states, with optimality 
proven in about 3 seconds. I tested your eplex version with CPLEX 12.2 
and it takes about 28 seconds for such cases.

But those randomly generated test cases were too simple, it seems.

Here is a test case that Sergey supplied where proving optimality was 
too expensive for CLP:

solve(9, [](1, 2, 1, 4, 5, 6, 7, 4, 3, 1, 2, 3, 4, 5, 6, 7, 8, 9,
              9, 8, 7, 6, 5, 4, 3, 2, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1,
              9, 8, 3, 2, 1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 9, 8, 3, 2,
              1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 9, 8, 3, 2, 1, 9, 8, 7,
              6, 5, 4, 3, 2, 1, 9, 8, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9,
              1, 1, 2, 3, 4, 5, 6, 7, 8, 9), S).

Assuming that the strategy is optimal and using search/6 alone, it can 
be solved in 0.01 seconds. Proving optimality takes forever with the CLP 
program, though  (I stopped it eventually). Your eplex program takes 0.5 
seconds with CPLEX to find a (proven) optimal solution.

I was wondering whether you could show that you need a certain number of 
sequences, where the number of different queries in each sequence is one 
less than the number of available states, to cover the whole length of 
the queries by modeling it with set constraints. But I'm not sure 
whether the set constraints available in ECLiPSe allow that.

Cheers,
Thorsten