A computational comparison of branch and bound and outer approximation algorithms for 0–1 mixed integer nonlinear programs
Computers & Operations ResearchPublished 1 August 1997
Brian Borchers, John E. Mitchell
Citations43
SJR quartileQ1
SJR score1.60
SNIP2.02
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper compares the performance of two codes for convex 0–1 mixed integer nonlinear programs on a number of test problems and demonstrates that both approaches are generally capable of solving the test problems.
Abstract
In this paper we compare the performance of two codes for convex 0–1 mixed integer nonlinear programs on a number of test problems. The first code uses a branch and bound algorithm. The second code is a commercially available implementation of an outer approximation algorithm. The comparison demonstrates that both approaches are generally capable of solving the test problems. However, there are significant differences in the robustness of the two codes and their performance on different classes of problems.
Keywords
MathematicsEngineering
ACM SIGNUM NewsletterGAMS, a user's guide
2,989 Citations1988Anthony Brook, David A. Kendrick +1 more
JuMP is an open-source modeling language that allows users to express a wide range of ideas in an easy-to-use manner.
Mathematical ProgrammingAn outer-approximation algorithm for a class of mixed-integer nonlinear programs
1,436 Citations1986Marco A. Durán, Ignacio E. Grossmann
An outer-approximation algorithm is presented for solving mixed-integer nonlinear programming problems of a particular class and a theoretical comparison with generalized Benders decomposition is presented on the lower bounds predicted by the relaxed master programs.
Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications
957 Citations1995Christodoulos A. Floudas
Computers & Chemical EngineeringA combined penalty function and outer-approximation method for MINLP optimization
749 Citations1990J. Viswanathan, Ignacio E. Grossmann
The results show that although no theoretical guarantee can be given, the proposed method has a high degree of reliability for finding the global optimum in nonconvex problems.
Management ScienceBranch and Bound Experiments in Convex Nonlinear Integer Programming
489 Citations1985Omprakash K. Gupta, A. Ravindran
This paper investigates the computational feasibility of branch and bound methods in solving convex nonlinear integer programming problems and develops heuristics to locate an integer feasible solution to provide an upper bound.
Computers & Operations ResearchAn improved branch and bound algorithm for mixed integer nonlinear programs
241 Citations1994Brian Borchers, John E. Mitchell
An improved branch and bound code for zero-one mixed integer nonlinear programs with convex objective functions and constraints with Lagrangian duality is described.
Computers & Chemical EngineeringComputational experience with dicopt solving MINLP problems in process systems engineering
185 Citations1989Gary R. Kocis, Ignacio E. Grossmann
Results show that DICOPT provides a very efficient tool for solving MINLP problems, utilizing state-of-the-art optimization tools and a powerful modelling language.
Operations ResearchQuadratic Binary Programming with Application to Capital-Budgeting Problems
142 Citations1970Dan J. Laughhunn
The algorithm developed to solve the quadratic binary programming problem and hence necessary to generate the efficient set is based on the concept of implicit enumeration recently introduced by Egon Balas for solution of the binary linear programming problem.
Operations ResearchAPROS: Algorithmic Development Methodology for Discrete-Continuous Optimization Problems
77 Citations1989Granville Paules, Christodoulos A. Floudas
The flexibility of APROS and the highly procedural modeling language GAMS provide a means of obtaining quick solutions to difficult classes of problems by implementing a selected algorithm, and also provide a unique tool for developing, prototyping and experimenting with new algorithms.
Management ScienceAn Extension of Lawler and Bell's Method of Discrete Optimization with Examples from Capital Budgeting
50 Citations1968James C. T. Mao, B. A. Wallingford
This paper extends Lawler and Bell's method for solving integer linear programs with 0--1 decision variables so that it can be generally applied to integer quadratic programs.