Paper Info
Title
Two linear approximation algorithms for convex mixed integer nonlinear programming
Abstract
We present two new algorithms for convex Mixed Integer Nonlinear Programming (MINLP), both based on the well known Extended Cutting Plane (ECP) algorithm proposed by Weterlund and Petersson. Our first algorithm, Refined Extended Cutting Plane (RECP), incorporates additional cuts to the MILP relaxation of the original problem, obtained by solving linear relaxations of NLP problems considered in the Outer Approximation algorithm. Our second algorithm, Linear Programming based Branch-and-Bound (LP-BB), applies the strategy of generating cuts that is used in RECP, to the linear approximation scheme used by the LP/NLP based Branch-and-Bound algorithm. Our computational results show that RECP and LP-BB are highly competitive with the most popular MINLP algorithms from the literature, while keeping the nice and desirable characteristic of ECP, of being a first-order method.
Year
DOI
Venue
2022
10.1007/s10479-020-03722-5
Annals of Operations Research
Keywords
DocType
Volume
Mixed integer nonlinear programming, Extended cutting plane, Outer approximation, Linear approximation
Journal
316
Issue
ISSN
Citations 
2
0254-5330
0
PageRank 
References 
Authors
0.34
8
3
Name
Order
Citations
PageRank
Wendel Melo1133.02
Marcia Fampa25811.69
Fernanda M. P. Raupp3295.35