A primal dual integer programming algorithm

DOI10.1016/0166-218X(93)90014-FMaRDI QIDQ1309813zbMATH OpenFDO

Authors V. Pereyra

Publication date 4 January 1994

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

Full work available at URL https://doi.org/10.1016/0166-218X(93)90014-F

zbMATH Keywords

Chvatal functionlinear integer problemsmaximum weight matching

Mathematics Subject Classification ID

Integer programming (90C10) Programming involving graphs or networks (90C35)

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.

Recommendations

• Primal integer programming
• scientific article; zbMATH DE number 4128658
• A primal-dual cutting-plane algorithm for all-integer programming
• scientific article; zbMATH DE number 1953187
• An algorithmic framework for the matching problem in some hypergraphs

Cites work

• An Introduction to the Theory of Cutting-Planes
• Computational Complexity of Some Problems in Parametric Discrete Programming. I
• Cutting-plane theory: Algebraic methods
• Edmonds polytopes and a hierarchy of combinatorial problems
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3578640 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 3431974 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• Integer programming duality: Price functions and sensitivity analysis
• Odd Minimum Cut-Sets and b-Matchings
• On Cutting Planes
• On the Group Problem and a Subadditive Approach to Integer Programming
• Outline of an algorithm for integer solutions to linear programs
• Paths, Trees, and Flowers
• The b-hull of an integer program
• The value function of a mixed integer program: I
• The value function of an integer program

Cited in

(9)

• Solution approaches for highly primal- and dual-degenerate all-integer programming problems
• The primal-dual method for approximation algorithms
• A Gilmore-Gomory construction of integer programming value functions
• Subadditive approaches in integer programming
• Two-stage integer programs with stochastic right-hand sides: A superadditive dual approach
• scientific article; zbMATH DE number 5371762 (Why is no real title available?)
• Scarf's Procedure for Integer Programming and a Dual Simplex Algorithm
• Primal integer programming
• The primal-dual algorithm as a constraint-set-manipulation device

This page was built for publication: A primal dual integer programming algorithm

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