Strengthening convex relaxations of 0/1-sets using Boolean formulas. (English) Zbl 1478.90060
Summary: In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set \(S\) of feasible integer points, such as popular linear programming or semi-definite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets \(S\) that arise in combinatorial optimization. We propose a new efficient method that interpolates between these two approaches. Our procedure strengthens any convex set containing a set \(S \subseteq \{0,1\}^n\) by exploiting certain additional information about \(S\). Namely, the required extra information will be in the form of a Boolean formula \(\phi\) defining the target set \(S\). The new relaxation is obtained by “feeding” the convex set into the formula \(\phi \). We analyze various aspects regarding the strength of our procedure. As one application, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems.
MSC:
| 90C10 | Integer programming |
| 90C25 | Convex programming |
| 68Q06 | Networks and circuits as models of computation; circuit complexity |
References:
| [1] | Averkov, G., Kaibel, V., Weltge, S.: Maximum semidefinite and linear extension complexity of families of polytopes. Math. Program. 167(2), Ser. A, pp. 381-394 (2018). MR 3755737 · Zbl 1384.52008 |
| [2] | Balas, E.: Disjunctive programming. Ann. Discrete Math. 5, 3-51 (1979). Discrete optimization (Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications, Banff, Alta., 1977), II. MR 558566 · Zbl 0409.90061 |
| [3] | Bazzi, A., Fiorini, S., Huang, S., Svensson, O.: Small extended formulation for knapsack cover inequalities from monotone circuits. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms 2017, (2017) · Zbl 1423.90205 |
| [4] | Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor 2-e. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1123-1142 (2015) · Zbl 1435.68110 |
| [5] | Beimel, A.; Weinreb, E., Monotone circuits for monotone weighted threshold functions, Inf. Process. Lett., 97, 1, 12-18 (2006) · Zbl 1184.68227 · doi:10.1016/j.ipl.2005.09.008 |
| [6] | Benchetrit, Y., Fiorini, S., Huynh, T., Weltge, S.: Characterizing Polytopes Contained in the \(0/1\)-Cube with Bounded Chvátal-Gomory Rank. Mathematics of Operations Research (2018) · Zbl 1451.90115 |
| [7] | Bienstock, D.; Zuckerberg, M., Subset algebra lift operators for 0-1 integer programming, SIAM J. Optim., 15, 1, 63-95 (2004) · Zbl 1077.90041 · doi:10.1137/S1052623402420346 |
| [8] | Bienstock, D.; Zuckerberg, M., Approximate fixed-rank closures of covering problems, Math. Program. Ser. A, 105, 9-27 (2006) · Zbl 1085.90031 · doi:10.1007/s10107-005-0598-z |
| [9] | Bienstock, D., Zuckerberg, M.: Simpler derivation of bounded pitch inequalities for set covering, and minimum knapsack sets, arXiv:1806.07435 (2018) |
| [10] | Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305-337 (1973) · Zbl 0253.05131 · doi:10.1016/0012-365X(73)90167-2 |
| [11] | Cornuéjols, G., Lee, D.: On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 300-311. Springer (2016) · Zbl 1419.90092 |
| [12] | Eisenbrand, F., On the membership problem for the elementary closure of a polyhedron, Combinatorica, 19, 2, 297-300 (1999) · Zbl 0947.90071 · doi:10.1007/s004930050057 |
| [13] | Fiorini, S., Groß, M., Könemann, J., Sanità, L.: Approximating weighted tree augmentation via Chvátal-Gomory cuts. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 817-831. SIAM, Philadelphia, PA (2018). MR 3775841 · Zbl 1403.68347 |
| [14] | Fiorini, S., Massar, S., Pokutta, S., Tiwary, H. R., de Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2), 1-23 (2015) · Zbl 1333.90107 |
| [15] | Göös, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. In: Proc. FOCS 2016, (2016) · Zbl 1416.90053 |
| [16] | Hoory, S., Magen, A., Pitassi, T.: Monotone circuits for the majority function. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, pp. 410-425 (2006) · Zbl 1155.68572 |
| [17] | Hrubeš, Pavel, On the nonnegative rank of distance matrices, Inf. Process. Lett., 112, 11, 457-461 (2012) · Zbl 1243.15003 · doi:10.1016/j.ipl.2012.02.009 |
| [18] | Karchmer, M.; Wigderson, A., Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Discrete Math., 3, 255-265 (1990) · Zbl 0695.94021 · doi:10.1137/0403021 |
| [19] | Klabjan, D.; Nemhauser, GL; Tovey, C., The complexity of cover inequality separation, Oper. Res. Lett., 23, 35-40 (1998) · Zbl 0957.90094 · doi:10.1016/S0167-6377(98)00025-X |
| [20] | Lasserre, J. B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. Integer programming and combinatorial optimization (Utrecht, 2001), Lecture Notes in Comput. Sci., vol. 2081, pp. 293-303. Springer, Berlin (2001). MR 2041934 · Zbl 1010.90515 |
| [21] | Lovász, L.; Schrijver, A., Cones of matrices and set-functions and \(0-1\) optimization, SIAM J. Optim., 1, 2, 166-190 (1991) · Zbl 0754.90039 · doi:10.1137/0801013 |
| [22] | Mastrolilli, M: High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts. In: Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pp. 405-416 (2017) · Zbl 1418.90167 |
| [23] | Raz, R.; Wigderson, Avi, Monotone circuits for matching require linear depth, J. Assoc. Comput. Mach., 39, 3, 736-744 (1992) · Zbl 0799.68077 · doi:10.1145/146637.146684 |
| [24] | Rothvoß, T., Some 0/1 polytopes need exponential size extended formulations, Math. Program. A, 142, 255-268 (2013) · Zbl 1282.90245 · doi:10.1007/s10107-012-0574-3 |
| [25] | Rothvoß, T.: The matching polytope has exponential extension complexity. J. ACM 64, no. 6, Art. 41, 19 (2017). MR 3713797 · Zbl 1426.90255 |
| [26] | Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency. Vol. A, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003, Paths, flows, matchings, Chapters 1-38. MR 1956924 (2004b:90004a) · Zbl 1041.90001 |
| [27] | Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 3, 411-430 (1990) · Zbl 0712.90050 · doi:10.1137/0403036 |
| [28] | Singh, M., Talwar, K.: Improving integrality gaps via Chvátal-Gomory rounding. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pp. 366-379 (2010) · Zbl 1306.90138 |
| [29] | Wegener, I., Relating monotone formula size and monotone depth of Boolean functions, Inf. Process. Lett., 16, 1, 41-42 (1983) · Zbl 0504.94035 · doi:10.1016/0020-0190(83)90011-X |
| [30] | Weltge, S.: Sizes of linear descriptions in combinatorial optimization. dissertation, Otto-von-Guericke-Universität Magdeburg, (2016) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
