Optimization of the Coulomb Glass Ground State

April 25, 2014

Fredrik JanssonI am a physicist working on the theory of charge transport in disordered materials. I have been studying materials such as amorphous semiconductors and organic semiconductors, e.g. conductive polymers.

One problem from my field of physics can be formulated as an optimization problem – finding the ground state of a Coulomb glass. The Coulomb glass ground state can then be studied with methods from the field of global optimization. The Coulomb glass model (1, 2) describes a semiconductor at a very low temperature, up to a few Kelvin.

We assume the electrons to be localized to impurity atoms in the material. The impurities are distributed in space somehow, either randomly or on a lattice. The electrons repel each other, and try to be as far from each other as possible. The task is to find the ground state of this system, that is, find how the electrons should be placed so that the total energy is minimized. The optimal placement is a balance between placing the electrons far from each other and placing the electrons on favorable sites. All electrons interact with each other, which makes this problem difficult.

This problem can be formulated as a binary quadratic optimization problem (3). This optimization problem is still very hard (in fact it is in NP), but branch-and-bound methods makes it possible to find the global optimum of much larger systems than what could be solved by brute force. In the physics community, the problem has been studied with different heuristic algorithms (4, 5). These are efficient in the sense that they quickly find “good” solutions, but they cannot prove that the global optimum has been found. Thus, the exact optimization methods is a nice complement to the heuristic methods already in use.

Some references

(1) M. Pollak, Effect of carrier-carrier interactions on some transport properties in disordered semiconductors, Discuss. Faraday Soc. 50, 13 (1970).
http://dx.doi.org/10.1039/DF9705000013

(2) B. I. Shklovskii and A. L. Efros, Electronic Properties of Doped Semiconductors (Springer-Verlag, 1984).
http://www.tpi.umn.edu/shklovskii/

(3) R. Pörn, O. Nissfolk, F. Jansson, and T. Westerlund, The Coulomb Glass – Modeling and Computational Experience with a Large Scale 0-1 QP Problem, Proceedings of ESCAPE 21, Computer Aided Chemical Engineering 29, 658 (2011)
http://dx.doi.org/doi:10.1016/B978-0-444-53711-9.50132-2

(4) S. Baranovskii, A. Efros, B. Gelmont, and B. Shklovskii, Coulomb gap in disordered systems: Computer simulation, Solid State Commun.27, 1 (1978).
http://dx.doi.org/10.1016/0038-1098(78)91038-4

(5) A. Möbius, M. Richter, and B. Drittler, Coulomb gap in two- and three-dimensional systems: Simulation results for large samples, Phys. Rev. B 45, 11568 (1992).
http://dx.doi.org/10.1103/PhysRevB.45.11568