Implementation of a unimodularity test

DOI10.1007/S12532-012-0048-XMaRDI QIDQ1947200zbMATH OpenOpenAlexFDO

Authors Matthias Walter, Klaus Truemper

Publication date 12 April 2013

Published in Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.4061

zbMATH Keywords

polynomial testtotal unimodularityunimodularity

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: This paper describes implementation and computational results of a polynomial test of total unimodularity. The test is a simplified version of a prior method. The program also decides two related unimodularity properties. The software is available free of charge in source code form under the Boost Software License.

Recommendations

• scientific article; zbMATH DE number 221298
• A decomposition theory for matroids. V: Testing of matrix total unimodularity
• Total weak unimodularity: Testing and applications
• On pseudounimodular matrices
• A unimodular problem of integer programming

Cites work

• A decomposition theory for matroids. V: Testing of matrix total unimodularity
• A decomposition theory for matroids. VII: Analysis of minimal violation matrices
• Algebraic Characterizations of Unimodular Matrices
• An efficient PQ-graph algorithm for solving the graph-realization problem
• Complement total unimodularity
• Converting Linear Programs to Network Problems
• Decomposition of regular matroids
• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 3133252 (Why is no real title available?)
• scientific article; zbMATH DE number 3185974 (Why is no real title available?)
• Local Unimodularity in the Matching Polytope
• Local unimodularity of matrix-vector pairs
• Minimum partition of a matroid into independent subsets
• Random Graphs

Cited in

(14)

• Computing the spark: mixed-integer programming for the (vector) matroid girth problem
• On the recognition of \(\{a,b,c\}\)-modular matrices
• Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
• Notes on \(\{a,b,c\}\)-modular matrices
• Sparse recovery with integrality constraints
• Computing convex hulls and counting integer points with \texttt{polymake}
• Unimodularity Test
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Stable matching: An integer programming approach
• Torsion-weighted spanning acycle entropy in cubical lattices and Mahler measures
• Implied integrality in mixed-integer optimization
• A mathematical programming approach for recognizing binet matrices
• Recognizing integrality of weighted rectangles partitions

Describes a project that uses

Uses Software

• Leibniz
• Unimodularity
• Boost

This page was built for publication: Implementation of a unimodularity test

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