Title: Inner approximations in mixed-integer nonlinear optimization
Speaker: Akshay Gupte (University of Edinburgh, UK)
Day, Date, and Time: Friday, 5th January, 2024, 03:30 PM
Venue: Seminar Room, IEOR, 2nd floor (Click here to join online)
Abstract: In this talk speaker will present two streams of work for generating good feasible solutions to mixed integer nonlinear programs. In the first part of the talk, we consider nonlinear integer programs and provide an approximation method that uses monomial orders on the integer lattice with different permutations of the variable order. An approximation factor is obtained, and it depends in some sense on the sparsity of the objective function. We also show that our method is exact (i.e., obtains the optimal solution) for binary problems. Although the method is not polynomial-time in general, we give some tractable approximations and implementable algorithms that are competitive in providing good solutions on benchmark test instances for linear and quadratic integer problems. This is joint work with my PhD student Yiran Zhu. A second idea is to do variable discretizations and reformulate the resulting problem into a mixed-integer linear program. I will talk about the many ways of doing this on mixed-integer quadratically constrained programs and how the discretizations can be adaptively refined in an iterative algorithm to improve the quality of solutions. Numerical tests on a wide range of test instances gives very good performance in comparison to global solvers. This is joint work with Arie Koster and Sascha Kuhnke at RWTH Aachen.
Bio: Akshay Gupte is a faculty member of the Optimization and Operational Research group within the School of Mathematics at the University of Edinburgh, UK. Before January 2020, he was a tenured Associate Professor of Mathematical Sciences at Clemson University, USA. His primary research interests are in convexification theory, algorithms, and applications of mixed-integer and nonconvex optimization, and he also has secondary research interests in areas of discrete mathematics, such as convex polytopes and graph theory. His research has been funded by government agencies in the US and UK, such as NSF, Naval Research, EPSRC. He is currently serving as the Chair of the INFORMS Computing Society, as the Treasurer and Council member of the Mixed Integer Programming Section of the Mathematical Optimization Society, and previously served as a Cluster Chair of the INFORMS Optimization Society. He is an Associate Editor at the journals Optimization and Engineering, and Operations Research Forum.