[eclipse-clp-users] Search-Effort Prediction

From: Amine Marref <cyborgamine_at_...32...>
Date: Thu, 28 Jan 2010 12:36:13 +0000

Assume that I have started solving a COP problem using Eclipse. Is it possible to predict whether the satisfaction of the COP will take long time based on the current state of search e.g. the state of the branch-and-bound? Is there any accessible internal data that enable me to make predictions about how much effort is yet to be spent?

In [1] I include a more elaborate description.



[1] Motivation
I am trying to solve the following problem.

I have a CLP problem P expressed in Eclipse. In order to solve P, an assignment to the list of variables V in P must be found. The time T to find a solution to P will depend on the ordering of the list of variables V in P. It might depend on other factors as well such as the ordering of values in the domains of the variables. In this case, we are only interested in the effect of the ordering of V in P on T.

I want to find the ordering of variables V that gives the shorest solution time T for problem P. 

For example, let V have 5 variables. I could try solving P for 5! times, and obtain V that causes T to be minimum in all 5! times.

When the size of V is large, this type of exhaustive testing is not possible. Instead, I will use an optimization method, such as a genetic algorithm. The idea is to be able to predict that a particular V list is going to lead to large solution times by starting the solving of P for some time, and based on current state of branch-and-bound, get a prediction (reasonably accurate) which tells me that V will cause T to be large for instance.

In short, if T is the time to find the solution of P which depends on ordering of V, is it possible to predict with reasonable accuracy that T is going to be large? Such prediction must be performed within a small amount of time t after the solving of the problem has started.

Received on Thu Jan 28 2010 - 12:44:39 CET

This archive was generated by hypermail 2.3.0 : Mon Aug 26 2019 - 09:14:36 CEST