An Extension of the Bound Escalation Method for Integer Programming: A Pseudo Primal-Dual Algorithm of the Gomory Allinteger Variety

摘要

An extension of the bound escalation method is presented that enables the customary dual feasibility requirement in the integer programming tableau to be systematically violated and then restored. The bound escalation method itself is composed of two stages. In the first stage a structure called the bounding form is created by applying a series of nonsingular integer transformations to the problem matrix. The second stage then operates on the bounding form to obtain lower bounds for a subset of the current problem variables and thereby to advance the problem toward solution.