{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:18:25Z","timestamp":1740122305216,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T00:00:00Z","timestamp":1685577600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100007655","name":"\u010cesk\u00e9 Vysok\u00e9 U\u010den\u00ed Technick\u00e9 v Praze","doi-asserted-by":"publisher","award":["SGS19\/170\/OHK3\/3T\/13","SGS22\/061\/OHK3\/1T\/13"],"award-info":[{"award-number":["SGS19\/170\/OHK3\/3T\/13","SGS22\/061\/OHK3\/1T\/13"]}],"id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["19-09967S","19-09967S"],"award-info":[{"award-number":["19-09967S","19-09967S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001823","name":"Ministerstvo \u0160kolstv\u00ed, Ml\u00e1de\u017ee a T\u011blov\u00fdchovy","doi-asserted-by":"publisher","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765","CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765","CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s10601-023-09349-0","type":"journal-article","created":{"date-parts":[[2023,7,25]],"date-time":"2023-07-25T10:01:51Z","timestamp":1690279311000},"page":"244-276","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Activity propagation in systems of linear inequalities and its relation to block-coordinate descent in linear programs"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1944-6569","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Dlask","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6161-7157","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Werner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,25]]},"reference":[{"issue":"3","key":"9349_CR1","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1023\/A:1017501703105","volume":"109","author":"P Tseng","year":"2001","unstructured":"Tseng, P. (2001). Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization. Journal Optim Theory Appl., 109(3), 475\u2013494.","journal-title":"Journal Optim Theory Appl."},{"key":"9349_CR2","doi-asserted-by":"crossref","unstructured":"Werner T., Pr\u016f\u0161a D. (2019) Relative Interior Rule in Block-Coordinate Minimization. arXiv:1910.09488 [math.OC]","DOI":"10.1109\/CVPR42600.2020.00758"},{"key":"9349_CR3","doi-asserted-by":"crossref","unstructured":"Werner T., Pr\u016f\u0161a D., Dlask T. (2020) Relative Interior Rule in Block-Coordinate Descent. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition. 7559\u20137567.","DOI":"10.1109\/CVPR42600.2020.00758"},{"issue":"1\u20132","key":"9349_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000001","volume":"1","author":"MJ Wainwright","year":"2008","unstructured":"Wainwright, M. J., & Jordan, M. I. (2008). Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends in Machine Learning, 1(1\u20132), 1\u2013305.","journal-title":"Foundations and Trends in Machine Learning"},{"issue":"2","key":"9349_CR5","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s11263-015-0809-x","volume":"115","author":"JH Kappes","year":"2015","unstructured":"Kappes, J. H., Andres, B., Hamprecht, F. A., Schn\u00f6rr, C., Nowozin, S., Batra, D., et al. (2015). A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems. International Journal of Computer Vision, 115(2), 155\u2013184.","journal-title":"International Journal of Computer Vision"},{"issue":"3\u20134","key":"9349_CR6","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1561\/0600000084","volume":"11","author":"B Savchynskyy","year":"2019","unstructured":"Savchynskyy, B. (2019). Discrete Graphical Models - An Optimization Perspective. Foundations and Trends in Computer Graphics and Vision, 11(3\u20134), 160\u2013429.","journal-title":"Foundations and Trends in Computer Graphics and Vision"},{"key":"9349_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33974-5","volume-title":"The Complexity of Valued Constraint Satisfaction Problems","author":"S \u017divn\u00fd","year":"2012","unstructured":"\u017divn\u00fd, S. (2012). The Complexity of Valued Constraint Satisfaction Problems. Cognitive Technologies: Springer."},{"key":"9349_CR8","volume-title":"A diffusion algorithm for decreasing energy of max-sum labeling problem","author":"V Kovalevsky","year":"1975","unstructured":"Kovalevsky, V., & Koval, V. (1975). A diffusion algorithm for decreasing energy of max-sum labeling problem. Kiev, USSR: Glushkov Institute of Cybernetics. Unpublished."},{"issue":"7","key":"9349_CR9","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/TPAMI.2007.1036","volume":"29","author":"T Werner","year":"2007","unstructured":"Werner, T. (2007). A Linear Programming Approach to Max-sum Problem: A Review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(7), 1165\u20131179.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"10","key":"9349_CR10","doi-asserted-by":"publisher","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","volume":"28","author":"V Kolmogorov","year":"2006","unstructured":"Kolmogorov, V. (2006). Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10), 1568\u20131583.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"9349_CR11","unstructured":"Globerson, A., Jaakkola, T.S. (2008) Fixing max-product: Convergent message passing algorithms for MAPLP-relaxations. In: Advances in Neural Information Processing Systems. 553\u2013560."},{"key":"9349_CR12","doi-asserted-by":"crossref","unstructured":"Tourani, S., Shekhovtsov, A., Rother, C., Savchynskyy, B. (2018) MPLP++: Fast, parallel dual block-coordinate ascent for dense graphical models. In: Proceedings of the European Conference on Computer Vision. 251\u2013267.","DOI":"10.1007\/978-3-030-01225-0_16"},{"issue":"8","key":"9349_CR13","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1109\/TPAMI.2009.134","volume":"32","author":"T Werner","year":"2010","unstructured":"Werner, T. (2010). Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction. IEEE Trans Pattern Analysis and Machine Intelligence., 32(8), 1474\u20131488.","journal-title":"IEEE Trans Pattern Analysis and Machine Intelligence."},{"issue":"7\u20138","key":"9349_CR14","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.artint.2010.02.001","volume":"174","author":"MC Cooper","year":"2010","unstructured":"Cooper, M. C., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M., & Werner, T. (2010). Soft arc consistency revisited. Artificial Intelligence, 174(7\u20138), 449\u2013478.","journal-title":"Artificial Intelligence"},{"key":"9349_CR15","first-page":"149","volume":"8","author":"VK Koval","year":"1976","unstructured":"Koval, V. K., & Schlesinger, M. I. (1976). Dvumernoe programmirovanie v zadachakh analiza izobrazheniy (Two-dimensional Programming in Image Analysis Problems). Automatics and Telemechanics., 8, 149\u2013168. In Russian.","journal-title":"Automatics and Telemechanics."},{"key":"9349_CR16","doi-asserted-by":"crossref","unstructured":"Dlask, T., Werner, T. (2020) Bounding linear programs by constraint propagation: application to Max-SAT. In: International Conference on Principles and Practice of Constraint Programming. Springer. p. 177\u2013193.","DOI":"10.1007\/978-3-030-58475-7_11"},{"key":"9349_CR17","unstructured":"Papadimitriou, C.H., Steiglitz, K. (1998) Combinatorial optimization: algorithms and complexity. Courier Corporation."},{"key":"9349_CR18","doi-asserted-by":"crossref","unstructured":"Dlask, T. (2020) Unit Propagation by Means of Coordinate-Wise Minimization. In: International Conference on Machine Learning, Optimization, and Data Science. Springer. 688\u2013699.","DOI":"10.1007\/978-3-030-64583-0_60"},{"key":"9349_CR19","doi-asserted-by":"crossref","unstructured":"Apt, K.R. (1997) From chaotic iteration to constraint propagation. In: International Colloquium on Automata, Languages, and Programming. Springer. 36\u201355.","DOI":"10.1007\/3-540-63165-8_163"},{"key":"9349_CR20","doi-asserted-by":"crossref","unstructured":"Apt K.R. The Rough Guide to Constraint Propagation. In: Conf. on Principles and Practice of Constraint Programming. Springer; 1999. p. 1\u201323.","DOI":"10.1007\/978-3-540-48085-3_1"},{"key":"9349_CR21","doi-asserted-by":"crossref","unstructured":"Dlask, T., Werner, T. (2020) On relation between constraint propagation and block-coordinate descent in linear programs. In: International Conference on Principles and Practice of Constraint Programming. Springer. 194\u2013210.","DOI":"10.1007\/978-3-030-58475-7_12"},{"key":"9349_CR22","doi-asserted-by":"crossref","unstructured":"Dlask, T. (2022) Block-Coordinate Descent and Local Consistencies in Linear Programming [Ph.D. thesis, available online https:\/\/dspace.cvut.cz\/handle\/10467\/102874?locale-attribute=en]. Czech Technical University in Prague, Faculty of Electrical Engineering.","DOI":"10.1007\/s10601-023-09350-7"},{"key":"9349_CR23","volume-title":"Lattices and Ordered Algebraic Structures","author":"TS Blyth","year":"2005","unstructured":"Blyth, T. S. (2005). Lattices and Ordered Algebraic Structures. London: Universitext. Springer."},{"key":"9349_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809088","volume-title":"Introduction to lattices and order","author":"BA Davey","year":"2002","unstructured":"Davey, B. A., & Priestley, H. A. (2002). Introduction to lattices and order. Cambridge University Press."},{"key":"9349_CR25","unstructured":"Nation J.B.: Notes on lattice theory. https:\/\/math.hawaii.edu\/~jb\/math618\/Nation-LatticeTheory.pdf."},{"key":"9349_CR26","doi-asserted-by":"crossref","unstructured":"Bessiere, C. ( 2006) Constraint Propagation. In: Handbook of Constraint Programming. Elsevier.","DOI":"10.1016\/S1574-6526(06)80007-6"},{"key":"9349_CR27","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A. (1998). Theory of linear and integer programming. John Wiley & Sons."},{"key":"9349_CR28","unstructured":"Matou\u0161ek J., G\u00e4rtner B. Understanding and using linear programming. Springer-Verlag; 2006."},{"key":"9349_CR29","unstructured":"Schrijver, A. (2004) Combinatorial optimization: polyhedra and efficiency. Springer Science & Business Media."},{"key":"9349_CR30","unstructured":"Freund, R.M., Roundy, R., Todd, M.J. (1985) Identifying the set of always-active constraints in a system of linear inequalities by a single linear program. Massachusetts Institute of Technology, Alfred P. Sloan School of Management. 1674-85."},{"key":"9349_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge University Press."},{"key":"9349_CR32","volume-title":"Fundamentals of Convex Analysis","author":"C Lemar\u00e9chal","year":"2004","unstructured":"Lemar\u00e9chal, C., & Hiriart-Urruty, J. B. (2004). Fundamentals of Convex Analysis. Springer Grundlehren Text Editions: Springer Verlag, New York."},{"key":"9349_CR33","doi-asserted-by":"crossref","unstructured":"Goldman, A.J., Tucker, A.W. (1956) In: Theory of Linear Programming. Princeton University Press. 53\u201397.","DOI":"10.1515\/9781400881987-005"},{"key":"9349_CR34","doi-asserted-by":"crossref","unstructured":"Jansen, B., Roos, C., Terlaky, T., Vial, J.P. (1993) Interior-point methodology for linear programming: duality, sensitivity analysis and computational aspects. In: Optimization in Planning and Operation of Electric Power Systems. Springer. 57\u2013123.","DOI":"10.1007\/978-3-662-12646-2_3"},{"issue":"4","key":"9349_CR35","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0167-6377(94)90075-2","volume":"15","author":"HJ Greenberg","year":"1994","unstructured":"Greenberg, H. J. (1994). The use of the optimal partition in a linear programming solution for postoptimal analysis. Operations Research Letters, 15(4), 179\u2013185.","journal-title":"Operations Research Letters"},{"key":"9349_CR36","doi-asserted-by":"crossref","unstructured":"Zhang, S. (1994) On the strictly complementary slackness relation in linear programming. In: Advances in Optimization and Approximation. Springer. 347\u2013361.","DOI":"10.1007\/978-1-4613-3629-7_19"},{"issue":"1","key":"9349_CR37","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF01758841","volume":"8","author":"I Adler","year":"1992","unstructured":"Adler, I., & Monteiro, R. D. (1992). A geometric view of parametric linear programming. Algorithmica, 8(1), 161\u2013176.","journal-title":"Algorithmica"},{"issue":"1","key":"9349_CR38","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/BF01585180","volume":"62","author":"S Mehrotra","year":"1993","unstructured":"Mehrotra, S., & Ye, Y. (1993). Finding an interior point in the optimal face of linear programs. Mathematical Programming, 62(1), 497\u2013515.","journal-title":"Mathematical Programming"},{"issue":"10","key":"9349_CR39","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1287\/mnsc.29.10.1209","volume":"29","author":"J Telgen","year":"1983","unstructured":"Telgen, J. (1983). Identifying redundant constraints and implicit equalities in systems of linear constraints. Management Science, 29(10), 1209\u20131222.","journal-title":"Management Science"},{"issue":"1","key":"9349_CR40","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF02284624","volume":"17","author":"HJ Greenberg","year":"1996","unstructured":"Greenberg, H. J. (1996). Consistency, redundancy, and implied equalities in linear systems. Annals of Mathematics and Artificial Intelligence, 17(1), 37\u201383.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"7","key":"9349_CR41","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1007\/s10472-021-09731-9","volume":"90","author":"T Dlask","year":"2022","unstructured":"Dlask, T., & Werner, T. (2022). Classes of linear programs solvable by coordinate-wise minimization. Annals of Mathematics and Artificial Intelligence, 90(7), 777\u2013807.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"9349_CR42","doi-asserted-by":"crossref","unstructured":"Pisinger, D., Ropke, S. (2010) Large neighborhood search. In: Handbook of metaheuristics. Springer.","DOI":"10.1007\/978-1-4419-1665-5_13"},{"key":"9349_CR43","doi-asserted-by":"crossref","unstructured":"Hansen, P., Mladenovi\u0107, N., Brimberg, J., P\u00e9rez, J.A.M. (2010) Variable neighborhood search. In: Handbook of metaheuristics. Springer.","DOI":"10.1007\/978-1-4419-1665-5_3"},{"key":"9349_CR44","unstructured":"Werner, T. (2017) On Coordinate Minimization of Piecewise-Affine Functions. Department of Cybernetics, Faculty of Electrical Engineering, Czech Technical University in Prague. CTU-CMP-2017-05."},{"key":"9349_CR45","unstructured":"Dlask, T. (2018) Minimizing Convex Piecewise-Affine Functions by Local Consistency Techniques. Master\u2019s Thesis."},{"key":"9349_CR46","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-030-53552-0_8","volume-title":"Learning and Intelligent Optimization","author":"T Dlask","year":"2020","unstructured":"Dlask, T., & Werner, T. (2020). A Class of Linear Programs Solvable by Coordinate-Wise Minimization. In I. S. Kotsireas & P. M. Pardalos (Eds.), Learning and Intelligent Optimization (pp. 52\u201367). Springer."},{"issue":"1","key":"9349_CR47","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10601-016-9251-0","volume":"22","author":"DA Cohen","year":"2017","unstructured":"Cohen, D. A., & Jeavons, P. G. (2017). The power of propagation: when GAC is enough. Constraints, 22(1), 3\u201323.","journal-title":"Constraints"},{"key":"9349_CR48","doi-asserted-by":"crossref","unstructured":"Cooper M.C., \u017divn\u00fd S. (2016) The power of arc consistency for CSPs defined by partially-ordered forbidden patterns. In: Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science; 652\u2013661.","DOI":"10.1145\/2933575.2933587"},{"key":"9349_CR49","volume-title":"Lectures on Polytopes","author":"GM Ziegler","year":"1994","unstructured":"Ziegler, G. M. (1994). Lectures on Polytopes. New York: Springer-Verlag."},{"key":"9349_CR50","unstructured":"Bachem, A., Gr\u00f6tschel, M. (1980) New aspects of polyhedral theory. Inst. f\u00fcr \u00d6konometrie und Operations Research."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09349-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-023-09349-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09349-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T02:09:44Z","timestamp":1691114984000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-023-09349-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9349"],"URL":"https:\/\/doi.org\/10.1007\/s10601-023-09349-0","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2023,6]]},"assertion":[{"value":"13 May 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}