Combinatorial optimization with one quadratic term: spanning trees and forests

DOI10.1016/J.DAM.2014.05.031MaRDI QIDQ406320zbMATH OpenOpenAlexFDO

Authors Christoph Buchheim, Laura Klein

Publication date 8 September 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2014.05.031

zbMATH Keywords

binary quadratic programmingquadratic spanning tree polytope

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Boolean programming (90C09)

Recommendations

• Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
• Complete description for the spanning tree problem with one linearised quadratic term
• scientific article; zbMATH DE number 35513
• Polyhedral results, branch‐and‐cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation

Cites work

• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• Combinatorial optimization with one quadratic term: spanning trees and forests
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complete description for the spanning tree problem with one linearised quadratic term
• Geometric algorithms and combinatorial optimization.
• L’algebre de Boole et ses applications en recherche operationnelle
• On The Boolean Quadric Forest Polytope
• On minimum changeover cost arborescences
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Solving the quadratic minimum spanning tree problem
• Speeding up IP-based algorithms for constrained quadratic 0-1 optimization
• The complexity of a minimum reload cost diameter problem
• The cut polytope and the Boolean quadric polytope
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm

Cited in

(14)

• Multilinear sets with two monomials and cardinality constraints
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• The quadratic minimum spanning tree problem and its variations
• Combinatorial optimization with one quadratic term: spanning trees and forests
• Matroid optimization problems with monotone monomials in the objective
• Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs
• Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem
• On the path avoiding forbidden pairs polytope
• A class of valid inequalities for multilinear 0-1 optimization problems
• An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations
• Complete description for the spanning tree problem with one linearised quadratic term
• Matroid optimisation problems with nested non-linear monomials in the objective function
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• Computational methods for logistics problems related to optimal trees

Describes a project that uses

Uses Software

• SCIL

This page was built for publication: Combinatorial optimization with one quadratic term: spanning trees and forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q406320)