Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems

作者：D. Gribanov, Ivan A. Shumilov, D. Malyshev, N. Zolotykh · 发表于：Journal of Global Optimization · 年份：2022 · DOI：10.1007/s10898-024-01379-z · 被引用次数：7 · 研究领域：Computer Science、Mathematics

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P∩Zn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\mathcal {P}}\,}}\cap {{\,\mathrm{\mathbb {Z}}\,}}^n$$\end{document}, assuming that P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\mathcal {P}}\,}}$$\end{document} is a polyhedron, defined by systems Ax≤b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A x \le b$$\end{document} or Ax=b,x≥0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Ax = b,\, x \ge 0$$\end{document} with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on spars...