Article ID: | iaor20013621 |
Country: | Germany |
Volume: | 89 |
Issue: | 1 |
Start Page Number: | 35 |
End Page Number: | 53 |
Publication Date: | Jan 2000 |
Journal: | Mathematical Programming |
Authors: | Savelsbergh M.W.P., Nemhauser George L., Atamtrk A. |
Keywords: | Vertex packing |
We study a generalization of the vertex packing problem having both binary and bounded continuous variables, called the mixed vertex packing problem (MVPP). The well-known vertex packing model arises as a subproblem or relaxation of many 0–1 integer problems, whereas the mixed vertex packing model arises as a natural counterpart of vertex packing in the context of mixed 0–1 integer programming. We describe strong valid inequalities for the convex hull of solutions to the MVPP and separation algorithms for these inequalities. We give a summary of computational results with a branch-and-cut algorithm for solving the MVPP and using it to solve general mixed-integer problems.