Extended formulations via decision diagrams. (English) Zbl 07900429
Wu, Weili (ed.) et al., Computing and combinatorics. 29th international conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 14423, 17-28 (2024).
Summary: We propose a general algorithm of constructing an extended formulation for any given set of linear constraints with integer coefficients. Our algorithm consists of two phases: first construct a decision diagram \((V, E)\) that somehow represents a given \(m \times n\) constraint matrix, and then build an equivalent set of \(|E|\) linear constraints over \(n+|V|\) variables. That is, the size of the resultant extended formulation depends not explicitly on the number \(m\) of the original constraints, but on its decision diagram representation. Therefore, we may significantly reduce the computation time and space for optimization problems with integer constraint matrices by solving them under the extended formulations, especially when we obtain concise decision diagram representations for the matrices. We demonstrate the effectiveness of our extended formulations for mixed integer programming and the 1-norm regularized soft margin optimization tasks over synthetic and real datasets.
Eligible for best student paper.
For the entire collection see [Zbl 1543.68019].
Eligible for best student paper.
For the entire collection see [Zbl 1543.68019].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
References:
| [1] | Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1997), pp. 360-369 (1997) · Zbl 1321.68549 |
| [2] | Bergman, D., Cire, A.A., van Hoeve, W.J., Hooker, J.: Decision Diagrams for Optimization. Springer Cham (2016). doi:10.1007/978-3-319-42849-9 · Zbl 06653190 |
| [3] | Bergman, D.; van Hoeve, W-J; Hooker, JN; Achterberg, T.; Beck, JC, Manipulating MDD relaxations for combinatorial optimization, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 20-35, 2011, Heidelberg: Springer, Heidelberg · Zbl 1302.90166 · doi:10.1007/978-3-642-21311-3_5 |
| [4] | Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35(8), 677-691 (1986) · Zbl 0593.94022 |
| [5] | Castro, M.P., Cire, A.A., Beck, J.C.: An MDD-based Lagrangian approach to the multicommodity pickup-and-delivery TSP. INFORMS J. Comput. 32(2), 263-278 (2019). doi:10.1287/IJOC.2018.0881 · Zbl 07290845 |
| [6] | Chang, CC; Lin, CJ, LIBSVM: a library for support vector machines, ACM Trans. Intell. Syst. Technol., 2, 27, 1-27, 2011 · doi:10.1145/1961189.1961199 |
| [7] | Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8(1), 1-48 (2010) · Zbl 1219.90193 |
| [8] | Duchi, J.; Hazan, E.; Singer, Y., Adaptive subgradient methods for online learning and stochastic optimization, J. Mach. Learn. Res., 12, 7, 2121-2159, 2011 · Zbl 1280.68164 |
| [9] | Fiorini, S., Huynh, T., Weltge, S.: Strengthening convex relaxations of 0/1-sets using Boolean formulas. Math. Program. 190(1), 467-482 (2021) · Zbl 1478.90060 |
| [10] | Freund, Y.; Schapire, RE, A decision-theoretic generalization of on-line learning and an application to boosting, J. Comput. Syst. Sci., 55, 1, 119-139, 1997 · Zbl 0880.68103 · doi:10.1006/jcss.1997.1504 |
| [11] | Fujita, T.; Hatano, K.; Takimoto, E., Boosting over non-deterministic ZDDs, Theoret. Comput. Sci., 806, 81-89, 2020 · Zbl 1436.68301 · doi:10.1016/j.tcs.2018.11.027 |
| [12] | Goto, K.; Bannai, H.; Inenaga, S.; Takeda, M., Fast q-gram mining on SLP compressed strings, J. Discrete Algorithms, 18, 89-99, 2013 · Zbl 1267.68112 · doi:10.1016/j.jda.2012.07.006 |
| [13] | Hermelin, D., Landau, G.M., Landau, S., Weimann, O.: A unified algorithm for accelerating edit-distance computation via text-compression. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), LIPIcs, vol. 3, pp. 529-540 (2009) · Zbl 1236.68308 |
| [14] | Inoue, T., Distribution loss minimization with guaranteed error bound, IEEE Trans. Smart Grid, 5, 1, 102-111, 2014 · doi:10.1109/TSG.2013.2288976 |
| [15] | Jiang, T.; Ravikumar, B., Minimal NFA problems are hard, SIAM J. Comput., 22, 6, 1117-1141, 1993 · Zbl 0799.68079 · doi:10.1137/0222067 |
| [16] | Knuth, D.E.: The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Part 1. Addison-Wesley Professional, Upper Saddle River (2011) · Zbl 1354.68001 |
| [17] | Kurokawa, Y., Mitsuboshi, R., Hamasaki, H., Hatano, K., Takimoto, E., Rahmanian, H.: Extended formulations via decision diagrams (2022) |
| [18] | Lifshits, Y.; Ma, B.; Zhang, K., Processing compressed texts: a tractability border, Combinatorial Pattern Matching, 228-240, 2007, Heidelberg: Springer, Heidelberg · Zbl 1138.68419 · doi:10.1007/978-3-540-73437-6_24 |
| [19] | Lohrey, M., Algorithmics on SLP-compressed strings: a survey, Groups - Complexity - Cryptology, 4, 2, 241-299, 2012 · Zbl 1285.68088 · doi:10.1515/gcc-2012-0016 |
| [20] | Minato, S.I.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: Proceedings of the 30th International Design Automation Conference (DAC 1993), pp. 272-277 (1993) |
| [21] | Minato, S.I.: Power of enumeration - recent topics on BDD/ZDD-based techniques for discrete structure manipulation. IEICE Trans. Inf. Syst. E100.D(8), 1556-1562 (2017) |
| [22] | Minato, S.I., Uno, T.: Frequentness-transition queries for distinctive pattern mining from time-segmented databases. In: Proceedings of the 2010 SIAM International Conference on Data Mining (SDM), pp. 339-349 (2010) |
| [23] | Minato, S.; Uno, T.; Arimura, H.; Washio, T.; Suzuki, E.; Ting, KM; Inokuchi, A., LCM over ZBDDs: fast generation of very large-scale frequent itemsets using a compact graph-based representation, Advances in Knowledge Discovery and Data Mining, 234-246, 2008, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-68125-0_22 |
| [24] | Morrison, D.R., Sewell, E.C., Jacobson, S.H.: Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams. INFORMS J. Comput. 28(1), 67-82 (2016). doi:10.1287/IJOC.2015.0667 · Zbl 1338.90431 |
| [25] | Nishino, M., Yasuda, N., Minato, S.I., Nagata, M.: Accelerating graph adjacency matrix multiplications with adjacency forest. In: Proceedings of the 2014 SIAM International Conference on Data Mining (SDM 2014), pp. 1073-1081 (2014) |
| [26] | Raina, R., Madhavan, A., Ng, A.Y.: Large-scale deep unsupervised learning using graphics processors. In: Proceedings of the 26th Annual International Conference on Machine Learning (ICML 2009), pp. 873-880 (2009) |
| [27] | Rätsch, G.; Warmuth, MK, Efficient margin maximizing with boosting, J. Mach. Learn. Res., 6, 2131-2152, 2005 · Zbl 1222.68285 |
| [28] | Rytter, W.; Díaz, J.; Karhumäki, J.; Lepistö, A.; Sannella, D., Grammar compression, LZ-encodings, and string algorithms with implicit input, Automata, Languages and Programming, 15-27, 2004, Heidelberg: Springer, Heidelberg · Zbl 1099.68028 · doi:10.1007/978-3-540-27836-8_5 |
| [29] | Tabei, Y., Saigo, H., Yamanishi, Y., Puglisi, S.J.: Scalable partial least squares regression on grammar-compressed data matrices. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016), pp. 1875-1884 (2016) |
| [30] | Toda, T.; Fürnkranz, J.; Hüllermeier, E.; Higuchi, T., Fast compression of large-scale hypergraphs for solving combinatorial problems, Discovery Science, 281-293, 2013, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-40897-7_19 |
| [31] | Toda, T.: ZCOMP: Fast Compression of Hypergraphs into ZDDs (2015). https://www.sd.is.uec.ac.jp/toda/code/zcomp.html |
| [32] | Yannakakis, M., Expressing combinatorial optimization problems by Linear Programs, J. Comput. Syst. Sci., 43, 3, 441-466, 1991 · Zbl 0748.90074 · doi:10.1016/0022-0000(91)90024-Y |
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.
