[gecode-users] Optimization

[Christian Schulte]

Hi Peter,

Hmm. Why are you so sure that the energy constraint only works if all
variables are already assigned? Don't think about a double as result but try
to think (just for the sake of argument) to express the result of the energy
function as an integer (with some approximation). Then it would be a
constraint between the problem variables and the variable for the energy.

The thing from which search can benefit is just the opposite case: you put a
constraint on the energy variable (derived from a solution found earlier by
search) and there is propagation that narrows down the potential values for
your problem variables.

Waiting for all the problem variables until they become assigned, then (as I
tried to express before) normal search will do as branch and bound search
offers no advantage. Even implementing a propagator that waits until all
variables become assigned and then computes an energy value would not help.
All of this is equivalent to:
	- find a first solution and compute its energy value
      - keep finding all solutions and discard the worse ones and update to
the better ones
And this, of course, is not really feasible for most problems!

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:56 PM
To: Christian Schulte
Cc: users at gecode.org
Subject: Re: [gecode-users] Optimization

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
> 


_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users