Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Strong formulations for conic quadratic optimization with indicator variables

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

Abstract

We study the convex hull of the mixed-integer set given by a conic quadratic inequality and indicator variables. Conic quadratic terms are often used to encode uncertainties, while the indicator variables are used to model fixed costs or enforce sparsity in the solutions. We provide the convex hull description of the set under consideration when the continuous variables are unbounded. We propose valid nonlinear inequalities for the bounded case, and show that they describe the convex hull for the two-variable case. All the proposed inequalities are described in the original space of variables, but extended SOCP-representable formulations are also given. We present computational experiments demonstrating the strength of the proposed formulations.

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

Similar content being viewed by others

Notes

  1. If \(\varOmega =\nicefrac {-a(N)+b(N)}{\sqrt{\sum _{i\in N}c_i^2}}\), then the objective values corresponding to the solutions \(x=y=0\) and \(x=y=1\) have objective values of 0; in most cases, such solutions are optimal, resulting in initial/root gaps of infinity. Thus, we multiply \(\varOmega \) by 0.999 to ensure optimal solutions with objective value different from 0.

  2. We also tested the cuts with data generated according to [7]. However in such cases the initial gaps are very small—less than 5%—and the simple linear cuts (17) result in close to 100% root gap improvement, thus the stronger inequalities yield a marginal improvement at best. In contrast, the instances generated according to [6] are more challenging, with initial gaps up to 80%.

References

  1. Aktürk, M.S., Atamtürk, A., Gürel, S.: A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett. 37, 187–191 (2009)

    MathSciNet  MATH  Google Scholar 

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

  3. Atamtürk, A., Gómez, A.: Maximizing a class of utility functions over the vertices of a polytope. Oper. Res. 65, 433–445 (2017)

    MathSciNet  MATH  Google Scholar 

  4. Atamtürk, A., Gómez, A.: Strong formulations for quadratic optimization with M-matrices and indicator variables. Math. Program. 170, 141–176 (2018)

    MathSciNet  MATH  Google Scholar 

  5. Atamtürk, A., Gómez, A.: Rank-one convexification for sparse regression. arXiv preprint arXiv:1901.10334 (2019)

  6. Atamtürk, A., Gómez, A.: Submodularity in conic quadratic mixed 0–1 optimization. Oper. Res. 68(2), 609–630 (2020)

    MathSciNet  MATH  Google Scholar 

  7. Atamtürk, A., Jeon, H.: Lifted polymatroid inequalities for mean-risk optimization with indicator variables. J. Global Optim. 73, 677–699 (2019)

    MathSciNet  MATH  Google Scholar 

  8. Atamtürk, A., Narayanan, V.: Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36, 618–622 (2008)

    MathSciNet  MATH  Google Scholar 

  9. Atamtürk, A., Narayanan, V.: Conic mixed-integer rounding cuts. Math. Program. 122, 1–20 (2010)

    MathSciNet  MATH  Google Scholar 

  10. Atamtürk, A., Narayanan, V.: Lifting for conic mixed-integer programming. Math. Program. 126, 351–363 (2011)

    MathSciNet  MATH  Google Scholar 

  11. Atamtürk, A., Berenguer, G., Shen, Z.J.: A conic integer programming approach to stochastic joint location-inventory problems. Oper. Res. 60, 366–381 (2012)

    MathSciNet  MATH  Google Scholar 

  12. Atamtürk, A., Gómez, A., Han, S.: Sparse and smooth signal estimation: Convexification of l0 formulations. arXiv preprint arXiv:1811.02655 BCOL Research Report 18.05, IEOR, UC Berkeley (2018)

  13. Belotti, P., Góez, J.C., Pólik, I., Ralphs, T.K., Terlaky, T.: On families of quadratic surfaces having fixed intersections with two hyperplanes. Discrete Appl. Math. 161, 2778–2793 (2013)

    MathSciNet  MATH  Google Scholar 

  14. Belotti, P., Góez, J.C., Pólik, I., Ralphs, T.K., Terlaky, T.: A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization. In: Numerical Analysis and Optimization, pp. 1–35. Springer (2015)

  15. Belotti, P., Góez, J.C., Pólik, I., Ralphs, T.K., Terlaky, T.: Disjunctive conic cuts for mixed integer second order cone optimization. GERAD-HEC Montréal (2015)

  16. Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23, 769–805 (1998)

    MathSciNet  MATH  Google Scholar 

  17. Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25, 1–13 (1999)

    MathSciNet  MATH  Google Scholar 

  18. Bienstock, D., Michalka, A.: Cutting-planes for optimization of convex functions over nonconvex sets. SIAM J. Optim. 24, 643–677 (2014)

    MathSciNet  MATH  Google Scholar 

  19. Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, Berlin (2011)

    MATH  Google Scholar 

  20. Bonami, P.: Lift-and-project cuts for mixed integer convex programs. In: International Conference on Integer Programming and Combinatorial Optimization, pp 52–64. Springer (2011)

  21. Bonami, P., Lodi, A., Tramontani, A., Wiese, S.: On mathematical programming with indicator constraints. Math. Program. 151, 191–223 (2015)

    MathSciNet  MATH  Google Scholar 

  22. Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Math. Program. 86, 595–614 (1999)

    MathSciNet  MATH  Google Scholar 

  23. Çezik, M.T., Iyengar, G.: Cuts for mixed 0–1 conic programming. Math. Program. 104, 179–202 (2005)

    MathSciNet  MATH  Google Scholar 

  24. Dong, H., Linderoth, J.: On valid inequalities for quadratic programming with continuous variables and binary indicators. In: Goemans, M., Correa, J. (eds.) Proc. IPCO 2013, pp 169–180. Springer, Berlin (2013)

  25. Dong, H., Chen, K., Linderoth, J.: Regularization vs. relaxation: a conic optimization perspective of statistical variable selection. arXiv preprint arXiv:1510.06083 (2015)

  26. Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Guy, R., Hanani, H., Sauer, N., Schönenheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69–87. Gordon and Breach, New York (1970)

    Google Scholar 

  27. El Ghaoui, L., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18, 1035–1064 (1997)

    MathSciNet  MATH  Google Scholar 

  28. El Ghaoui, L., Oks, M., Oustry, F.: Worst-case value-at-risk and robust portfolio optimization: a conic programming approach. Oper. Res. 51, 543–556 (2003)

    MathSciNet  MATH  Google Scholar 

  29. Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0–1 mixed integer programs. Math. Program. 106, 225–236 (2006)

    MathSciNet  MATH  Google Scholar 

  30. Frangioni, A., Gentile, C.: SDP diagonalizations and perspective cuts for a class of nonseparable MIQP. Oper. Res. Lett. 35, 181–185 (2007)

    MathSciNet  MATH  Google Scholar 

  31. Frangioni, A., Gentile, C.: A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes. Oper. Res. Lett. 37, 206–210 (2009)

    MathSciNet  MATH  Google Scholar 

  32. Frangioni, A., Furini, F., Gentile, C.: Approximated perspective relaxations: a project and lift approach. Comput. Optim. Appl. 63, 705–735 (2016)

    MathSciNet  MATH  Google Scholar 

  33. Frangioni, A., Furini, F., Gentile, C.: Improving the approximated projected perspective reformulation by dual information. Oper. Res. Lett. 45, 519–524 (2017)

    MathSciNet  MATH  Google Scholar 

  34. Frangioni, A., Gentile, C., Hungerford, J.: Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs. Math. Oper. Res. 45(1), 15–33 (2019)

    MathSciNet  MATH  Google Scholar 

  35. Gómez, A., Prokopyev, O.: A mixed-integer fractional optimization approach to best subset selection. http://www.optimization-online.org/DB_HTML/2018/08/6791.html (2018). Accessed 15 Apr 2020

  36. Günlük, O., Linderoth, J.: Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program. 124, 183–205 (2010)

    MathSciNet  MATH  Google Scholar 

  37. Han, G., Shaoning, Andrés, Atamtürk, A.: 2x2-convexifications for convex quadratic optimization with indicator variables. http://www.optimization-online.org/DB_HTML/2020/04/7746.html (2020). Accessed 15 Apr 2020

  38. Hijazi, H., Bonami, P., Cornuéjols, G., Ouorou, A.: Mixed-integer nonlinear programs featuring “on/off” constraints. Comput. Optim. Appl. 52, 537–558 (2012)

    MathSciNet  MATH  Google Scholar 

  39. Jeon, H., Linderoth, J., Miller, A.: Quadratic cone cutting surfaces for quadratic programs with on–off constraints. Discrete Optim. 24, 32–50 (2017)

    MathSciNet  MATH  Google Scholar 

  40. Kılınç, M., Linderoth, J., Luedtke, J.: Effective separation of disjunctive cuts for convex mixed integer nonlinear programs. Optimization Online (2010)

  41. Kılınç-Karzan, F.: On minimal valid inequalities for mixed integer conic programs. Math. Oper. Res. 41(2), 477–510 (2015)

    MathSciNet  MATH  Google Scholar 

  42. Kılınç-Karzan, F., Yıldız, S.: Two-term disjunctions on the second-order cone. Math. Program. 154, 463–491 (2015)

    MathSciNet  MATH  Google Scholar 

  43. Lovász, L.: Submodular functions and convexity. In: Bachem, A., Korte, B., Grötschel, M. (eds.) Mathematical Programming the State of the Art: Bonn 1982, pp. 235–257. Springer, Berlin (1983)

    Google Scholar 

  44. Mahajan, A., Leyffer, S., Linderoth, J., Luedtke, J., Munson, T.: Minotaur: a mixed-integer nonlinear optimization toolkit. ANL/MCS-P8010-0817, Argonne National Lab (2017)

  45. Mazumder, R., Radchenko, P., Dedieu, A.: Subset selection with shrinkage: sparse linear modeling when the SNR is low. arXiv preprint arXiv:1708.03288 (2017)

  46. Miyashiro, R., Takano, Y.: Mixed integer second-order cone programming formulations for variable selection in linear regression. Eur. J. Oper. Res. 247, 721–731 (2015)

    MathSciNet  MATH  Google Scholar 

  47. Modaresi, S., Kılınç, M.R., Vielma, J.P.: Split cuts and extended formulations for mixed integer conic quadratic programming. Oper. Res. Lett. 43(1), 10–15 (2015)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  49. Morán, R.D.A., Dey, S.S., Vielma, J.P.: A strong dual for conic mixed-integer programs. SIAM J. Optim. 22, 1136–1150 (2012)

    MathSciNet  MATH  Google Scholar 

  50. Ozsen, L., Coullard, C.R., Daskin, M.S.: Capacitated warehouse location model with risk pooling. Nav. Res. Logist. (NRL) 55, 295–312 (2008)

    MathSciNet  MATH  Google Scholar 

  51. Richard, J.P.P., Tawarmalani, M.: Lifting inequalities: a framework for generating strong cuts for nonlinear programs. Math. Program. 121, 61–104 (2010)

    MathSciNet  MATH  Google Scholar 

  52. Santana, A., Dey, S.S.: Some cut-generating functions for second-order conic sets. Discrete Optim. 24, 51–65 (2017)

    MathSciNet  MATH  Google Scholar 

  53. Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0–1 mixed convex programming. Math. Program. 86, 515–532 (1999)

    MathSciNet  MATH  Google Scholar 

  54. Wu, B., Sun, X., Li, D., Zheng, X.: Quadratic convex reformulations for semicontinuous quadratic programming. SIAM J. Optim. 27, 1531–1553 (2017)

    MathSciNet  MATH  Google Scholar 

  55. Xie, W., Deng, X.: Scalable algorithms for sparse ridge regression. arXiv preprint arXiv:1806.03756 (2020)

  56. Yıldız, S., Cornuéjols, G.: Disjunctive cuts for cross-sections of the second-order cone. Oper. Res. Lett. 43(4), 432–437 (2015)

    MathSciNet  MATH  Google Scholar 

  57. Zhang, Y., Jiang, R., Shen, S.: Ambiguous chance-constrained bin packing under mean-covariance information. arXiv preprint arXiv:1610.00035 (2016)

  58. Zheng, X., Sun, X., Li, D.: Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach. INFORMS J. Comput. 26, 690–703 (2014)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This paper is based upon work supported by the National Science Foundation under Grant No. 1818700.

Author information

Authors and Affiliations

  1. Daniel J. Epstein Department of Industrial and Systems Engineering, Viterbi School of Engineering, University of Southern California, Los Angeles, CA, 90089, USA

    Andrés Gómez

Authors
  1. Andrés Gómez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrés Gómez.

Additional information

Publisher's Note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gómez, A. Strong formulations for conic quadratic optimization with indicator variables. Math. Program. 188, 193–226 (2021). https://doi.org/10.1007/s10107-020-01508-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-020-01508-y

Keywords

Mathematics Subject Classification

Search

Navigation