Optimization Online


Polyhedron Flatness as an explanatory variable for Branch and Bound algorithm computational effort

Ivan Derpich (iderpich***at***gmail.com)
Carlos Herrera (carlos.herrera***at***udec.cl)

Abstract: This paper uses the polyhedron flatness and relevant computation variables to describe the computational effort of the Branch and Bound algorithm. These measures are explanatory variables for the number of nodes of the Branch and Bound algorithm . The polyhedron flatness is the quotient between the highest and lowest eigenvalues of an ellipse inside the polyhedron matrix. Several experiments were made showing interesting relation between the polyhedron flatness and number of nodes and Cpu Time in the $B\&B$ algorithm.

Keywords: Integer programming, Branch and Bound, Conditioning measures

Category 1: Integer Programming

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )



Entry Submitted: 10/09/2013
Entry Accepted: 10/10/2013
Entry Last Modified: 10/10/2013

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