Abstract: This paper introduces an exact algorithm for solving integer programs, neither using cutting planes nor enumeration techniques. It is a primal augmentation algorithm that relies on iteratively substituting one column by columns that correspond to irreducible solutions of certain linear diophantine inequalities. We demonstrate the algorithm's potential by testing it on some instances of the MIPLIB with up to 6000 variables.
Preprint (Postscript), BibTeX entry, Springer LINK with PDF.
This is the conference version of the paper On the Way to Perfection: Primal Operations for Stable Sets in Graphs.
Abstract: This paper addresses the question of decomposing an infinite family of rational polyhedra in an integer fashion. It is shown that there is a finite subset of this family that generates the entire family. Moreover, an integer analogue of Carathéodory's theorem carries over to this general setting. The integer decomposition of a family of polyhedra has different applications in integer and mixed integer programming.
Preprint (Postscript), Springer LINK with PDF
The dissertation is also available as a PDF file from Shaker Verlag.
Abstract: This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method.
Preprint (Postscript), Springer LINK with PDF
Abstract: This paper introduces an algorithm for solving mixed integer programs. The core of the method is an iterative technique for changing the representation of the original mixed integer optimization problem.
Preprint (revised) (Postscript). Springer LINK with PDF
Abstract: In this paper some operations are described that transform every graph into a perfect graph by replacing nodes with sets of new nodes. The transformation is done in such a way that every stable set in the perfect graph corresponds to a stable set in the original graph. These operations yield a purely combinatorial augmentation procedure for finding a maximum weighted stable set in a graph. Starting with a stable set in a given graph one defines a simplex type tableau whose associated basic feasible solution is the incidence vector of the stable set. In an iterative fashion, non-basic columns that would lead to pivoting into non-integral basic feasible solutions, are replaced by new columns that one can read off from special graph structures such as odd holes, odd antiholes, and various generalizations. Eventually, either a pivot leading to an integral basic feasible solution is performed, or the optimality of the current solution is proved.
Preprint (Postscript)
Abstract: We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory's group relaxations. We present an algorithm based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation.
Preprint (revised) (Postscript), Elsevier ScienceDirect with text and PDF
Abstract: This paper deals with algorithmic issues related to the design of an augmentation algorithm for general and 0/1-integer programs. We recall the approach of integer pivoting and introduce the family of Gomory-Young augmentation vectors that can be derived from a simplex tableau. Furthermore, a technique of combining Gomory-Young vectors and combinatorial augmentation vectors in one augmentation scheme is presented. Two computational experiments demonstrate the potential of pivoting in an integer fashion.
Technical Report (Postscript)