Affordable Access

Publisher Website

Primal Integer Programming

Authors
Publisher
Elsevier B.V.
Identifiers
DOI: 10.1016/s0927-0507(05)12005-2
Disciplines
  • Computer Science
  • Design
  • Mathematics

Abstract

Abstract Primal Integer Programming is concerned with the design of algorithms for linear integer programs that move from a feasible solution to a better feasible solution until optimality is proved. We refer to such a method as a primal (or augmentation) algorithm. We study such algorithms and address the questions related to making such an approach theoretically efficient and practically work. In particular, we address the question of computational complexity with respect to the number of augmentation steps. From a theoretical point of view, the study of the augmentation problem leads to the theory of irreducible lattice points and integral generating sets. We present the algorithmic approaches to attack general integer programs the first approach is based on the use of cutting planes, the Integral Basis Method is a second approach. For specific combinatorial optimization problems such a min-cost flow, matching, matroid intersection and the problem of minimizing a submodular function, we discuss the basics of the related combinatorial algorithms.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Accelerated primal-dual cutting plane algorithm fo...

on Computers & Operations Researc... Jan 01, 1983

Solution approaches for highly primal- and dual-de...

on Computers & Operations Researc... Jan 01, 1985
More articles like this..