Nonlinear Multidimensional Assignment Problems Efficient Conic Optimization Methods and Applications.

摘要

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*10^26. 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.