{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:49:50Z","timestamp":1759063790647,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T00:00:00Z","timestamp":1667001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005017","name":"Bayerisches Staatsministerium f\u00fcr Wirtschaft, Infrastruktur, Verkehr und Technologie","doi-asserted-by":"publisher","award":["ADA-Center"],"award-info":[{"award-number":["ADA-Center"]}],"id":[{"id":"10.13039\/501100005017","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["CRC TRR 154","GRK 2297 MathCoRe"],"award-info":[{"award-number":["CRC TRR 154","GRK 2297 MathCoRe"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For the problem to find an <jats:italic>m<\/jats:italic>-clique in an <jats:italic>m<\/jats:italic>-partite graph, staircase compatibility has recently been introduced as a polynomial-time solvable special case. It is a property of a graph together with an <jats:italic>m<\/jats:italic>-partition of the vertex set and total orders on each subset of the partition. In optimization problems involving <jats:italic>m<\/jats:italic>-cliques in <jats:italic>m<\/jats:italic>-partite graphs as a subproblem, it allows for totally unimodular linear programming formulations, which have shown to efficiently solve problems from different applications. In this work, we address questions concerning the recognizability of this property in the case where the <jats:italic>m<\/jats:italic>-partition of the graph is given, but suitable total orders are to be determined. While finding these total orders is NP-hard in general, we give several conditions under which it can be done in polynomial time. For bipartite graphs, we present a polynomial-time algorithm to recognize staircase compatibility and show that staircase total orders are unique up to a small set of reordering operations. On <jats:italic>m<\/jats:italic>-partite graphs, where the recognition problem is NP-complete in the general case, we identify a polynomially solvable subcase and also provide a corresponding algorithm to compute the total orders. Finally, we evaluate the performance of our ordering algorithm for <jats:italic>m<\/jats:italic>-partite graphs on a set of artificial instances as well as real-world instances from a railway timetabling application. It turns out that applying the ordering algorithm to the real-world instances and subsequently solving the problem via the aforementioned totally unimodular reformulations indeed outperforms a generic formulation which does not exploit staircase compatibility.<\/jats:p>","DOI":"10.1007\/s10957-022-02091-2","type":"journal-article","created":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T12:02:51Z","timestamp":1667044971000},"page":"449-479","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Recognizing Staircase Compatibility"],"prefix":"10.1007","volume":"195","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8636-4478","authenticated-orcid":false,"given":"Andreas","family":"B\u00e4rmann","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0784-6696","authenticated-orcid":false,"given":"Patrick","family":"Gemander","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7602-3653","authenticated-orcid":false,"given":"Alexander","family":"Martin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7838-445X","authenticated-orcid":false,"given":"Maximilian","family":"Merkert","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,29]]},"reference":[{"key":"2091_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2019.104782","volume":"113","author":"JAS Araujo","year":"2020","unstructured":"Araujo, J.A.S., Santos, H.G., Gendron, B., Jena, S.D., Brito, S.S., Souza, D.S.: Strong bounds for resource constrained project scheduling: preprocessing and cutting planes. Comput Oper Res 113, 104782 (2020)","journal-title":"Comput Oper Res"},{"key":"2091_CR2","doi-asserted-by":"crossref","unstructured":"Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: Handbook of Combinatorial Optimization: Supplement Volume A, Chap. The Maximum Clique Problem, pp. 1\u201374. Springer, Berlin (1999)","DOI":"10.1007\/978-1-4757-3023-4_1"},{"key":"2091_CR3","unstructured":"Bornd\u00f6rfer, R.: Aspects of set packing, partitioning, and covering. Ph.D. thesis, TU Berlin (1998)"},{"key":"2091_CR4","unstructured":"Brito, S.S., Santos, H.G.: Preprocessing and cutting planes with conflict graphs. arXiv:1909.07780 (2019)"},{"key":"2091_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.disopt.2018.04.001","volume":"29","author":"A B\u00e4rmann","year":"2018","unstructured":"B\u00e4rmann, A., Gellermann, T., Merkert, M., Schneider, O.: Staircase compatibility and its applications in scheduling and piecewise linearization. Discrete Optim. 29, 111\u2013132 (2018)","journal-title":"Discrete Optim."},{"key":"2091_CR6","volume-title":"German Success Stories in Industrial Mathematics","author":"A B\u00e4rmann","year":"2021","unstructured":"B\u00e4rmann, A., Gemander, P., Martin, A., Merkert, M., N\u00f6th, F.: German Success Stories in Industrial Mathematics. Chap. Energy-Efficient Timetabling in a German Underground System. Springer, Berlin (2021)"},{"key":"2091_CR7","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.dam.2019.12.015","volume":"283","author":"A B\u00e4rmann","year":"2020","unstructured":"B\u00e4rmann, A., Gemander, P., Merkert, M.: The clique problem with multiple-choice constraints under a cycle-free dependency graph. Discrete Appl. Math. 283, 59\u201377 (2020)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"2091_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s12469-017-0160-4","volume":"9","author":"A B\u00e4rmann","year":"2017","unstructured":"B\u00e4rmann, A., Martin, A., Schneider, O.: A comparison of performance metrics for balancing the power consumption of trains in a railway network by slight timetable adaptation. Public Transp. 9(1\u20132), 95\u2013113 (2017)","journal-title":"Public Transp."},{"issue":"3","key":"2091_CR9","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1287\/trsc.2020.1021","volume":"55","author":"A B\u00e4rmann","year":"2021","unstructured":"B\u00e4rmann, A., Martin, A., Schneider, O.: Efficient formulations and decomposition approaches for power peak reduction in railway traffic via timetabling. Transp. Sci. 55(3), 747\u2013767 (2021)","journal-title":"Transp. Sci."},{"issue":"1","key":"2091_CR10","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/BF01583795","volume":"23","author":"R Fourer","year":"1982","unstructured":"Fourer, R.: Solving staircase linear programs by the simplex method, 1: inversion. Math. Program. 23(1), 274\u2013313 (1982)","journal-title":"Math. Program."},{"issue":"3","key":"2091_CR11","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF02594780","volume":"25","author":"R Fourer","year":"1982","unstructured":"Fourer, R.: Solving staircase linear programs by the simplex method, 2: pricing. Math. Program. 25(3), 251\u2013292 (1982)","journal-title":"Math. Program."},{"issue":"1","key":"2091_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/1026001","volume":"26","author":"R Fourer","year":"1984","unstructured":"Fourer, R.: Staircase matrices and systems. SIAM Rev. 26(1), 1\u201370 (1984)","journal-title":"SIAM Rev."},{"key":"2091_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"2091_CR14","unstructured":"Gurobi Optimization LLC: Gurobi optimizer reference manual (2020). http:\/\/www.gurobi.com"},{"key":"2091_CR15","unstructured":"Hagberg, A., Swart, P., Chult, D.S.: Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States) (2008)"},{"key":"2091_CR16","doi-asserted-by":"crossref","unstructured":"Jabrayilov, A., Mutzel, P.: New integer linear programming models for the vertex coloring problem. In: Latin American Symposium on Theoretical Informatics, pp. 640\u2013652. Springer (2018)","DOI":"10.1007\/978-3-319-77404-6_47"},{"key":"2091_CR17","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger J.D. (eds.) Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, pp. 85\u2013103. Springer US, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"2091_CR18","doi-asserted-by":"publisher","first-page":"2863","DOI":"10.1137\/15M1006751","volume":"26","author":"F Liers","year":"2016","unstructured":"Liers, F., Merkert, M.: Structural investigation of piecewise linearized network flow problems. SIAM J. Optim. 26(4), 2863\u20132886 (2016)","journal-title":"SIAM J. Optim."},{"key":"2091_CR19","unstructured":"Merkert, M.: Solving mixed-integer linear and nonlinear network optimization problems by local reformulations and relaxations. Ph.D. thesis, Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg (FAU) (2017). https:\/\/opus4.kobv.de\/opus4-fau\/frontdoor\/index\/index\/docId\/9403"},{"issue":"1","key":"2091_CR20","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111\u2013114 (1979). https:\/\/doi.org\/10.1137\/0208008","journal-title":"SIAM J. Comput."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-022-02091-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-022-02091-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-022-02091-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T08:11:28Z","timestamp":1674461488000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-022-02091-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,29]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["2091"],"URL":"https:\/\/doi.org\/10.1007\/s10957-022-02091-2","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2022,10,29]]},"assertion":[{"value":"31 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2023","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}