Shapes and recession cones in mixed-integer convex representability
Springer Science and Business Media LLC - Trang 1-14 - 2023
Tóm tắt
Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear representable (MILP-R) sets. First, we provide an example of an MICP-R set which is the countably infinite union of convex sets with countably infinitely many different recession cones. This is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that share the same recession cone. Second, we provide an example of an MICP-R set which is the countably infinite union of polytopes all of which have different shapes (no pair is combinatorially equivalent, which implies they are not affine transformations of each other). Again, this is in sharp contrast with MILP-R sets which are (countable) unions of polyhedra that are all translations of a finite subset of themselves.
Tài liệu tham khảo
Ceria, S., Ja, Soares: Convex programming for disjunctive convex optimization. Math. Program. 86(3), 595–614 (1999)
Del Pia, A., Poskin, J.: On the mixed binary representability of ellipsoidal regions. In: Louveaux, Q., Skutella, M. (eds) Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, Proceedings, Springer, Lecture Notes in Computer Science, vol 9682, pp 214–225 (2016)
Del Pia, A., Poskin, J.: Ellipsoidal mixed-integer representability. Math. Program. 172(1), 351–369 (2018)
Del Pia, A., Poskin, J.: Characterizations of mixed binary convex quadratic representable sets. Math. Program. 177(1), 371–394 (2019)
Glineur, F.: Computational experiments with a linear approximation of second order cone optimization. Image Technical Report 0001, Service de Mathématique et de Recherche Opérationnelle, Faculté Polytechnique de Mons, Mons, Belgium (2000)
Hiriart-Urruty, J.B., Lemaréchal, C.: Fundamentals of Convex Analysis. Springer Verlag, Heidelberg (2001)
Jeroslow, R.G.: Representability in mixed integer programming, I: characterization results. Discret. Appl. Math. 17(3), 223–243 (1987)
Jeroslow, R.G., Lowe, J.K.: Modeling with integer variables. Mathe. Program. Stud. 22, 167–184 (1984)
Klain, D.: On the equality conditions of the Brunn-Minkowski theorem. Proc. Am. Math. Soc. 139(10), 3719–3726 (2011)
Lubin, M., Zadik, I., Vielma, J.P.: Mixed-integer convex representability. In: Eisenbrand, F., Könemann, J. (eds) Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, Proceedings, Springer, Lecture Notes in Computer Science, vol 10328, pp. 392–404 (2017)
Lubin, M., Vielma, J.P., Zadik, I.: Mixed-integer convex representability. Math. Oper. Res. 47(1), 720–749 (2022)
Schneider, R.: Convex Bodies: The Brunn-Minkowski Theory. Encyclopedia of Mathematics and its Applications, 2nd edn. Cambridge University Press, Cambridge (2013)
Stubbs, R.A., Mehrotra, S.: A branch-and-cut method for 0–1 mixed convex programming. Math. Program. 86(3), 515–532 (1999)
Ziegler, G.M.: Lectures on Polytopes, vol. 152. Springer Science & Business Media, Berlin (2012)