[eclipse-clp-users] RES: minlist /2 in a Point list

From: Igor Kondrasovas <igor_at_inovativatec.com>
Date: Tue, 25 May 2010 11:25:58 -0300
Hello Joachim,

You are right, the bb_min is working fine. It actually finds a solution very quickly, the issue is in finding other solutions. It is taking much time to process very simple cases.

In my scenario I have a bi-dimensional domain (X and Y) where both are integers form 0 to 300. I'm trying to find 4 points in this space in a processing operation that is taking more than 8 hours and still running...

The goal of my research is actually explore this strategies for solving the nesting decision problem using CLP. As you may have noticed I'm experiencing more challenges and difficulties to move on than I initially thought (prolog and clp fundamentals). But I will not give up !.

Don't you think it is a little bit strange taking so long for the solution to explore all domain space? I really cannot estimate that...

As you mentioned, creating a "2-D aware search routine" to implement a search heuristic is something I imagine but have no idea how to do at the moment. I was thinking about using different search / 6 variations to explore more possibilities and see how they influence the results. It would be important to explore study cases I do not have to wait for so long to get results and move forward...

What do you suggest?


Igor Kondrasovas
Twitter: @ikondrasovas
Blog: http://ikondrasovas.wordpress.com
Facebook: www.facebook.com/ikondrasovas

-----Mensagem original-----
De: Joachim Schimpf [mailto:joachim.schimpf_at_infotech.monash.edu.au] 
Enviada em: quarta-feira, 19 de maio de 2010 02:24
Para: eclipse-clp-users_at_lists.sf.net
Assunto: Re: [eclipse-clp-users] minlist /2 in a Point list

Igor Kondrasovas wrote:
> Hello,
> I would like to use the the bb_min /3 predicate to find the lowest
> “Cost” solution available in my search / 6 results:
> The search is: search(XYs, 0, first_fail, indomain_split, complete, []),
> XYs is a list of points (X,Y) elements and the cost is equals to the
> maximum X value on the entire list, so my goal is to minimize this cost.
> I would like to know if I could use maxlist /2 to define the cost value
> or if there is any built-in predicate I could use, since it is not a
> simple scalar numeric list (only X value is considered).

Your code is perfectly fine (you do need to construct the auxiliary list
of Xs).  By the way, maxlist(Xs,Cost) is the same as Cost #= max(Xs).

> Here is the way I´m defining the predicate. In fact the code hangs when
> the bb_min is used.

First try doing the search without the bb_min: does it find a solution?

If yes, it should at least find that same first solution with the bb_min,
print "Found a solution with cost ....", and then go on trying to find a
better one.

It is also quite likely that you need to consider a search heuristic that
is better suited to the geometrical problem you have.  What I mean is that
your overlap constraints are of the form "no x overlap OR no y overlap".
When you have an object at (x1,y1) which must not overlap with (X,Y), then
that does not restrict the domains of X or Y, because they are allowed to
overlap in one of the dimensions.  A 2-D aware search routine could explore
the possible relative position of pairs of objects by imposing branching
constraints of the form X>x1 or X<x1 or Y>y1 or Y<y1.

-- Joachim


ECLiPSe-CLP-Users mailing list
Received on Tue May 25 2010 - 14:29:14 CEST

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