Re: [eclipse-clp-users] Execution time

Hi,

There can be various reasons.
One reason could be that you found a phase transition.
It looks as if your instances were randomly generated: which parameters 
did you use to generate these instances?

If you used the same parameters for the two instances, then they could 
be the so-called "exceptionally hard problems" (see works by Barbara 
Smith and colleagues).
If this is the case, the usual solution is to use a randomized search 
strategy with restarts at increasing timeouts (see works by Carla Gomes 
and colleagues).

As a basic implementation, you could change your search strategy as follows:

     TimeOut::1..300,
     bb_min((
        indomain(TimeOut), writeln(timeout(TimeOut)),

        bb_min((
         search(Starts, 0, smallest, indomain_random, complete, []),
         search([R], 0, smallest, indomain, complete, [])
        ),
        Cost, bb_options{strategy: restart, delta: 0.0001,
                         timeout: TimeOut, report_failure: Cost})
     ),
     Cost, bb_options{strategy: restart, delta: 0.0001,
                      report_failure: Cost}),

Of course, this linearly increasing timeout is very simplistic; Luby 
sequences would probably give better results:

http://www.cs.berkeley.edu/~sinclair/vegas.ps

Cheers,
Marco

On 21/09/10 11:06, Jacky wrote:
> Hi all,
>
> 	I am running my experiments in CLP, and notice that the execution times
> of some experiments were very long (>  15 hours, and still waiting) no
> matter what selection method I used. These experiments seem to be in the
> same complexity level as those which can be finished within several
> seconds if the right selection method was chosen.
>
> 	So I wonder how to deal with these experiments, and why CLP behaves
> like this. I've attached two experiments. r30_4.ecl have not finished
> execution yet, while r30_9.ecl gave me the optimal within 1 second.
>
> 	Any ideas? Thanks.
>
> Regards,
> Jacky

-- 
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/