[gecode-users] Optimization

[Peter Vanhee]

Thanks for the answer. Conceptually, I see a problem in the energy constraint:
it can only work if all variables are instantiated. Would it make sense to write
a function that posts the energy constraint? Something like

void energy(Home home, const IntVarArgs& x, double n, IntConLevel icl=ICL_DEF);

that would then implement a propagator that will get called once all variables
are instantiated, checks if the energy is better than n, and if not, fails the space.

I could then probably call this constraint within the constrain() function and bypass
use of static variables. Still, it wouldn't change the search tree, but this is
simply because the energy constraint is unable the domains. Is this correct
reasoning? The static variable seemed much easier to implement than implementing
a post function.

I hadn't given it a thought to convert the double to an int, but would this make
sense if there is nothing to prune?

Thanks a lot,
Peter

On 3 Feb 2010, at 16:39, Christian Schulte wrote:

> Hi,
> 
> The problem with your solution is that you do not use branch and bound for
> search (as you basically say yourself): what you will do is basically find
> all solutions and pick a best one among them (provided I really understand
> what you are doing). The idea of branch and bound is to add a constraint
> after a solution has been found such that the additional constraint will
> guarantee that a better solution is found next and - crucially! - the added
> constraint can prune the search space by triggering additional propagation.
> 
> Moreover, your idea is not compatible with parallel search (static
> variable).
> 
> Did you think about turning your double value into a sufficiently accurate
> integer variable?
> 
> Christian
> 
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
> 
> 
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Peter Vanhee
> Sent: Wednesday, February 03, 2010 4:30 PM
> To: users at gecode.org
> Subject: [gecode-users] Optimization
> 
> Hi all,
> 
> I am working on an optimization problem defined using constraints,
> to compute the lowest energy model of a protein lattice. My variables are
> implemented as integer variables that refer to a pool of protein fragments,
> and I wish to implement an optimization function that - given an assignment
> of all variables - returns an energy value (double) that should be
> minimized.
> 
> So far, I've implemented the optimization as follows:
> 
> - in the model constructor, I use synchronized execution to call a function
> c when all variables become assigned (using wait(Space&, IntVarArray&, c&)
> 
> - a static variable that holds the best energy so far
> 
> static BEST_ENERGY = 10000;
> 
> - the continuation function c looks something like 
> 
> static void c(Space& _home) {
> 	// compute energy using assigned variables
> 	double energy = ...;
> 
> 	if(energy > BEST_ENERGY) {
> 		// fail if energy is worse
> 		home.fail();
> 	} else {
> 		BEST_ENERGY = energy;
> 	}
> }
> 
> 
> This works fine, and I can use different search algorithms to traverse the
> tree
> and move into the direction of lowest energy. However, I am not sure if this
> is the 
> correct way. Initially, I thought about implementing the cost() function but
> quickly
> discarded it because it only seems to work with integer variables. Also
> using the
> constrain function I need to use a static variable as well, and I don't know
> what
> kind of constrained I should post there (the energy function can not prune
> domains,
> it can either accept it as better or fail the space..)
> 
> Thanks for the clarification!
> Peter
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>