Decomposing Matrices into Blocks

DOI10.1137/S1052623497318682MaRDI QIDQ4229489zbMATH OpenOpenAlexFDO

Authors Ralf Borndörfer, Alexander Martin, Carlos E. Ferreira

Publication date 22 February 1999

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s1052623497318682

zbMATH Keywords

integer programmingcutting planespolyhedral combinatoricsmatrix decompositionblock structure of a sparse matrix

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Linear programming (90C05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10) Mixed integer programming (90C11)

Recommendations

• scientific article; zbMATH DE number 709605
• A decomposition procedure for one class of block programming problems
• Permuting Sparse Rectangular Matrices into Block-Diagonal Form
• Décomposition en matrices graphiques de matrices en $\lbrace 0, 1, -1\rbrace $ : application à la résolution de programmes linéaires entiers

Cited in

(31)

• Block rearranging elements within matrix columns to minimize the variability of the row sums
• A-priori upper bounds for the set covering problem
• Block SOS decomposition
• High-multiplicity \(N\)-fold IP via configuration LP
• New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem
• Exact algorithms for the vertex separator problem in graphs
• scientific article; zbMATH DE number 709605 (Why is no real title available?)
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• A branch-and-price algorithm for capacitated hypergraph vertex separation
• Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
• Improving strong branching by domain propagation
• Automatic Dantzig-Wolfe reformulation of mixed integer programs
• Structure Detection in Mixed-Integer Programs
• A model-based approach and analysis for multi-period networks
• Political districting to minimize cut edges
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
• scientific article; zbMATH DE number 3912097 (Why is no real title available?)
• Revisiting dynamic programming for finding optimal subtrees in trees
• Disconnecting graphs by removing vertices: a polyhedral approach
• Branching rules revisited
• A decomposition-based approach for the multiperiod multiproduct distribution planning problem
• Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
• Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• On integer and bilevel formulations for the \(k\)-vertex cut problem
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• Décomposition en matrices graphiques de matrices en $\lbrace 0, 1, -1\rbrace $ : application à la résolution de programmes linéaires entiers
• Packing and partitioning orbitopes
• A decomposition heuristic for mixed-integer supply chain problems
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

Describes a project that uses

Uses Software

• MIPLIB
• CPLEX
• Netlib

This page was built for publication: Decomposing Matrices into Blocks

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