Title: Solving nonconvex discrete diversity location problems with cutting planes

Speaker: Dr Hoa Bui

Summary:

The problem of diversity location problems involves choosing a subset of locations from a broader set to optimise the sum of distances. While significant progress has been made in exact methods for related variants, such as max-min and max-mean problems, finding a fast exact solver for the max-sum diversity problem remains an open problem. The max-sum problem is the most widely studied problem variation, yet very few exact methods exist. One of the reasons for this is that the problem is generally nonconvex, making traditional convex optimisation techniques unsuitable. We show that cutting plane method, traditionally designed for convex problems, converges for these nonconvex problems, even in the absence of convexity. This leads to stronger cuts and faster convergence. Numerical results show that cutting plane algorithm outperforms other exact methods for benchmark diversity problems (capacitated, generalised and max sum), and can easily solve problems of up to three thousand variables.At the end of the talk, we show that this technique can even be applied to “de-convexity” convex quadratic problems to enhance the convergence speed.

Biography:

Dr Hoa Bui is a research fellow at ARC Training Centre for Transforming Maintenance through Data Science and Curtin Centre for Optimisation and Decision Science. Her research interests include operations research, discrete optimisation, convex analysis, and graph theory. Her current focus is on developing efficient algorithms for solving nonconvex discrete optimisation problems and developing optimisation scheduling platform for maintenance scheduling for mining industry.

MEETING ID: 873 1557 5255; PASSWORD: 778635

WED 18 SEPTEMBER 2024 16:00-17:00 (AEST, Melbourne Time)