Many real-world problems involve optimizing over decisions that take discrete set of values. Examples of such problems include routing vehicles in a logistics network, VLSI circuit design, gene sequencing, portfolio selection, wireless network design and many others. Large-scale instances of such problems are extremely difficult to solve and require both theoretical and computational advancements in solution approaches. This project is aimed at development of theory and computational enhancements for Functional Annealing (FA) algorithm to solve large-scale discrete optimization problems. FA is a stochastic local search algorithm that performs local improvement while randomly perturbing the objective function in each iteration. The random perturbation allows the algorithm to escape local optima and can also be used to guide the stochastic search in the solution space by creating bias. The algorithm can be used with any local improvement strategy. These features make the algorithm computationally more attractive but significantly harder to analyze theoretically compared to well-known algorithms such as Simulated Annealing. The proposed work involves investigating asymptotic and finite time convergence properties of FA. It also seeks to identify computational enhancements of the algorithm by finding the optimal choice of perturbation, and incorporating learning schemes in the generation of bias in the perturbation. As part of the computational investigation, FA algorithms will be developed for two important problem classes. The first class is the network design problems arising in logistics applications. The PI will work with an industry partner in package shipment industry to develop and test the algorithms on real-world instances of network design problems. The second class is the unconstrained quadratic binary programming problems. This class models a large number of combinatorial optimization problems.
If successful, the proposed work will lead to development of efficient algorithms for very large instances of discrete optimization problems with provable convergence guarantees. Theoretical results from this work would improve the understanding of other stochastic local search methods as well. The work on network design problems could lead to new algorithms and software tools for planning problems in logistics. The computational testing for unconstrained quadratic binary programming problems could generate a powerful solution tool for many researchers and practitioners, given its broad applicability. Software developed during the research would be available as part of the Metaheuristic Cyber Infrastructure for Operations Research to give easy access to researchers and practitioners.
