A primal dual integer programming algorithm
type: Item
instance of: scholarly article
title: A primal dual integer programming algorithm
zbMATH Open document ID: 0794.90040
DOI: 10.1016/0166-218X(93)90014-F
author: V. Pereyra
published in: Discrete Applied Mathematics
publication date: 1994-01-04T00:00:00Z
review text: The authors intend to apply the results of theoretical investigations in practice and propose an algorithm for solving linear integer problems (LIP). The method uses a Chvatal function to verify the optimality of a feasible solution. As the authors note themselves, two steps of the algorithm include in fact the solution of two LIPs that could be as difficult as the original problem. To solve these subproblems cutting planes and Chvatal functions are applied. A problem of finding a maximum weight matching in a graph is solved as an example of the proposed algorithm.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 474689
zbMATH Keywords: linear integer problems
zbMATH Keywords: Chvatal function
zbMATH Keywords: maximum weight matching
MaRDI profile type: Publication
cites work: The value function of a mixed integer program: I
cites work: The value function of an integer program
cites work: Computational Complexity of Some Problems in Parametric Discrete Programming. I
cites work: Q4147876
cites work: Edmonds polytopes and a hierarchy of combinatorial problems
cites work: Hermite Normal Form Computation Using Modulo Determinant Arithmetic
cites work: Paths, Trees, and Flowers
cites work: Q4149476
cites work: Outline of an algorithm for integer solutions to linear programs
cites work: Q5645210
cites work: Cutting-plane theory: Algebraic methods
cites work: An Introduction to the Theory of Cutting-Planes
cites work: Q5183269
cites work: On the Group Problem and a Subadditive Approach to Integer Programming
cites work: Odd Minimum Cut-Sets and b-Matchings
cites work: On Cutting Planes
cites work: Q3818127
cites work: Integer programming duality: Price functions and sensitivity analysis
cites work: The b-hull of an integer program
description: scientific article; zbMATH DE number 474689