EFFICIENT GROUP CUTS FOR INTEGER PROGRAMS

Gomory's group relaxation for integer programs has been refined by column generation methods and dual ascent algorithms to identify a set of candidate solutions which are feasible in the relaxation but not necessarily so in the original integer program. Attempts at avoiding branch and bound procedures at this point have focussed on providing extra group constraints which eliminate all or most of the candidate solutions so that further ascent can take place. It will be shown that a single constraint usually of order 2 or 3, can eliminate all of the candidate solutions. © 1979 North-Holland Publishing Company.