EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3573. Warm Starting of Outer Approximation for Biobjective MINLPs

Invited abstract in session WA-4: Algorithms for Mixed-Integer Nonlinear Programming and Nonconvex Optimization, stream MINLP.

Wednesday, 8:30-10:00
Room: 1001 (building: 202)

Authors (first author is the speaker)

1. Erik Tamm
Department of Mathematics, KTH Royal Institute of Technology
2. Jan Kronqvist
Mathematics, KTH Royal Institute of Technology

Abstract

Multiobjective mixed-integer nonlinear programming is a challenging type of problem to solve even when the continuous relaxation is convex. This work presents two new methods which attempts to solve convex biobjective MINLPs efficiently. This is done by considering the so-called epsilon-constraint method for a biobjective problem. Since the set of nondominated points is in general not convex due to integrality constraints, the classic weighted sum method is not suitable. The epsilon-constraint method solves a sequence of similar convex MINLPs to approximate the set of nondominated points. Each subproblem can be solved using outer approximation, where a polyhedral approximation is obtained. The main contribution of the work is the two methods presented of how to reuse the polyhedral approximation from a solved subproblem when solving the next one. The methods are derived from two observations. First, the subproblems are by construction increasingly restrictive, which means that a valid cut will be valid for all the following subproblems. Second, the problems are only slightly changed, which means that the integer combinations needed to be visited should be similar between subproblems. Preliminary results show that there is a noticeable improvement in both solution time and the number of iterations needed to solve each subproblem.

Keywords

Status: accepted

Back to the list of papers