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

From: Thorsten Winterer <thorsten_winterer_at_...126...>
Date: Thu, 06 Oct 2011 16:31:03 +0200
```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

```
Received on Thu Oct 06 2011 - 14:31:15 CEST

This archive was generated by hypermail 2.3.0 : Tue Aug 06 2024 - 21:13:21 CEST