Matrices with lexicographically-ordered rows

被引：0
作者：
Gustavo Angulo
机构：
[1] Pontificia Universidad Católica de Chile,Department of Industrial and Systems Engineering
来源：
Optimization Letters | 2019年 / 13卷
关键词：
Lexicographic order; Extended formulation; Dynamic programming;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：235 / 248
页数：13
相关论文
共 23 条
  • [1] Angulo G(2014)Forbidden vertices Math. Oper. Res. 40 350-360
  • [2] Ahmed S(2018)Lexicographical polytopes Discret. Appl. Math. 240 3-7
  • [3] Dey SS(2015)A short convex-hull proof for the all-different system with the inclusion property Oper. Res. Lett. 43 69-73
  • [4] Kaibel V(2016)Convex hulls of superincreasing knapsacks and lexicographic orderings Discret. Appl. Math. 201 150-163
  • [5] Barbato M(2008)Packing and partitioning orbitopes Math. Program. 114 1-36
  • [6] Grappe R(2002)All-different polytopes J. Comb. Optim. 6 335-352
  • [7] Lacroix M(2007)On a binary-encoded ILP coloring formulation INFORMS J. Comput. 19 406-415
  • [8] Pira C(2012)A polyhedral approach to the all different system Math. Program. 132 209-260
  • [9] Di Summa M(1990)Polyhedral characterization of discrete dynamic programming Oper. Res. 38 127-138
  • [10] Gupte A(2001)Representations of the all\_different predicate of constraint satisfaction in integer programming INFORMS J. Comput. 13 96-103
123