Optimization Online


Integer packing sets form a well-quasi-ordering

Alberto Del Pia (delpia***at***wisc.edu)
Dion Gijswijt (d.c.gijswijt***at***tudelft.nl)
Jeff Linderoth (linderoth***at***wisc.edu)
Haoran Zhu (hzhu94***at***wisc.edu)

Abstract: An integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y ≤ x is in the set as well. Integer packing sets appear naturally in Integer Optimization. In fact, the set of integer points in any packing polyhedron is an integer packing set. The main result of this paper is that integer packing sets, ordered by inclusion, form a well-quasi-ordering. This result allows us to answer a question recently posed by Bodur et al. In fact, we prove that the k-aggregation closure of any packing polyhedron is again a packing polyhedron. The generality of our main result allows us to provide a generalization to non-polyhedral sets: The k-aggregation closure of any downset of R^n_+ is a packing polyhedron.

Keywords: Well-quasi-ordering; k-aggregation closure; Polyhedrality; Packing polyhedra.

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 01/31/2020
Entry Accepted: 02/01/2020
Entry Last Modified: 05/30/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society