# Optimisation Problem

I'm given a lattice with particles having charges which have known magnitude but unknown signs. The primary aim is to stabilize the lattice (or decrease the force acting on the system) by assigning signs to the charges so that the sum of the products of neighboring charges is minimum, that is, I'll take products of charges of each particle with its neighbor and take the sum across the whole crystal (a pair is considered only once). So my aim is to assign +ve/-ve signs to the charges in crystal to minimize the total force on the crystal. The smaller the value of force (in negative side as well), the more stabilized the crystal . For simplification I've assumed a square lattice represented by a matrix, where north, south, east and west particles are neighbors,

The only solution that I can think of right now is bruteforcing all possible combinations.

-

## 2 Answers

This isn't a real answer, but the question reminds me of the Ising model. If the literature about this model doesn't lead to an appropriate algorithm, then you can probably use some kind of branch and bound search to gain some speed over literally trying all possible combinations. Or if you only need an approximation then you can use something like simulated annealing.

-
I's reading through notes on simulated annealing and branch and bound algorithm . it seems a perfect match . just one curious ques they all belong to the genetic algorithm category,dont they ? – Malice Jan 24 '12 at 15:44

What about Hopfield networks? I guess you could set the weights to 0/1 depending on a neigbouring condition. Hopfield networks start from the assumption that you can formulate the target as a quadratic function and the solutions lie at the vertices of the hypercube $[-1,1]^n$, which I think is your case.

Admittedly, the performance of Hopfield networks is disputed...

-