Efficient group cuts for integer programs |
| |
Authors: | David E Bell |
| |
Institution: | (1) Harvard University Boston, MA, USA |
| |
Abstract: | 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. |
| |
Keywords: | Integer Programming Column Generation Group Theoretic Method Lagrangian Group Cuts Generalized Linear Programming |
本文献已被 SpringerLink 等数据库收录! |