Accession Number : ADA627005


Title :   Nonlinear Multidimensional Assignment Problems Efficient Conic Optimization Methods and Applications


Descriptive Note : Final rept. Apr 2012-Mar 2015


Corporate Author : ARIZONA STATE UNIV TEMPE OFFICE OF RESEARCH AND SPONSORED PROJECT ADMINISTRATION


Personal Author(s) : Mittelmann, Hans D


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a627005.pdf


Report Date : 24 Jun 2015


Pagination or Media Count : 8


Abstract : The major goals of this project were completed: the exact solution of previously unsolved challenging combinatorial optimization problems. The size 16 three-dimensional quadratic assignment problem Q3AP from wireless communications was solved using a sophisticated approach with orbital shrinking and other techniques to exploit its symmetry. This problem has complexity (16!)2 which is about 4.4*1026. Another combinatorial optimization problem, the Directional Sensor Problem, was solved in two ways. First, heuristically in an engineering fashion and second, exactly after convexification. This had not been done before. While the Q3AP was solved in a linearized form leveraging the power of available MILP solvers, the sensor problem was solved as a nonlinear MINLP problem. Specifically, the information gain obtained was maximized in order to determine the optimal placement of the sensors. However, available MINLP solvers are not sufficiently effective, even in the convex case, and a hybrid Benders decomposition method was developed and applied. Results were published or submitted for publication and presented at several international conferences and a large number of research centers and universities around the world.


Descriptors :   *MATHEMATICAL PROGRAMMING , *WIRELESS COMMUNICATIONS , OPTIMIZATION


Subject Categories : Operations Research
      Radio Communications


Distribution Statement : APPROVED FOR PUBLIC RELEASE