Optimization Online


Combinatorial Optimization with One Quadratic Term: Spanning Trees and Forests

Christoph Buchheim (christoph.buchheim***at***tu-dortmund.de)
Laura Klein (laura.klein***at***tu-dortmund.de)

Abstract: The standard linearization of a binary quadratic program yields an equivalent reformulation as an integer linear program, but the resulting LP-bounds are very weak in general. We concentrate on applications where the underlying linear problem is tractable and exploit the fact that, in this case, the optimization problem is still tractable in the presence of a single quadratic term in the objective function. We propose to strengthen the standard linearization by the use of cutting planes that are derived from jointly considering each single quadratic term with the underlying combinatorial structure. We apply this idea to the quadratic minimum spanning tree and spanning forest problems and present complete polyhedral descriptions of the corresponding problems with one quadratic term, as well as efficient separation algorithms for the resulting polytopes. Computationally, we observe that the new inequalities significantly improve dual bounds with respect to the standard linearization, particularly for sparse graphs.

Keywords: Quadratic Spanning Tree Polytope, Binary Quadratic Programming

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (0-1 Programming )

Category 3: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 07/11/2013
Entry Accepted: 07/12/2013
Entry Last Modified: 04/11/2014

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