A Simplified Primal (All-Integer) Integer Programming Algorithm

doi:10.1287/opre.16.4.750

A Simplified Primal (All-Integer) Integer Programming Algorithm

1968-08-01

0

PRE

AI

DOI：10.1287/opre.16.4.750

原文链接

原文求助

摘要

En 中文

This paper describes a primal, all-integer algorithm for solving a bounded and solvable pure integer programming problem. The method is a primal analogue to the Gomory All-Integer Algorithm, and is a variant of the simplex method in sense that the Gomory algorithm is a variant of the dual method. The simplified primal algorithm makes these major amendments to the simplex method: (i) a special row, indexed by L, is adjoined to the tableau and is periodically revised by a well-defined procedure; (ii) in most cycles of the algorithm the pivot column, AJ, is selected so that aLJ > 0 and (1/aLJ)AJ is lexicographically smaller than (1/aLj)Aj for all nonbasic columns Aj that have aLj > 0; (iii) in all cycles of the algorithm a Gomory cut is adjoined after selection of the pivot column, and the cut is selected so that it will have a unit coefficient in the pivot column and it will qualify (in order to be used) as the pivot row. With comparatively minor restrictions on the selection of the row used to generate the Gomory cut the simplified primal algorithm is shown to be finite.

A Simplified Primal (All-Integer) Integer Programming Algorithm

摘要

AI总结

期刊

机构

引用论文