RESEARCH PRESENTATION - RAY PÖRN
Applications of mixed integer and global optimization
Minimizing the energy of electron configuration in disordered materials
The Coulomb glass is a model for a disordered material, where the conduction electrons are localized to impurity sites and the electrons strongly interact with each other [1,2]. Given n possible sites where the k electrons can be localized, the problem is to find the electron configuration that minimizes the total energy of the system. A certain configuration of electrons in a material gives rise to a specific total energy of the system. If the configuration changes, so does its total energy. The problem of minimizing the total energy of the system, or equivalently finding its ground state, is a combinatorial optimization problem that can be modeled as zero-one quadratic programming problem. The energy function is likely to be non-convex and have a large number of local minimizers.
To get physically reasonable results the system should be large, preferably containing thousands of sites and electrons (n=1000, k=500). Due to the large size of these problems, they have usually been solved using heuristic methods that are fast but have no guarantee to actually find the global optimum, i.e. the ground state.
The objective of this research is three-fold: 1) To obtain a tight lower bound to the original problem; (2) to reformulate the original non-convex problem to an equivalent convex problem that has good characteristics, such as tight underestimation, and to (3) generalize this approach to other combinatorial problems. The main theoretical tool to achieve this is semidefinite programming [3,4]. A computational study using this technique is presented in [5].
A mixed integer quadratic formulation for the quadratic assignment problem
The quadratic assignment problem (QAP, [6]) is a strongly NP-hard combinatorial optimization problem. We develop a new mixed integer quadratic optimization model for the QAP that is especially suited for instances with low-rank flow or distance matrices (typically rank=1-2). The proposed formulation is much more efficient than standard linearization techniques.
Optimization based approaches for constructing finite Blaschke products
How to efficiently construct finite Blaschke products with prescribed critical points in the open complex unit disk is an open problem. We develop an optimization-based approach that aims to locate all solutions to a certain non-linear equation system.
Some references
[1] Shklovskii, B.I., Efros, A.L. Electron properties of doped semiconductors, Springer-Verlag, Berlin, 1984.
[2] Ortuño, M., Caravaca, M. and Somoza, A.M. Numerical Study of Relaxation in Coulomb Glasses, Physica Status Solidi (c), 5, 674–679, 2008.
[3] Billionett A., Elloumi S, Plateau M-C. Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method. Discrete Applied Mathematics 157 (2009) 1185-1197.
[4] Lemaréchal C., Oustry F. Semidefinite relaxations and lagrangian duality with application to combinatorial optimization.RR-3710, INRIA Rhones-Alpes (1999).
[5] Pörn R., Nissfolk O., Jansson F. and Westerlund T. (2011). The Coulomb Glass - Modeling and Computational Experience with a Large Scale 0-1 QP Problem. 21st European Symposium on Computer Aided Process Engineering - ESCAPE21, 658-662.
[6] QAPLIB - http://www.seas.upenn.edu/qaplib/