Matrices with lexicographically-ordered rows

The lexicographic order can be used to force a collection of decision vectors to be all different, i.e., to take on different values in some coordinates. We consider the set of fixed-size matrices with bounded integer entries and rows in lexicographic order. We present a dynamic program to optimize a linear function over this set, from which we obtain a compact extended formulation for its convex hull.


Department of Industrial and Systems Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile



View Matrices with lexicographically-ordered rows