Integer program with bimodular matrix

DOI10.1016/J.DISOPT.2008.12.002MaRDI QIDQ1015329zbMATH OpenOpenAlexFDO

Authors S. I. Veselov, A. J. Chirkov

Publication date 7 May 2009

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

integer solutioninteger vertex

Mathematics Subject Classification ID

Integer programming (90C10)

Abstract: This paper has been accepted for publication in Discrete Optimization.

Recommendations

• A strongly polynomial algorithm for bimodular integer linear programming
• The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
• On integer programming with bounded determinants
• Notes on \(\{a,b,c\}\)-modular matrices
• On the recognition of \(\{a,b,c\}\)-modular matrices

Cites work

• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• Polynomial algorithms in linear programming

Cited in

(33)

• On Proximity for k-Regular Mixed-Integer Linear Optimization
• The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
• Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
• Notes on \(\{a,b,c\}\)-modular matrices
• The integrality number of an integer program
• New Bounds for the Integer Carathéodory Rank
• On the Column Number and Forbidden Submatrices for \(\Delta\)-Modular Matrices
• The complexity of some graph problems with bounded minors of their constraint matrices
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Advances on strictly \(\varDelta \)-modular IPs
• FPT-algorithms for some problems related to integer programming
• A unimodular problem of integer programming
• Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• Distances between optimal solutions of mixed-integer programs
• On integer programming with bounded determinants
• The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
• On lattice width of lattice-free polyhedra and height of Hilbert bases
• On lattice point counting in \(\varDelta\)-modular polyhedra
• A note on non-degenerate integer programs with small sub-determinants
• The Integrality Number of an Integer Program
• Congruency-constrained TU problems beyond the bimodular case
• Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
• FPT-algorithm for computing the width of a simplex given by a convex hull
• Improving the Cook et al. proximity bound given integral valued constraints
• On the recognition of \(\{a,b,c\}\)-modular matrices
• Enumerating integer points in polytopes with bounded subdeterminants
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• On the number of distinct rows of a matrix with bounded subdeterminants
• Complexity of optimizing over the integers
• 2-modular matrices
• The computational complexity of three graph problems for instances with bounded minors of constraint matrices

This page was built for publication: Integer program with bimodular matrix

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