Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Matrices with lexicographically-ordered rows

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Angulo, G., Ahmed, S., Dey, S.S., Kaibel, V.: Forbidden vertices. Math. Oper. Res. 40(2), 350–360 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  2. Barbato, M., Grappe, R., Lacroix, M., Pira, C.: Lexicographical polytopes. Discret. Appl. Math. 240, 3–7 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  3. Di Summa, M.: A short convex-hull proof for the all-different system with the inclusion property. Oper. Res. Lett. 43(1), 69–73 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  4. Gupte, A.: Convex hulls of superincreasing knapsacks and lexicographic orderings. Discret. Appl. Math. 201, 150–163 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  5. Hojny, C., Pfetsch, M.E.: Polytopes associated with symmetry handling. Math. Program. (2018). https://doi.org/10.1007/s10107-018-1239-7

  6. Kaibel, V., Loos, A.: Branched Polyhedral Systems, Integer Programming and Combinatorial Optimization, pp. 177–190. Springer, Berlin (2010)

    Book  MATH  Google Scholar 

  7. Kaibel, V., Pfetsch, M.E.: Packing and partitioning orbitopes. Math. Program. 114(1), 1–36 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Lee, J.: All-different polytopes. J. Comb. Optim. 6(3), 335–352 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  9. Lee, J., Margot, F.: On a binary-encoded ILP coloring formulation. INFORMS J. Comput. 19(3), 406–415 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  10. Loos, A.: Describing Orbitopes by Linear Inequalities and Projection Based Tools, Ph.D. thesis (2011)

  11. Magos, D., Mourtos, I., Appa, G.: A polyhedral approach to the all different system. Math. Program. 132(1–2), 209–260 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  12. Martin, R.K., Rardin, R.L., Campbell, B.A.: Polyhedral characterization of discrete dynamic programming. Oper. Res. 38(1), 127–138 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  13. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)

    MATH  Google Scholar 

  14. Williams, H.P., Yan, H.: Representations of the all\_different predicate of constraint satisfaction in integer programming. INFORMS J. Comput. 13(2), 96–103 (2001)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author thanks an anonymous referee whose comments and suggestions greatly helped to improve the paper.

Author information

Authors and Affiliations

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

    Gustavo Angulo

Authors
  1. Gustavo Angulo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gustavo Angulo.

Additional information

Funded by Conicyt Fondecyt 11150689.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Angulo, G. Matrices with lexicographically-ordered rows. Optim Lett 13, 235–248 (2019). https://doi.org/10.1007/s11590-018-1369-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-018-1369-0

Keywords

Search

Navigation