|
|||||
|
|
Two linear approximation algorithms for convex mixed integer nonlinear programming |
|
| Authors: | Melo Wendel Fampa Marcia Raupp Fernanda |
| Institution: | 1.College of Computer Science, Federal University of Uberlandia, Uberlandia, Brazil ;2.Institute of Mathematics and COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil ;3.National Laboratory for Scientific Computing of the Ministry of Science, Technology, Innovations and Communications, Rio de Janeiro, Brazil ; |
| 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |