Abstract.
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received: June 1998 / Accepted: February 2000¶Published online September 20, 2000
Rights and permissions
About this article
Cite this article
Atamtürk, A., Nemhauser, G. & Savelsbergh, M. The mixed vertex packing problem. Math. Program. 89, 35–53 (2000). https://doi.org/10.1007/s101070000154.
Issue Date:
DOI: https://doi.org/10.1007/s101070000154.