Optimization Online


A disjunctive cut strengthening technique for convex MINLP

Jan Kronqvist (j.kronqvist***at***imperial.ac.uk)
Ruth Misener (r.misener***at***imperial.ac.uk)

Abstract: Generating polyhedral outer approximations and solving mixed-integer linear relaxations remains one of the main approaches for solving convex mixed-integer nonlinear programming (MINLP) problems. There are several algorithms based on this concept, and the efficiency is greatly affected by the tightness of the outer approximation. In this paper, we present a new framework for strengthening cutting planes of nonlinear convex constraints, to obtain tighter outer approximations. The strengthened cuts can give a tighter continuous relaxation and an overall tighter representation of the nonlinear constraints. The cuts are strengthened by analyzing disjunctive structures in the MINLP problem, and we present two types of strengthened cuts. The first type of cut is obtained by reducing the right-hand side value of the original cut, such that it forms the tightest generally valid inequality for a chosen disjunction. The second type of cut effectively uses individual right-hand side values for each term of the disjunction. We prove that both types of cuts are valid and that the second type of cut can dominate both the first type and the original cut. We use the cut strengthening in conjunction with the extended supporting hyperplane algorithm, and numerical results show that the strengthening can significantly reduce both the number of iterations and the time needed to solve convex MINLP problems.

Keywords: Disjunctive cuts, Convex MINLP, Cut strengthening, Extended supporting hyperplane algorithm

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Submitted to Optimization and Engineering

Download: [PDF]

Entry Submitted: 08/06/2020
Entry Accepted: 08/06/2020
Entry Last Modified: 08/06/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society