Constraint Pairing In Integer Programming
Peter L. Hammer, Manfred W. Padberg, Uri N. Peled · INFOR Information Systems and Operational Research · 1975
Single linear constraints can be used in a straightforward way for deriving bounds on the variables of discrete optimization problems. More powerful conclusions can be obtained from the examination of all the surrogate constraints associated to pairs of constraints. The paper shows that for problems involving n integer variables, the examination of at most n + 2 surrogates (constructively) associated to any pair of constraints in the problem produces all the conclusions derivable from any linear combination of the given constraint pair. The bounds obtained are shown to be the same as those obtained by maximizing or minimizing the individual variables under the pair of constraints. If m denotes the number of constraints in the problem, then 0(m2n2) elementary operations will be performed for testing all constraint-pairs of the problem in order to improve the bounds on the variables and/or to derive binary relations among them.
Cited by 20 works. doi:10.1080/03155986.1975.11731594