From: Thorsten Winterer <thorsten_winterer_at_web.de>

Date: Thu, 06 Oct 2011 16:31:03 +0200

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

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

- text/x-eclipse attachment: switches.ecl

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*