Branch and Bound Experiments in Convex Nonlinear Integer Programming

Omprakash K. Gupta and A. Ravindran
Additional contact information
Omprakash K. Gupta: Indian Institute of Management, Ahmedabad--380015, India
A. Ravindran: School of Industrial Engineering, University of Oklahoma, Norman, Oklahoma 73019

Management Science, 1985, vol. 31, issue 12, 1533-1546

Abstract: The branch and bound principle has long been established as an effective computational tool for solving mixed integer linear programming problems. This paper investigates the computational feasibility of branch and bound methods in solving convex nonlinear integer programming problems. The efficiency of a branch and bound method often depends on the rules used for selecting the branching variables and branching nodes. Among others, the concepts of pseudo-costs and estimations are implemented in selecting these parameters. Since the efficiency of the algorithm also depends on how fast an upper bound on the objective minimum is attained, heuristic rules are developed to locate an integer feasible solution to provide an upper bound. The different criteria for selecting branching variables, branching nodes, and heuristics form a total of 27 branch and bound strategies. These strategies are computationally tested and the empirical results are presented.

Keywords: programming: integer algorithms; branch and bound; programming: integer algorithms; tests; programming: nonlinear; algorithm tests (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (45)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.31.12.1533 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:31:y:1985:i:12:p:1533-1546

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().