Optimization Online


Strong Branching Inequalities for Convex Mixed Integer Nonlinear Programs

Mustafa KılınÁ (mrk46***at***pitt.edu)
Jeff Linderoth (linderoth***at***wisc.edu)
James Luedtke (jrluedt1***at***wisc.edu)
Andrew Miller (Andrew.Miller***at***math.u-bordeaux1.fr)

Abstract: Strong branching is an effective branching technique that can significantly reduce the size of the branch-and-bound tree for solving Mixed Integer Nonlinear Programming (MINLP) problems. The focus of this paper is to demonstrate how to effectively use discarded information from strong branching to strengthen relaxations of MINLP problems. Valid inequalities such as branching-based linearizations, various forms of disjunctive inequalities, and mixing-type inequalities are all discussed. The inequalities span a spectrum from those that require almost no extra effort to compute to those that require the solution of an additional linear program. In the end, we perform an extensive computational study to measure the impact of each of our proposed techniques. Computational results reveal that existing algorithms can be significantly improved by leveraging the information generated as a byproduct of strong branching in the form of valid inequalities.


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

Citation: Technical Report, Computer Science Department, University of Wisconsin-Madison

Download: [PDF]

Entry Submitted: 09/03/2011
Entry Accepted: 09/03/2011
Entry Last Modified: 09/04/2011

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