Name
Abstract | ||
|---|---|---|
This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one colum n in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequ alities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the su bproblem 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. Forty years have passed since Ralph Gomory suggested a series of primal and dual algorithms for tackling linear integer programs. Dual type algorithms start solving a linear programming rel axation of the problem, typically with the dual simplex method. In the course of the algorithm one maintains as an invariant both primal and dual feasibility of the solutio n of the relaxation. While the optimal solution to the relaxation is not integral, one cont inues adding cutting planes to the problem formulation and reoptimizes. Within this framework, Gomory developed a method of systematically generating valid inequalities d irectly from a given simplex tableau, see (Gom58, Gom60). A disadvantage of a dual-type method is, however, that intermediate stopping does not yield a primal feasible inte gral solution. In contrast to dual methods, primal type algorithms always preserve integrality of the solution to the relaxation. Primal type algorithms may b e further distinguished ac- cording to whether the algorithm preserves either dual feas ibility or primal feasibility. Note that it is impossible to preserve integrality and both d ual and primal feasibility. The only representative of the first family of primal type met hods is Gomory's so- called "primal all integer algorithm" that appeared in (Gom 63). We are not aware of interesting computational experiments with this method, however. A second alternative to design a primal type algorithm is to p reserve integrality of the solution to the relaxation and simultaneously primal fe asibility. In order to achieve |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/s10107-003-0384-8 | Math. Program. |
Keywords | Field | DocType |
Computational Result,Integer Program,Linear Integer Program,Diophantine Inequality,Augmentation Algorithm | Integer,Discrete mathematics,Mathematical optimization,Algebraic method,Algorithm,Integer programming,Linear programming,Diophantine equation,Mathematics,Cornacchia's algorithm,Diophantine approximation | Journal |
Volume | Issue | ISSN |
96 | 2 | 0025-5610 |
Citations | PageRank | References |
14 | 0.98 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Utz-Uwe Haus | 1 | 226 | 18.47 |
| Matthias KöPpe | 2 | 191 | 20.95 |
| Robert Weismantel | 3 | 964 | 90.05 |