Convex mixed-integer optimization with Frank-Wolfe methods
This addresses computational challenges in mixed-integer nonlinear optimization for researchers and practitioners, but it appears incremental as it builds on existing branch-and-bound and Frank-Wolfe techniques.
The paper tackles mixed-integer nonlinear optimization problems by proposing a branch-and-bound method with convex node relaxations solved via a Frank-Wolfe algorithm over the convex hull of mixed-integer feasible points, resulting in a method that computes feasible solutions without outer approximation and exploits inexact subproblem solutions.
Mixed-integer nonlinear optimization encompasses a broad class of problems that present both theoretical and computational challenges. We propose a new type of method to solve these problems based on a branch-and-bound algorithm with convex node relaxations. These relaxations are solved with a Frank-Wolfe algorithm over the convex hull of mixed-integer feasible points instead of the continuous relaxation via calls to a mixed-integer linear solver as the linear minimization oracle. The proposed method computes feasible solutions while working on a single representation of the polyhedral constraints, leveraging the full extent of mixed-integer linear solvers without an outer approximation scheme and can exploit inexact solutions of node subproblems.