Affordable Access

Publisher Website

Primal Integer Programming

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


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.


Seen <100 times