Pontificia Universidad Católica de Chile Pontificia Universidad Católica de Chile
Angulo G. (2019)

Matrices with lexicographically-ordered rows

Revista : Optimization Letters
Tipo de publicación : ISI Ir a publicación


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.