[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A characterization of maximal homogeneous-quadratic-free sets

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

The intersection cut framework was introduced by Balas in 1971 as a method for generating cutting planes in integer optimization. In this framework, one uses a full-dimensional convex S-free set, where S is the feasible region of the integer program, to derive a cut separating S from a non-integral vertex of a linear relaxation of S. Among all S-free sets, it is the inclusion-wise maximal ones that yield the strongest cuts. Recently, this framework has been extended beyond the integer case in order to obtain cutting planes in non-linear settings. In this work, we consider the specific setting when S is defined by a homogeneous quadratic inequality. In this ‘quadratic-free’ setting, every function \(\Gamma : D^m \rightarrow D^n\), where \(D^k\) is the unit sphere in \(\mathbb {R}^k\), generates a representation of a quadratic-free set. While not every \(\Gamma \) generates a maximal quadratic free set, it is the case that every full-dimensional maximal quadratic free set is generated by some \(\Gamma \). Our main result shows that the corresponding quadratic-free set is full-dimensional and maximal if and only if \(\Gamma \) is non-expansive and satisfies a technical condition. This result yields a broader class of maximal S-free sets than previously known. Our result stems from a new characterization of maximal S-free sets (for general S beyond the quadratic setting) based on sequences that ‘expose’ inequalities defining the S-free set.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. As a side note, we remark that this condition is equivalent to saying that the image of \(\Gamma \) is strictly contained in a hemisphere.

  2. Note that Lemma 4.1 does not directly imply that \(\gamma (\varvec{\beta })\) can be assumed to have unit norm. Moreover, one could produce a (not necessarily maximal) Q-free set with \(\gamma \) that satisfies \(\Vert \gamma (\varvec{\beta })\Vert < 1\) for some \(\varvec{\beta }\).

  3. Using the language in [27], the constant sequence here is an exposing point.

  4. Note that we cannot assume \((\Gamma (\varvec{\beta }^{[i,t]}),\varvec{\beta }^{[i,t]})\in I\) because Lemma 5.3 does not hold if \(\left\{ (\Gamma (\varvec{\beta }),-\varvec{\beta })\,: \varvec{\beta } \in D^m\,\right\} \) is replaced by I, which is not closed. We will not require that these points be in I, though. Here, we are implicitly using two representations of \(C_{\Gamma }\), one obtained by intersecting inequalities whose coefficients belong to I and another obtained by intersecting inequalities whose coefficients belong to \(\left\{ (\Gamma (\varvec{\beta }),-\varvec{\beta })\,: \varvec{\beta } \in D^m\,\right\} \).

References

  1. Andersen, K., Jensen, A.: Intersection cuts for mixed integer conic quadratic sets. In: Integer Programming and Combinatorial Optimization, pp. 37–48. Springer, Berlin (2013)

  2. Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.: Cutting planes from two rows of the simplex tableau. In: Proceedings of Integer Programming and Combinatorial Optimization (IPCO), pp. 1–15 (2007)

  3. Averkov, G.: On maximal s-free sets and the Helly number for the family of s-convex sets. SIAM J. Discrete Math. 27(3), 1610–1624 (2013)

    Article  MathSciNet  Google Scholar 

  4. Averkov, G.: A proof of Lovász’s theorem on maximal lattice-free sets. Contributions to Algebra and Geometry (2013)

  5. Averkov, G., Basu, A., Paat, J.: Approximation of corner polyhedra with families of intersection cuts. SIAM J. Optim. 28(1), 904–929 (2018)

    Article  MathSciNet  Google Scholar 

  6. Baes, M., Oertel, T., Weismantel, R.: Duality for mixed-integer convex minimization. Math. Program. 158, 547–564 (2016)

    Article  MathSciNet  Google Scholar 

  7. Balas, E.: Intersection cuts - a new type of cutting planes for integer programming. Operations Research (1971)

  8. Basu, A., Conforti, M., Cornuéjols, G., Weismantel, R., Weltge, S.: Optimality certificates for convex minimization and Helly numbers. Oper. Res. Lett. 45(6), 671–674 (2017)

    Article  MathSciNet  Google Scholar 

  9. Basu, A., Conforti, M., Cornuéjols, G., Zambelli, G.: Maximal lattice-free convex sets in linear subspaces. Math. Oper. Res. 35(3), 704–720 (2010)

    Article  MathSciNet  Google Scholar 

  10. Basu, A., Conforti, M., Cornuéjols, G., Zambelli, G.: Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discrete Math. 24(1), 158–168 (2010)

    Article  MathSciNet  Google Scholar 

  11. Basu, A., Dey, S., Paat, J.: Nonunique lifting of integer variables in minimal inequalities. SIAM J. Discrete Math. 33, 755–783 (2019)

    Article  MathSciNet  Google Scholar 

  12. Basu, A., Martin, K., Ryan, C.T.: Projection: a unified approach to semi-infinite linear programs and duality in convex programming. Math. Oper. Res. 40(1), 146–170 (2015)

    Article  MathSciNet  Google Scholar 

  13. Bienstock, D., Chen, C., Muñoz, G.: Intersection cuts for polynomial optimization. In: Lodi, A., Nagarajan, V. (eds.) Integer Programming and Combinatorial Optimization, pp. 72–87. Springer, Cham (2019)

    Chapter  Google Scholar 

  14. Bienstock, D., Chen, C., Muñoz, G.: Outer-product-free sets for polynomial optimization and oracle-based cuts. Math. Program. 183, 105–148 (2020)

    Article  MathSciNet  Google Scholar 

  15. Chmiela, A., Muñoz, G., Serrano, F.: On the implementation and strengthening of intersection cuts for QCQPs. Math. Program. 1–38 (2022)

  16. Conforti, M., Cornuéjols, G., Daniilidis, A., Lemaréchal, C., Malick, J.: Cut-generating functions and S-free sets. Math. Oper. Res. 40, 276 (2014)

    Article  MathSciNet  Google Scholar 

  17. Conforti, M., Cornuéjols, G., Zambelli, G.: A geometric perspective on lifting. Oper. Res. 59(3), 569–577 (2011)

    Article  MathSciNet  Google Scholar 

  18. Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, Berlin (2014)

    Book  Google Scholar 

  19. Conforti, M., Summa, M.D.: Maximal s-free convex sets and the Helly number. SIAM J. Discrete Math. 30(4), 2206–2216 (2016)

    Article  MathSciNet  Google Scholar 

  20. Dey, S., Wolsey, L.: Two row mixed-integer cuts via lifting. Math. Program. 124, 143–174 (2010)

    Article  MathSciNet  Google Scholar 

  21. Goberna, M., López, M., Pastor, J.: Farkas-Minkowski systems in semi-infinite programming. Appl. Math. Optim. 7, 295–308 (1981)

    Article  MathSciNet  Google Scholar 

  22. Goberna, M.A., Lopez-Cerda, M.: Linear Semi-infinite Optimization. Wiley, Chichester (1998)

    Google Scholar 

  23. Lovász, L.: Geometry of numbers and integer programming. In: Iri, M., Tanabe, K. (eds.) Mathematical Programming: Recent Developments and Applications, pp. 177–201. Kluwer Academic Publishers, Boston (1989)

    Google Scholar 

  24. Modaresi, S., Kılınç, M., Vielma, J.: Intersection cuts for nonlinear integer programming convexification techniques for structured sets. Math. Program. 155, 575–611 (2016)

    Article  MathSciNet  Google Scholar 

  25. Muñoz, G., Paat, J., Serrano, F.: Towards a characterization of maximal quadratic-free sets. In: Del Pia, A., Kaibel, V. (eds.) Integer Programming and Combinatorial Optimization, pp. 334–347. Springer International Publishing, Cham (2023)

    Chapter  Google Scholar 

  26. Muñoz, G., Serrano, F.: Maximal quadratic-free sets. In: Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, pp. 307–321 (2020)

  27. Muñoz, G., Serrano, F.: Maximal quadratic-free sets. Math. Program. 192, 229–270 (2022)

    Article  MathSciNet  Google Scholar 

  28. Paat, J., Schlöter, M., Speakman, E.: Constructing lattice-free gradient polyhedra in dimension two. Math. Program. 192(1), 293–317 (2022)

    Article  MathSciNet  Google Scholar 

  29. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    Book  Google Scholar 

  30. Tuy, H.: Concave minimization under linear constraints with special structure. Dokl. Akad. Nauk SSSR 159, 32–35 (1964)

    MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to thank Roberto Cominetti for fruitful discussions; in particular, for discussions leading to Remark 1.3, for noticing the subtlety in Theorem 17.3 from [29] discussed in Remark 4.1, and for the example provided in the latter. The authors would also like to thank the anonymous reviewers for their insightful comments that greatly helped in improving the article.

Funding

J. Paat was supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant [RGPIN-2021-02475]. G. Muñoz was supported by the National Research and Development Agency of Chile (ANID) through the Fondecyt Grant 1231522 and PIA/PUENTE AFB230002.

Author information

Authors and Affiliations

  1. Industrial Engineering Department, Universidad de Chile, Santiago, Chile

    Gonzalo Muñoz

  2. Sauder School of Business, University of British Columbia, Vancouver, BC, Canada

    Joseph Paat

  3. COPT GmbH, Berlin, Germany

    Felipe Serrano

Authors
  1. Gonzalo Muñoz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joseph Paat
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Felipe Serrano
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joseph Paat.

Ethics declarations

Conflict of interest

The authors have no relevant financial or non-financial interests to disclose. The authors have no conflict of interest to declare that are relevant to the content of this article.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

An extended abstract of this article appeared at IPCO 2023 [25]. This full version contains many new results, including a resolution of a conjecture posed in the extended abstract.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Muñoz, G., Paat, J. & Serrano, F. A characterization of maximal homogeneous-quadratic-free sets. Math. Program. (2024). https://doi.org/10.1007/s10107-024-02092-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10107-024-02092-1

Keywords

Mathematics Subject Classification

Search

Navigation