A new and faster representation for counting integer points in parametric polyhedra

Dmitry V. Gribanov; Dmitry S. Malyshev; P. M. Pardalos; Zolotykh N. Y.

doi:10.1007/s10589-024-00632-1

Публикации

?

A new and faster representation for counting integer points in parametric polyhedra

Computational Optimization and Applications. 2025. Vol. 92. P. 811–861.

Dmitry V. Gribanov, Dmitry S. Malyshev, Пардалос П. О., Zolotykh N. Y.

Научное направление: Компьютерные науки Математика

Язык: английский

Полный текст

DOI

Текст на другом сайте

Ключевые слова: integer linear programming Short rational generating function subset-sum problem Bounded sub-determinants counting problem parametric integer programming multidimensional knapsack problem

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Сетевые и графовые модели, сложность алгоритмов и интеллектуальный анализ данных (2025)

Proceedings of the 6th Workshop on Computational Approaches to Discourse, Context and Document-Level Inferences (CODI 2025)

Strube M., Braud C., Hardmeier C. и др., Suzhou: Association for Computational Linguistics, 2025.

Добавлено: 11 июня 2026 г.

On the Ramsey Number R(K_{1,s},P_t)

Kh. Kh. Abdullin, D. B. Mokeev, D. S. Taletskii, Mathematical notes 2026 Vol. 119 No. 1 P. 3–7

Добавлено: 10 июня 2026 г.

TreeDQN: Sample-efficient off-policy reinforcement learning for combinatorial optimization

Sorokin D., Kostin A., Савченко Л. В. и др., Knowledge-Based Systems 2026 Vol. 348 Article 116258

Добавлено: 10 июня 2026 г.

Microbial diversity and production of milk spirit using traditional Buryat fermentation and distillation technologies

Namsaraev Z., Nanzatov B., Козлова А. Д. и др., Scientific Reports 2026 Vol. 16 No. 1 Article 17769

Дистиллированные кисломолочные напитки встречаются в пищевой промышленности редко, несмотря на повсеместное распространение растительных спиртных напитков. В настоящее время производство крепких дистиллированных алкогольных напитков из кисломолочных продуктов с использованием традиционных технологий известно лишь среди монголоязычных народов и их сибирских соседей. Данное исследование представляет собой первый междисциплинарный анализ дарасуна, традиционного бурятского спиртного напитка, изготавливаемого из кисломолочного напитка ...

Добавлено: 10 июня 2026 г.

Artificial intelligence and digital twins for failure prediction in data center cooling systems: a comprehensive literature review (2018–2026)

Butorova A., Bobakov V., Sergeev A. и др., European Physical Journal: Special Topics 2026 P. 1–19

Добавлено: 10 июня 2026 г.

Innovations in Information and Decision Sciences. Proceedings of the 13th International Conference on Frontiers in Intelligent Computing: Theory and Applications (FICTA 2025), Volume 4

Springer, 2026.

Добавлено: 8 июня 2026 г.

Wave dynamics within the Whitham-Ostrovsky equation

Flamarion M. V., Пелиновский Е. Н., Nonlinear Dynamics 2026 Vol. 114 Article 784

Добавлено: 5 июня 2026 г.

On a simple connection between Δ-modular ILP and LP, and a new bound on the number of integer vertices

Грибанов Д. В., Малышев Д. С., Shumilov I., Operations Research Forum 2024 Vol. 5 Article 32

Добавлено: 4 апреля 2024 г.

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems

Грибанов Д. В., Shumilov I., Малышев Д. С. и др., Journal of Global Optimization 2024 Vol. 89 P. 1033–1067

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 , assuming that P is a polyhedron, defined by systems Ax ≤ b or Ax = b, x ≥ 0 with a sparse ...

Добавлено: 6 марта 2024 г.

A faster algorithm for counting the integer points number in ∆-modular polyhedra

Грибанов Д. В., Малышев Д. С., Siberian Electronic Mathematical Reports 2022 Vol. 19 No. 2 P. 613–626

Добавлено: 19 сентября 2022 г.

On Delta-modular integer linear problems in the canonical form and equivalent problems

Грибанов Д. В., Shumilov I., Dmitry Malyshev и др., Journal of Global Optimization 2024 Vol. 88 P. 591–651

Добавлено: 10 мая 2022 г.

Cost-Effective V2X Task Offloading in MEC-assisted Intelligent Transportation Systems

Белогаев А. А., Alexey Elokhin, Красилов А. Н. и др., IEEE Access 2020 Vol. 8 P. 169010–169023

Добавлено: 18 сентября 2020 г.

A Mathematical Model for the Astronaut Training Scheduling Problem

Мусатова Е. Г., Лазарев А. А., Ponomarev K. и др., IFAC-PapersOnLine 2016 Vol. 49 No. 12 P. 221–225

We consider a problem of the astronaut training scheduling. Each astronaut has his own set of tasks which should be performed with respect to resource and time constraints. The problem is to determine start moments for all considered tasks. For this issue a mathematical model based on integer linear programming is proposed. Computational results of ...

Добавлено: 31 октября 2016 г.

Calculating the minimal fraction of thepopular vote to win the U.S. Presidency in the electoral college

Беленький А. С., Computers & Mathematics with Applications 2005 Vol. 50 No. 5-6 P. 783–802

As is known, in U.S. presidential elections, all 50 states and the District of Columbi(DC) award their electoral votes to (the electors of) U.S. presidential candidates based on the popular vote received by (the electors of) the candidates there (although two different schemes of awarding the electoral votes are currently applied in the U.S.). For ...

Добавлено: 21 октября 2016 г.

Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений

Грибанов Д. В., Малышев Д. С., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19–31

Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...

Добавлено: 20 октября 2016 г.

Целочисленные постановки задачи формирования железнодорожных составов и расписания их движения

Лазарев А. А., Мусатова Е. Г., Управление большими системами: сборник трудов 2012 № 38 С. 161–169

Рассматривается задача формирования грузовых составов и маршрутов их следования по железнодорожной сети. Необходимо их следования по железнодорожной сети. Необходимо из имеющихся на станциях заказов сформировать составы и определить расписание и маршрут их движения до станций назначения так, чтобы минимизировать суммарное взвешенное время выполнения заказов. Предлагаются целочисленные постановки данной задачи, учитывающие ограничения, возникающие на практике. ...

Добавлено: 23 ноября 2012 г.