Synopses & Reviews
Synopsis
Excerpt from Relaxation Methods for Pure and Mixed Integer Programming Problems
Computational experience with a group theoretic integer programming (ip) algorithm has been unusually promising; see reference 6. A major irawback, however, of this method in the past has been the size of the finite abelian groups encountered during the computation of certain 1? Problems. In this paper, we show how the difficulty can be overcome by the application of some rather simple number theoretic procedures. Although these procedures cannot be guaranteed to reduce the size of the induced groups, computational experience to date has shown them to be efficacious in practically all cases. The central idea is that a given IP problem can be usefully transformed by dividing all the coefficients of an inequality by a rational divisor greater than 1, and then taking integer parts. Such a transformation of the problem, called a relaxation, has the property that all feasible solutions to the original IP problem are feasible in the transformed or relaxed problem. The idea for this particular relaxation method in IP is originally due to Wolsey The term relaxation is also used by Geoffrion in 3] to describe mathematical programming methods conceived in the same spirit as the ones here.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.