[gecode-users] Optimization

[Christian Schulte]

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