The complexity landscape of decompositional parameters for ILP. (English) Zbl 1451.90099
Summary: Integer Linear Programming (ILP) can be seen as the archetypical problem for NP-complete optimization problems, and a wide range of problems in artificial intelligence are solved in practice via a translation to ILP. Despite its huge range of applications, only few tractable fragments of ILP are known, probably the most prominent of which is based on the notion of total unimodularity. Using entirely different techniques, we identify new tractable fragments of ILP by studying structural parameterizations of the constraint matrix within the framework of parameterized complexity.
In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we give an overview of the complexity of ILP w.r.t. decompositional parameters defined on the constraint matrix.
In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we give an overview of the complexity of ILP w.r.t. decompositional parameters defined on the constraint matrix.
MSC:
| 90C10 | Integer programming |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Alumur, S. A.; Kara, B. Y., Network hub location problems: the state of the art, Eur. J. Oper. Res., 190, 1, 1-21 (2008) · Zbl 1146.90455 |
| [2] | Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 2, 125-150 (2000) · Zbl 1009.68102 |
| [3] | Cunningham, W. H.; Geelen, J., On integer programming and the branch-width of the constraint matrix, (Fischetti, M.; Williamson, D. P., Integer Programming and Combinatorial Optimization, Proceedings. Integer Programming and Combinatorial Optimization, Proceedings, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007. Integer Programming and Combinatorial Optimization, Proceedings. Integer Programming and Combinatorial Optimization, Proceedings, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Lecture Notes in Computer Science, vol. 4513 (2007), Springer), 158-166 · Zbl 1136.90403 |
| [4] | Cygan, M.; Fomin, F. V.; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Springer · Zbl 1334.90001 |
| [5] | De Loera, J. A.; Hemmecke, R.; Köppe, M., Algebraic and Geometric Ideas in the Theory of Discrete Optimization, MOS-SIAM Series on Optimization, vol. 14 (2013), SIAM · Zbl 1401.90012 |
| [6] | Diestel, R., Graph Theory, Graduate Texts in Mathematics, vol. 173 (2012), Springer |
| [7] | Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity, Texts in Computer Science (2013), Springer · Zbl 1358.68006 |
| [8] | Fellows, M. R.; Lokshtanov, D.; Misra, N.; Rosamond, F. A.; Saurabh, S., Graph layout problems parameterized by vertex cover, (ISAAC. ISAAC, Lecture Notes in Computer Science (2008), Springer), 294-305 · Zbl 1183.68424 |
| [9] | Fischer, E.; Makowsky, J. A.; Ravve, E. R., Counting truth assignments of formulas of bounded tree-width or clique-width, Discrete Appl. Math., 156, 4, 511-529 (2008) · Zbl 1131.68093 |
| [10] | Floudas, C.; Lin, X., Mixed integer linear programming in process scheduling: modeling, algorithms, and applications, Ann. Oper. Res., 139, 1, 131-162 (2005) · Zbl 1091.90055 |
| [11] | Flum, J.; Grohe, M., Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, vol. XIV (2006), Springer Verlag: Springer Verlag Berlin · Zbl 1143.68016 |
| [12] | Frank, A.; Tardos, É., An application of simultaneous diophantine approximation in combinatorial optimization, Combinatorica, 7, 1, 49-65 (1987) · Zbl 0641.90067 |
| [13] | Ganian, R.; Szeider, S., Community structure inspired algorithms for SAT and #SAT, (Theory and Applications of Satisfiability Testing, Proceedings. Theory and Applications of Satisfiability Testing, Proceedings, 18th International Conference, SAT 2015, Austin, Texas, USA, September 24-27, 2015. Theory and Applications of Satisfiability Testing, Proceedings. Theory and Applications of Satisfiability Testing, Proceedings, 18th International Conference, SAT 2015, Austin, Texas, USA, September 24-27, 2015, Lecture Notes in Computer Science, vol. 9340 (2015), Springer), 294-305 · Zbl 1471.68322 |
| [14] | Ganian, R.; Hliněný, P.; Obdržálek, J., Better algorithms for satisfiability problems for formulas of bounded rank-width, Fundam. Inform., 123, 1, 59-76 (2013) · Zbl 1280.68239 |
| [15] | Ganian, R.; Kim, E. J.; Szeider, S., Algorithmic applications of tree-cut width, (Mathematical Foundations of Computer Science 2015, Proceedings, Part II. Mathematical Foundations of Computer Science 2015, Proceedings, Part II, 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015 (2015)), 348-360 · Zbl 1465.68211 |
| [16] | Garey, M. R.; Johnson, D. R., Computers and Intractability (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco, New York · Zbl 0411.68039 |
| [17] | Gaspers, S.; Szeider, S., Backdoors to satisfaction, (The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, vol. 7370 (2012), Springer Verlag), 287-317 · Zbl 1358.68133 |
| [18] | Gutin, G.; Jones, M.; Wahlström, M., Structural parameterizations of the Mixed Chinese Postman Problem, (Algorithms, Proceedings. Algorithms, Proceedings, 23rd Annual European Symposium, ESA 2015, Patras, Greece, September 14-16, 2015 (2015)), 668-679 · Zbl 1467.68074 |
| [19] | Hemmecke, R.; Onn, S.; Romanchuk, L., N-fold integer programming in cubic time, Math. Program., 137, 1-2, 325-341 (2013) · Zbl 1262.90104 |
| [20] | Jansen, B. M.P.; Kratsch, S., A structural approach to kernels for ILPs: treewidth and total unimodularity, (Algorithms, Proceedings. Algorithms, Proceedings, 23rd Annual European Symposium, ESA 2015, Patras, Greece, September 14-16, 2015. Algorithms, Proceedings. Algorithms, Proceedings, 23rd Annual European Symposium, ESA 2015, Patras, Greece, September 14-16, 2015, Lecture Notes in Computer Science, vol. 9294 (2015), Springer), 779-791 · Zbl 1466.68046 |
| [21] | Kannan, R., Minkowski’s convex body theorem and integer programming, Math. Oper. Res., 12, 3, 415-440 (1987) · Zbl 0639.90069 |
| [22] | Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 4, 538-548 (1983) · Zbl 0524.90067 |
| [23] | Lodi, A.; Martello, S.; Monaci, M., Two-dimensional packing problems: a survey, Eur. J. Oper. Res., 141, 2, 241-252 (2002) · Zbl 1081.90576 |
| [24] | Nešetřil, J.; Ossona de Mendez, P., Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28 (2012), Springer · Zbl 1268.05002 |
| [25] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [26] | Onn, S., Nonlinear Discrete Optimization, Zurich Lectures in Advanced Mathematics (2010), European Mathematical Society · Zbl 1219.90003 |
| [27] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall · Zbl 0503.90060 |
| [28] | Papadimitriou, C. H., On the complexity of integer programming, J. ACM, 28, 4, 765-768 (1981) · Zbl 0468.68050 |
| [29] | Szeider, S., Finding paths in graphs avoiding forbidden transitions, Discrete Appl. Math., 126, 2-3, 239-251 (2003) · Zbl 1010.68099 |
| [30] | (Toth, P.; Vigo, D., The Vehicle Routing Problem (2001), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA) · Zbl 0966.90009 |
| [31] | van den Briel, M.; Vossen, T.; Kambhampati, S., Reviving integer programming approaches for AI planning: a branch-and-cut framework, (Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling. Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling, ICAPS 2005, Monterey, California, USA, June 5-10, 2005 (2005), AAAI), 310-319 |
| [32] | Vossen, T.; Ball, M. O.; Lotem, A.; Nau, D. S., On the use of integer programming models in AI planning, (Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July 31-August 6, 1999 (1999), Morgan Kaufmann), 304-309, (2 volumes, 1450 pages) |
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.
