{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T10:27:56Z","timestamp":1777544876172,"version":"3.51.4"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T00:00:00Z","timestamp":1563494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Grantov\u00e1 Agentura \u00f0esk\u00e9 Republiky","award":["17-09142S"],"award-info":[{"award-number":["17-09142S"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["308\/18"],"award-info":[{"award-number":["308\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, and so on, were achieved by applying the theory of so-called\n            <jats:italic>n<\/jats:italic>\n            -fold integer programming. An\n            <jats:italic>n<\/jats:italic>\n            -fold integer program (IP) has a highly uniform block structured constraint matrix. Hemmecke, Onn, and Romanchuk [Math. Program., 2013] showed an algorithm with runtime \u0394\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>rst<\/jats:italic>\n              +\n              <jats:italic>r<\/jats:italic>\n              <jats:sup>\n                2\n                <jats:italic>s<\/jats:italic>\n              <\/jats:sup>\n              )\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            , where \u0394 is the largest coefficient,\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>s<\/jats:italic>\n            , and\n            <jats:italic>t<\/jats:italic>\n            are dimensions of blocks of the constraint matrix and\n            <jats:italic>n<\/jats:italic>\n            is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and\n            <jats:italic>n<\/jats:italic>\n            -fold IPs have the special property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. However, this algorithm has never been implemented and evaluated.\n          <\/jats:p>\n          <jats:p>\n            We have implemented the algorithm and learned the following along the way. The original algorithm is practically unusable, but we discover a series of improvements that make its evaluation possible. Crucially, we observe that a certain constant in the algorithm can be treated as a tuning parameter, which yields an efficient heuristic (essentially searching in a smaller-than-guaranteed neighborhood). Furthermore, the algorithm uses an overly expensive strategy to find a \u201cbest\u201d step, while finding only an \u201capproximately best\u201d step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on\n            <jats:italic>n<\/jats:italic>\n            from\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            to\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>Finally, we tested the behavior of the algorithm with various values of the tuning parameter and different strategies of finding improving steps. First, we show that decreasing the tuning parameter initially leads to an increased number of iterations needed for convergence and eventually to getting stuck in local optima, as expected. However, surprisingly small values of the parameter already exhibit good behavior while significantly lowering the time the algorithm spends per single iteration. Second, our new strategy for finding \u201capproximately best\u201d steps wildly outperforms the original construction.<\/jats:p>","DOI":"10.1145\/3330137","type":"journal-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:14Z","timestamp":1563542234000},"page":"1-22","source":"Crossref","is-referenced-by-count":11,"title":["Evaluating and Tuning\n            <i>n<\/i>\n            -fold Integer Programming"],"prefix":"10.1145","volume":"24","author":[{"given":"Kate\u0159ina","family":"Altmanov\u00e1","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, Charles University, Praha, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[{"name":"Algorithmics and Computational Complexity, Faculty\u00a0IV, Technische Univerzit\u00e4t Berlin, Germany and Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Praha, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Kouteck\u00fd","sequence":"additional","affiliation":[{"name":"Technion\u2013Israel Institute of Technology, Israel and Computer Science Institute, Charles University, Praha, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,19]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"4ti2 team. 2001\u20132018. 4ti2\u2014A software package for algebraic geometric and combinatorial problems on linear spaces. Retrieved from www.4ti2.de.  4ti2 team. 2001\u20132018. 4ti2\u2014A software package for algebraic geometric and combinatorial problems on linear spaces. Retrieved from www.4ti2.de."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.10.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.08.007"},{"key":"e_1_2_1_4_1","volume-title":"Production Factor Mathematics","author":"Bornd\u00f6rfer Ralf","unstructured":"Ralf Bornd\u00f6rfer , Martin Gr\u00f6tschel , and Ulrich J\u00e4ger . 2010. Planning problems in public transit . In Production Factor Mathematics . Springer , 95--121. Ralf Bornd\u00f6rfer, Martin Gr\u00f6tschel, and Ulrich J\u00e4ger. 2010. Planning problems in public transit. In Production Factor Mathematics. Springer, 95--121."},{"key":"e_1_2_1_5_1","volume-title":"In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","volume":"107","author":"Chatzigiannakis Ioannis","year":"2018","unstructured":"Ioannis Chatzigiannakis , Christos Kaklamanis , D\u00e1niel Marx , and Donald Sannella ( Eds .). 2018 . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) . LIPIcs, vol. 107 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Retrieved from http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-076-7. Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella (Eds.). 2018. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918). LIPIcs, vol. 107. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Retrieved from http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-076-7."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175482"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790248.2790250"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0518-7"},{"key":"e_1_2_1_9_1","volume-title":"Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM Series on Optimization","author":"De Loera Jesus A.","unstructured":"Jesus A. De Loera , Raymond Hemmecke , and Matthias K\u00f6ppe . 2013. Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM Series on Optimization , vol. 14 . SIAM. Jesus A. De Loera, Raymond Hemmecke, and Matthias K\u00f6ppe. 2013. Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM Series on Optimization, vol. 14. SIAM."},{"key":"e_1_2_1_10_1","unstructured":"Friedrich Eisenbrand Christoph Hunkenschr\u00f6der and Kim-Manuel Klein. 2018. Faster algorithms for integer programs with block structure. See Reference {5} 49:1--49:13.  Friedrich Eisenbrand Christoph Hunkenschr\u00f6der and Kim-Manuel Klein. 2018. Faster algorithms for integer programs with block structure. See Reference {5} 49:1--49:13."},{"key":"e_1_2_1_11_1","unstructured":"Friedrich Eisenbrand Christoph Hunkenschr\u00f6der Kim-Manuel Klein Martin Kouteck\u00fd Asaf Levin and Shmuel Onn. 2019. An algorithmic theory of integer programming. Retrieved from http:\/\/arxiv.org\/abs\/1904.01361.  Friedrich Eisenbrand Christoph Hunkenschr\u00f6der Kim-Manuel Klein Martin Kouteck\u00fd Asaf Levin and Shmuel Onn. 2019. An algorithmic theory of integer programming. Retrieved from http:\/\/arxiv.org\/abs\/1904.01361."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-015-0297-2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0395-5"},{"key":"e_1_2_1_14_1","unstructured":"Gurobi Optimization Inc. 2016. Gurobi Optimizer Reference Manual. Retrieved from http:\/\/www.gurobi.com.  Gurobi Optimization Inc. 2016. Gurobi Optimizer Reference Manual. Retrieved from http:\/\/www.gurobi.com."},{"key":"e_1_2_1_15_1","volume-title":"Beck","author":"Heinz Stefan","year":"2013","unstructured":"Stefan Heinz , Wen-Yang Ku , and Christopher J . Beck . 2013 . Recent improvements using constraint integer programming for resource allocation and scheduling. In Proceedings of the International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems. Springer , 12--27. Stefan Heinz, Wen-Yang Ku, and Christopher J. Beck. 2013. Recent improvements using constraint integer programming for resource allocation and scheduling. In Proceedings of the International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems. Springer, 12--27."},{"key":"e_1_2_1_16_1","unstructured":"Raymond Hemmecke. 2004. Exploiting symmetries in the computation of graver bases. arXiv preprint math\/0410334.  Raymond Hemmecke. 2004. Exploiting symmetries in the computation of graver bases. arXiv preprint math\/0410334."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0638-z"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0490-y"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2007.55"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919)","volume":"124","author":"Jansen Klaus","year":"2019","unstructured":"Klaus Jansen , Kim-Manuel Klein , Marten Maack , and Malin Rau . 2019 . Empowering the configuration-IP\u2014New PTAS results for scheduling with setups times . In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919) (LIPIcs), Avrim Blum (Ed.) , vol. 124 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 44:1--44:19. Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. 2019. Empowering the configuration-IP\u2014New PTAS results for scheduling with setups times. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919) (LIPIcs), Avrim Blum (Ed.), vol. 124. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 44:1--44:19."},{"key":"e_1_2_1_21_1","unstructured":"Klaus Jansen Alexandra Lassota and Lars Rohwedder. 2018. Near-linear time algorithm for n-fold ILPs via color coding. Retrieved from http:\/\/arxiv.org\/abs\/1811.00950.  Klaus Jansen Alexandra Lassota and Lars Rohwedder. 2018. Near-linear time algorithm for n-fold ILPs via color coding. Retrieved from http:\/\/arxiv.org\/abs\/1811.00950."},{"key":"e_1_2_1_22_1","volume-title":"Sylvain Corlay et al","author":"Kluyver Thomas","year":"2016","unstructured":"Thomas Kluyver , Benjamin Ragan-Kelley , Fernando P\u00e9rez , Brian E. Granger , Matthias Bussonnier , Jonathan Frederic , Kyle Kelley , Jessica B. Hamrick , Jason Grout , Sylvain Corlay et al . 2016 . Jupyter notebooks-a publishing format for reproducible computational workflows. In Proceedings of the International Conference on Electronic Publishing (ELPUB\u2019 16). 87--90. Thomas Kluyver, Benjamin Ragan-Kelley, Fernando P\u00e9rez, Brian E. Granger, Matthias Bussonnier, Jonathan Frederic, Kyle Kelley, Jessica B. Hamrick, Jason Grout, Sylvain Corlay et al. 2016. Jupyter notebooks-a publishing format for reproducible computational workflows. In Proceedings of the International Conference on Electronic Publishing (ELPUB\u201916). 87--90."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-017-0550-0"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201917)","volume":"87","author":"Knop Du\u0161an","year":"2017","unstructured":"Du\u0161an Knop , Martin Kouteck\u00fd , and Matthias Mnich . 2017 . Combinatorial n-fold integer programming and applications . In Proceedings of the European Symposium on Algorithms (ESA\u201917) (Leibniz Int. Proc. Informatics) , vol. 87 . 54:1--54:14. Du\u0161an Knop, Martin Kouteck\u00fd, and Matthias Mnich. 2017. Combinatorial n-fold integer programming and applications. In Proceedings of the European Symposium on Algorithms (ESA\u201917) (Leibniz Int. Proc. Informatics), vol. 87. 54:1--54:14."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201917)","volume":"66","author":"Knop Du\u0161an","year":"2017","unstructured":"Du\u0161an Knop , Martin Kouteck\u00fd , and Matthias Mnich . 2017 . Voting and bribing in single-exponential time . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201917) (Leibniz Int. Proc. Informatics) , vol. 66 . 46:1--46:14. Du\u0161an Knop, Martin Kouteck\u00fd, and Matthias Mnich. 2017. Voting and bribing in single-exponential time. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201917) (Leibniz Int. Proc. Informatics), vol. 66. 46:1--46:14."},{"key":"e_1_2_1_26_1","volume-title":"MIPLIB 2010","author":"Koch Thorsten","year":"2011","unstructured":"Thorsten Koch , Tobias Achterberg , Erling Andersen , Oliver Bastert , Timo Berthold , Robert E. Bixby , Emilie Danna , Gerald Gamrath , Ambros M. Gleixner , Stefan Heinz et al. 2011 . MIPLIB 2010 . Math. Program. Comput. 3, 2 ( 2011 ), 103. Thorsten Koch, Tobias Achterberg, Erling Andersen, Oliver Bastert, Timo Berthold, Robert E. Bixby, Emilie Danna, Gerald Gamrath, Ambros M. Gleixner, Stefan Heinz et al. 2011. MIPLIB 2010. Math. Program. Comput. 3, 2 (2011), 103."},{"key":"e_1_2_1_27_1","unstructured":"Martin Kouteck\u00fd Asaf Levin and Shmuel Onn. 2018. A parameterized strongly polynomial algorithm for block structured integer programs. See Reference {5} 85:1--85:14.  Martin Kouteck\u00fd Asaf Levin and Shmuel Onn. 2018. A parameterized strongly polynomial algorithm for block structured integer programs. See Reference {5} 85:1--85:14."},{"key":"e_1_2_1_28_1","volume-title":"Mixed integer programming computation. In 50 Years of Integer Programming 1958--2008","author":"Lodi Andrea","unstructured":"Andrea Lodi . 2010. Mixed integer programming computation. In 50 Years of Integer Programming 1958--2008 . Springer , 619--645. Andrea Lodi. 2010. Mixed integer programming computation. In 50 Years of Integer Programming 1958--2008. Springer, 619--645."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4171\/093"},{"key":"e_1_2_1_30_1","volume-title":"Handbook of Metaheuristics","author":"Pisinger David","unstructured":"David Pisinger and Stefan Ropke . 2010. Large neighborhood search . In Handbook of Metaheuristics . Springer , 399--419. David Pisinger and Stefan Ropke. 2010. Large neighborhood search. In Handbook of Metaheuristics. Springer, 399--419."},{"key":"e_1_2_1_31_1","volume-title":"Wolsey","author":"Pochet Yves","year":"2006","unstructured":"Yves Pochet and Laurence A . Wolsey . 2006 . Production Planning by Mixed Integer Programming. Springer Science 8 Business Media. Yves Pochet and Laurence A. Wolsey. 2006. Production Planning by Mixed Integer Programming. Springer Science 8 Business Media."},{"key":"e_1_2_1_32_1","volume-title":"Programming Languages and Systems in Computational Economics and Finance","author":"Saltzman Matthew J.","unstructured":"Matthew J. Saltzman . 2002. COIN-OR: An open-source library for optimization . In Programming Languages and Systems in Computational Economics and Finance . Springer , 3--32. Matthew J. Saltzman. 2002. COIN-OR: An open-source library for optimization. In Programming Languages and Systems in Computational Economics and Finance. Springer, 3--32."},{"key":"e_1_2_1_33_1","first-page":"200","article-title":"Operations research with GNU linear programming kit. Vaasa: Department of Mathematics and Statistics, University of Vaasa","volume":"1020","author":"Sottinen Tommi","year":"2009","unstructured":"Tommi Sottinen . 2009 . Operations research with GNU linear programming kit. Vaasa: Department of Mathematics and Statistics, University of Vaasa , Finland 1020 (2009), 200 . Tommi Sottinen. 2009. Operations research with GNU linear programming kit. Vaasa: Department of Mathematics and Statistics, University of Vaasa, Finland 1020 (2009), 200.","journal-title":"Finland"},{"key":"e_1_2_1_34_1","unstructured":"The Sage Developers. 2017. SageMath the Sage Mathematics Software System (Version 7.6). Retrieved from http:\/\/www.sagemath.org.  The Sage Developers. 2017. SageMath the Sage Mathematics Software System (Version 7.6). Retrieved from http:\/\/www.sagemath.org."},{"key":"e_1_2_1_35_1","volume-title":"Constantine Evans, Clark Fitzgerald, Brian, and Adel Qalieh.","author":"Waskom Michael","year":"2018","unstructured":"Michael Waskom , Olga Botvinnik , Drew O\u2019Kane , Paul Hobson , Joel Ostblom , Saulius Lukauskas , David C. Gemperline , Tom Augspurger , Yaroslav Halchenko , John B. Cole , Jordi Warmenhoven , Julian de Ruiter , Cameron Pye , Stephan Hoyer , Jake Vanderplas , Santi Villalba , Gero Kunter , Eric Quintero , Pete Bachant , Marcel Martin , Kyle Meyer , Alistair Miles , Yoav Ram , Thomas Brunner , Tal Yarkoni , Mike Lee Williams , Constantine Evans, Clark Fitzgerald, Brian, and Adel Qalieh. 2018 . mwaskom\/seaborn: v0.9.0. Retrieved September 3, 2019 from https:\/\/github.com\/mwaskom\/seaborn\/issues\/252. Michael Waskom, Olga Botvinnik, Drew O\u2019Kane, Paul Hobson, Joel Ostblom, Saulius Lukauskas, David C. Gemperline, Tom Augspurger, Yaroslav Halchenko, John B. Cole, Jordi Warmenhoven, Julian de Ruiter, Cameron Pye, Stephan Hoyer, Jake Vanderplas, Santi Villalba, Gero Kunter, Eric Quintero, Pete Bachant, Marcel Martin, Kyle Meyer, Alistair Miles, Yoav Ram, Thomas Brunner, Tal Yarkoni, Mike Lee Williams, Constantine Evans, Clark Fitzgerald, Brian, and Adel Qalieh. 2018. mwaskom\/seaborn: v0.9.0. Retrieved September 3, 2019 from https:\/\/github.com\/mwaskom\/seaborn\/issues\/252."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3330137","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3330137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:23Z","timestamp":1750206383000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3330137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,19]]},"references-count":35,"alternative-id":["10.1145\/3330137"],"URL":"https:\/\/doi.org\/10.1145\/3330137","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,19]]}}}