New inequalities for finite and infinite group problems from approximate lifting |
| |
| Authors: | Lisa A. Miller Yanjun Li Jean‐Philippe P. Richard |
| |
| Affiliation: | 1. Department of Mechanical Engineering, University of Minnesota, Minneapolis, Minnesota;2. Krannert School of Management, Purdue University, West Lafayette, Indiana;3. School of Industrial Engineering, Purdue University, West Lafayette, Indiana |
| |
| Abstract: | In this paper, we derive new families of facet‐defining inequalities for the finite group problem and extreme inequalities for the infinite group problem using approximate lifting. The new valid inequalities for the finite group problem include two‐ and three‐slope facet‐defining inequalities as well as the first family of four‐slope facet‐defining inequalities. The new valid inequalities for the infinite group problem include families of two‐ and three‐slope extreme inequalities. These new inequalities not only illustrate the diversity of strong inequalities for the finite and infinite group problems, but also provide a large variety of new cutting planes for solving integer and mixed‐integer programming problems. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008 |
| |
| Keywords: | integer programming approximate lifting group problem polyhedral theory |
|
|
