In many applications such as power system operations, it is necessary to solve challenging Mixed Binary Quadratic Programming (MBQP) instances repeatedly. These instances typically have the same constraint matrix, representing data corresponding to some invariant physical infrastructure, but varying objective function and right-hand-side (rhs). This motivates the need to develop methodology for conducting sensitivity analysis of MBQPs. In this talk, we consider sensitivity analysis for MBQPs with respect to changing rhs. We show that even if the optimal solution of a given MBQP is known, it is NP-hard to approximate the change in objective function value with respect to changes in rhs. Next, we study algorithmic approaches to obtaining dual bounds for MBQP with changing rhs. We leverage Burer’s completely-positive (CPP) reformulation of MBQPs. Its dual is an instance of co-positive programming (COP) and can be used to obtain sensitivity bounds. We prove that strong duality between the CPP and COP problems holds if the feasible region is bounded or if the objective function is convex, while the duality gap can be strictly positive if neither condition is met. We also show that the COP dual has multiple optimal solutions, and the choice of the dual solution affects the quality of the bounds with rhs changes. Finally, we provide an algorithmic approach to find ``best values" of optimal dual solutions, and present preliminary computational results on sensitivity analysis for MBQPs. This is joint work with Diego Cifuentes and Jingye Xu.

Bio: Santanu S. Dey is a professor and director of doctorial recruiting and admissions in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. Dr. Dey's research interests are in non-convex optimization, and in particular mixed integer linear and nonlinear programming. His research is partly motivated by applications arising in areas such as electrical power engineering, process engineering, structural engineering, logistics, and statistics. Dr. Dey currently serves on the editorial board of Computational Optimization and Applications, Mathematical Programming A, Mathematics of Operations Research and SIAM Journal on Optimization. He has previously served as an area editor for Mathematical Programming C and associate editor of INFORMS Journal on Computing. He has won the INFORMS Nicholson student paper competition, IBM Faculty Award, the Class of 1969 Teaching Fellow at Georgia Tech, the NSF CAREER award, the INFORMS Energy Natural Resources and Environment best paper award, and the INFORMS optimization society Balas Prize. He has been a Diversity Fellow at Georgia Tech, and has held the Fouts Family Junior Professorship, the A. Russell Chandler III Professorship, and the Anderson-Interface Professorship at Georgia Tech.