Global Non-Convex Optimization with Integer Variables

Non-convex optimization refers to the process of solving problems whose objective or constraints are non-convex. Historically, this type of problems have been very difficult to solve to global optimality, with traditional solvers often relying on approximate solutions. Bertsimas et al. [1] introduce a novel approach for solving continuous non-convex optimization problems to provable optimality, called the Relaxation Perspectification Technique - Branch and Bound (RPT-BB). In this thesis, we extend the RPT-BB approach to the binary, mixed-binary, integer, and mixed-integer variable domains. We outline a novel branch-and-bound algorithm that makes use of the Relaxation Perspectification Technique (RPT), as well as binary, integer, and eigenvector cuts. We demonstrate the performance of this approach on two representative non-convex problems, as well as two real-world non-convex optimization problems, and we benchmark its performance on BARON and SCIP, two state-of-the-art optimization solvers for non-convex mixed-integer problems. We observe that our algorithm, despite being more general, is able to outperform the state-of-the-art solvers on many problem instances.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Kriezis, Demetrios C.

Advisor dc:contributor.advisor

• Bertsimas, Dimitris

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/162709

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/162709