(no subject)
В своей лекции №5 Нестеров рассказывал об
алгоритмах целочисленного программирования
(integer linear programming, ILP) полиномиальной
сложности в фикс. разм.
См. его статью:
Yu.Nesterov (2004) "Fast Fourier Transform and its
applications to integer knapsack problems"
http://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2004_64.pdf
Отправной точкой является, так называемый
Barvinok’s algorithm. Далее ссылки про него.
A.I.Barvinok (1993) "Computing the volume, counting integral points, and exponential sums"
Discrete Comput. Geom. 10, 123-141. MR 94d:52005
http://www.springerlink.com/content/uh13667243q06665/fulltext.pdf
A.I.Barvinok (1994) “A polynomial time algorithm for counting integral points in polyhedra
when the dimension is fixed”, Math. Oper. Res. 19, 769-779.
http://www.jstor.org/stable/3690312
A.I.Barvinok, J.E.Pommersheim (1999) "An algorithmic theory of lattice points in polyhedra"
In: “New perspectives in algebraic combinatorics”, MSRI Publications, 38, 91 - 147.
http://www.math.lsa.umich.edu/~barvinok/functions.ps
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.170.9496
A.I.Barvinok, K.Woods (2003) "Short rational generating functions for lattice point problems"
http://www.oberlin.edu/math/faculty/woods/research/gf-jams.pdf
A.I. Barvinok (2005) "Computing the Ehrhart quasi-polynomial of a rational simplex"
Mathematics of Computation. http://front.math.ucdavis.edu/0504.5444
M.Brion, M.Vergne (1997) "Residue formulae, vector partition functions and lattice
points in rational polytopes" J. Amer. Math, Soc., 10, 79 -833.
http://reference.kfupm.edu.sa/content/r/e/residue_formulae__vector_partition_funct_56659.pdf
M.Dyer, R.Kannan (1997) "On Barvinok’s algorithm for counting lattice points in fixed dimension"
Math. Oper. Res., 22(3):545-549, 1997.
http://www.jstor.org/stable/3690392
http://mathor.highwire.org/content/22/3/545.short
M.Cryan, M.Dyer, L.A.Goldberg, M.Jerrum, R.Martin (2000) "Rapidly Mixing Markov Chains for
Sampling Contingency Tables with a Constant Number of Rows"
http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Dyer/Dyer5.pdf
B.Chen (2002) "Lattice points, Dedekind sums and Ehrhart polynomials of lattice polyhedra"
Discrete Comput. Geom. 28, 175-199.
http://www.math.ust.hk/~mabfchen/Paper/Lattice-Points-Dedekind.pdf
J.B. Lasserre, E.S. Zeron (2001) "On Counting Integral Points in a Convex Rational Polytope"
Math. of Operat. Res., Vol.28, No.4, pp. 853-870.
https://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Lasserre/lasserrezeroncounting.pdf
J.B. Lasserre, E.S. Zeron (2001) "Solving a class of multivariate integration problems via Laplace techniques"
Appl. Math. (Warsaw), 28, pp. 391-405.
https://www.impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/applicationes-mathematicae/all/28/4/84463/solving-a-class-of-multivariate-integration-problems-via-laplace-techniques
J.B. Lasserre, E.S. Zeron (2001) "A Laplace transform algorithm for the volume of a convex polytope" J. ACM 48, 1126-1140.
http://homepages.wmich.edu/~ledyaev/lasserre-vol.pdf
J.B.Lasserre, E.S.Zeron (2002) "Solving the knapsack problem via Z-transform"
Operat. Res. Lett. archive, Vol.30 I.6, Pp.:394-400.
http://www.sciencedirect.com/science/article/pii/S016763770200161X
J.B. Lasserre (2003) "Integer programming, Barvinok’s counting algorithm and
Gomory relaxations" Oper. Res. Letters, 32:133-137, 2003.
http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Lasserre/barvinok.pdf
J.B.Lasserre (2004) "Generating functions and duality for integer programs"
Discrete Optimization 1, 167-187.
http://www.optimization-online.org/DB_FILE/2003/12/786.pdf
J.A. De Loera, D.Haws, R.Hemmecke, P.Huggins, R.Yoshida (2004) "Three kinds of integer
programming algorithms based on barvinok’s rational functions" 10th Int. IPCO Conf. LNCS.
http://www.springerlink.com/content/eq5qkgvxxyquypc3/
M.Köppe (2006) "A primal Barvinok’s algorithm based on irrational decompositions"
http://www.math.ucdavis.edu/~latte/theory/primalBarvinokAlgoBasedOnIrrationalDecompositions.pdf
Yu. Nesterov (2004) "Performance of trigonometric generating functions on some combinatorial problems"
http://www.core.ucl.ac.be/services/psfiles/dp05/dp2005_69.pdf
W.Baldoi-Silva, J.A. De Loera, M.Vergne (2003) "Counting Integer Flows in Networks"
http://www.math.ucdavis.edu/~latte/theory/totalresidue.pdf
K. Aardal, R. Weismantel, L.A. Wolsey (2002) "Non-standard
approaches to integer programming," Discr. Appl. Math. 123, 5-74.
https://www.ima.umn.edu/talks/workshops/10-14-19.2002/aardal/ut6n.pdf
R.R. Thomas (2001) "Algebraic methods in integer programming,"
Encyclopedia of Optimization (eds: C. Floudas and P. Pardalos),
Kluwer Academic Publishers, Dordrecht, 2001 (pp.:1624-1634).
G.L. Nemhauser (1985) "Duality for Integer Optimization,"
in: "Combinatorial Optimization: Annotated Bibliographies"
(M. O'hEigeartaigh, J.K. Lenstra, A.H.G. Rinnooy
Kan Eds.), John Wiley & Sons, Chichester, 1985.
C.E. Blair, R.G. Jeroslow (1982) "The value function
of an integer program," Math. Prog.23, 237-273.
http://link.springer.com/article/10.1007%2FBF01583794#page-1
L.A. Wolsey (1981) "Integer programming duality: Price functions
and sensitivity analysis," Math. Prog. 20, 173-195.
other papers:
http://www.math.ucdavis.edu/~latte/theory.php
%%%%%%%%%%%%%%%%%%%%%%%
books:
A. Barvinok (2008) "Integer Points in Polyhedra" Zurich Lect. in Adv.Math., Eu.Math.Soc.
http://libgen.info/view.php?id=615100
J.A. De Loera, R.Hemmecke "Algebraic-Geometric Ideas in Discrete Optimization: An Invitation" A draft 2010:
http://www.math.ucdavis.edu/~deloera/TEACHING/MATH280/NEWMETHODSOPTIMIZATION/280notes.pdf
Lasserre J.B. "Linear and integer programming vs linear integration and counting..
A duality viewpoint" (Springer, 2009). PDF link.
%%%%%%%%%%%%%%%%%%%%%%%
предыстория:
А.И. Барвинок (1990) “Метод сумм Ньютона в задачах комбинаторной
оптимизации”, Дискрет. матем., 2:1, 3-15.
Discrete Mathematics and Applications, 1991, 1:4, 349-363
http://www.mathnet.ru/rus/dm830
А.И. Барвинок (1990) “Метод статистических сумм в задачах
комбинаторной оптимизации" Алгебра и анализ, 2:5, 63-79.
http://www.mathnet.ru/rus/aa206
А.И. Барвинок (1991) “Вычисление экспоненциальных интегралов"
Зап. научн. сем. ЛОМИ, 192, 149-162.
http://www.mathnet.ru/rus/znsl4950
А.И. Барвинок (1991) “Задачи комбинаторной оптимизации, статистические суммы
и представления полной линейной группы" Матем. заметки, 49:1, 3-11.
http://www.mathnet.ru/rus/mzm2860
А.И. Барвинок, А.М. Вершик, Н.Е. Мнёв (1992)
"Топология пространств конфигураций,
выпуклых многогранников, представлений
решеток" Тр. МИАН СССР, 193, 37-41.
http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tm&paperid=1504&option_lang=rus
А.И. Барвинок (1992) “Экспоненциальные интегралы и суммы по выпуклым
многогранникам" Функц. анализ и его прил., 26:2, 64-66.
http://www.mathnet.ru/rus/faa784
А.И. Барвинок (1992) “Статистические суммы в оптимизации и
вычислительных задачах" Алгебра и анализ, 4:1, 3-53.
http://www.mathnet.ru/rus/aa298
related:
A.V. Pukhlikov, A.G. Khovanskii (1992) “The Riemann-Roch theorem for integrals and sums
of quasipolynomials on virtual polytopes”, Algebra i Analiz 4:4, 188-216.
translation in St. Petersburg Mathematical Journal, 4:4 (1993), 789-812. См.:
А. В. Пухликов, А. Г. Хованский (1992) "Теорема Римана-Роха для интегралов и
сумм квазиполиномов по виртуальным многогранникам" Алгебра и анализ, 4:4, 188-216.
http://www.mathnet.ru/rus/aa339
А. В. Пухликов, А. Г. Хованский (1992) "Конечно-аддитивные меры виртуальных
многогранников" Алгебра и анализ, 4:2, 161-185.
http://www.mathnet.ru/rus/aa315
А.Г. Хованский "Многогранники и Алгебра"
http://www.math.toronto.edu/askold/dop-vniisi.pdf
%%%%%%%%%%%%%%%%%%%%%%%
Lectures:
Г.Ю. Панина "Целые точки в выпуклых многогранниках"
http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=1307
Конспекты:
http://club.pdmi.ras.ru/moodle/mod/resource/view.php?id=102
http://club.pdmi.ras.ru/moodle/mod/resource/view.php?id=151
http://club.pdmi.ras.ru/~panina/spezkurs2009.html
Кушниренко А. "Целые точки в многоугольниках и многогранниках" Квант N4, 1977
http://kvant.mccme.ru/1977/04/celye_tochki_v_mnogougolnikah.htm
Васильев Н. "Сложение фигур" Квант N6, 1977
http://kvant.mccme.ru/1976/04/slozhenie_figur.htmA Short Lecture Series on Lattice Points:
http://www.math.ucdavis.edu/~latte/background.php
Software:
http://www.math.ucdavis.edu/~latte/
http://www.math.ucdavis.edu/~latte/software/manual_v1.5.pdf
%%%%%%%%%%%%%%%%%%%%%%%
Additional books:
R.P. Stanley (1986) "Enumerative Combinatorics" Vol.1, Ch.4,
Wadsworth & Brooks/Cole, Monterey, California, 1986.
http://libgen.info/view.php?id=3618
J.A. De Loera, J Rambau, F. Santos "Triangulations: Structures for Algorithms and Applications"
Springer series: Algorithms and Computation in Mathematics, Vol. 25, 2010.
http://www.springer.com/mathematics/geometry/book/978-3-642-12970-4
http://libgen.info/view.php?id=759981
%%%%%%%%%%%%%%%%%%%%%%%
P.S.: О Многоугольниках Ньютона:
Кушниренко А. журнал "Квант" N6,1977
http://kvant.mccme.ru/au/kushnirenko_a.htm
Н.Б.Медведева "Особые точки векторных полей на плоскости"
Соросовский образовательный журнал, 1999, №5, с. 121-127.
http://www.pereplet.ru/nauka/Soros/pdf/9905_121.pdf
Чеботарев Н.Г. 1943 "Многоугольник Ньютона".
http://libgen.info/view.php?id=5194
алгоритмах целочисленного программирования
(integer linear programming, ILP) полиномиальной
сложности в фикс. разм.
См. его статью:
Yu.Nesterov (2004) "Fast Fourier Transform and its
applications to integer knapsack problems"
http://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2004_64.pdf
Отправной точкой является, так называемый
Barvinok’s algorithm. Далее ссылки про него.
A.I.Barvinok (1993) "Computing the volume, counting integral points, and exponential sums"
Discrete Comput. Geom. 10, 123-141. MR 94d:52005
http://www.springerlink.com/content/uh13667243q06665/fulltext.pdf
A.I.Barvinok (1994) “A polynomial time algorithm for counting integral points in polyhedra
when the dimension is fixed”, Math. Oper. Res. 19, 769-779.
http://www.jstor.org/stable/3690312
A.I.Barvinok, J.E.Pommersheim (1999) "An algorithmic theory of lattice points in polyhedra"
In: “New perspectives in algebraic combinatorics”, MSRI Publications, 38, 91 - 147.
http://www.math.lsa.umich.edu/~barvinok/functions.ps
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.170.9496
A.I.Barvinok, K.Woods (2003) "Short rational generating functions for lattice point problems"
http://www.oberlin.edu/math/faculty/woods/research/gf-jams.pdf
A.I. Barvinok (2005) "Computing the Ehrhart quasi-polynomial of a rational simplex"
Mathematics of Computation. http://front.math.ucdavis.edu/0504.5444
M.Brion, M.Vergne (1997) "Residue formulae, vector partition functions and lattice
points in rational polytopes" J. Amer. Math, Soc., 10, 79 -833.
http://reference.kfupm.edu.sa/content/r/e/residue_formulae__vector_partition_funct_56659.pdf
M.Dyer, R.Kannan (1997) "On Barvinok’s algorithm for counting lattice points in fixed dimension"
Math. Oper. Res., 22(3):545-549, 1997.
http://www.jstor.org/stable/3690392
http://mathor.highwire.org/content/22/3/545.short
M.Cryan, M.Dyer, L.A.Goldberg, M.Jerrum, R.Martin (2000) "Rapidly Mixing Markov Chains for
Sampling Contingency Tables with a Constant Number of Rows"
http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Dyer/Dyer5.pdf
B.Chen (2002) "Lattice points, Dedekind sums and Ehrhart polynomials of lattice polyhedra"
Discrete Comput. Geom. 28, 175-199.
http://www.math.ust.hk/~mabfchen/Paper/Lattice-Points-Dedekind.pdf
J.B. Lasserre, E.S. Zeron (2001) "On Counting Integral Points in a Convex Rational Polytope"
Math. of Operat. Res., Vol.28, No.4, pp. 853-870.
https://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Lasserre/lasserrezeroncounting.pdf
J.B. Lasserre, E.S. Zeron (2001) "Solving a class of multivariate integration problems via Laplace techniques"
Appl. Math. (Warsaw), 28, pp. 391-405.
https://www.impan.pl/pl/wydawnictwa/czasopisma-i-serie-wydawnicze/applicationes-mathematicae/all/28/4/84463/solving-a-class-of-multivariate-integration-problems-via-laplace-techniques
J.B. Lasserre, E.S. Zeron (2001) "A Laplace transform algorithm for the volume of a convex polytope" J. ACM 48, 1126-1140.
http://homepages.wmich.edu/~ledyaev/lasserre-vol.pdf
J.B.Lasserre, E.S.Zeron (2002) "Solving the knapsack problem via Z-transform"
Operat. Res. Lett. archive, Vol.30 I.6, Pp.:394-400.
http://www.sciencedirect.com/science/article/pii/S016763770200161X
J.B. Lasserre (2003) "Integer programming, Barvinok’s counting algorithm and
Gomory relaxations" Oper. Res. Letters, 32:133-137, 2003.
http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Lasserre/barvinok.pdf
J.B.Lasserre (2004) "Generating functions and duality for integer programs"
Discrete Optimization 1, 167-187.
http://www.optimization-online.org/DB_FILE/2003/12/786.pdf
J.A. De Loera, D.Haws, R.Hemmecke, P.Huggins, R.Yoshida (2004) "Three kinds of integer
programming algorithms based on barvinok’s rational functions" 10th Int. IPCO Conf. LNCS.
http://www.springerlink.com/content/eq5qkgvxxyquypc3/
M.Köppe (2006) "A primal Barvinok’s algorithm based on irrational decompositions"
http://www.math.ucdavis.edu/~latte/theory/primalBarvinokAlgoBasedOnIrrationalDecompositions.pdf
Yu. Nesterov (2004) "Performance of trigonometric generating functions on some combinatorial problems"
http://www.core.ucl.ac.be/services/psfiles/dp05/dp2005_69.pdf
W.Baldoi-Silva, J.A. De Loera, M.Vergne (2003) "Counting Integer Flows in Networks"
http://www.math.ucdavis.edu/~latte/theory/totalresidue.pdf
K. Aardal, R. Weismantel, L.A. Wolsey (2002) "Non-standard
approaches to integer programming," Discr. Appl. Math. 123, 5-74.
https://www.ima.umn.edu/talks/workshops/10-14-19.2002/aardal/ut6n.pdf
R.R. Thomas (2001) "Algebraic methods in integer programming,"
Encyclopedia of Optimization (eds: C. Floudas and P. Pardalos),
Kluwer Academic Publishers, Dordrecht, 2001 (pp.:1624-1634).
G.L. Nemhauser (1985) "Duality for Integer Optimization,"
in: "Combinatorial Optimization: Annotated Bibliographies"
(M. O'hEigeartaigh, J.K. Lenstra, A.H.G. Rinnooy
Kan Eds.), John Wiley & Sons, Chichester, 1985.
C.E. Blair, R.G. Jeroslow (1982) "The value function
of an integer program," Math. Prog.23, 237-273.
http://link.springer.com/article/10.1007%2FBF01583794#page-1
L.A. Wolsey (1981) "Integer programming duality: Price functions
and sensitivity analysis," Math. Prog. 20, 173-195.
other papers:
http://www.math.ucdavis.edu/~latte/theory.php
%%%%%%%%%%%%%%%%%%%%%%%
books:
A. Barvinok (2008) "Integer Points in Polyhedra" Zurich Lect. in Adv.Math., Eu.Math.Soc.
http://libgen.info/view.php?id=615100
J.A. De Loera, R.Hemmecke "Algebraic-Geometric Ideas in Discrete Optimization: An Invitation" A draft 2010:
http://www.math.ucdavis.edu/~deloera/TEACHING/MATH280/NEWMETHODSOPTIMIZATION/280notes.pdf
Lasserre J.B. "Linear and integer programming vs linear integration and counting..
A duality viewpoint" (Springer, 2009). PDF link.
%%%%%%%%%%%%%%%%%%%%%%%
предыстория:
А.И. Барвинок (1990) “Метод сумм Ньютона в задачах комбинаторной
оптимизации”, Дискрет. матем., 2:1, 3-15.
Discrete Mathematics and Applications, 1991, 1:4, 349-363
http://www.mathnet.ru/rus/dm830
А.И. Барвинок (1990) “Метод статистических сумм в задачах
комбинаторной оптимизации" Алгебра и анализ, 2:5, 63-79.
http://www.mathnet.ru/rus/aa206
А.И. Барвинок (1991) “Вычисление экспоненциальных интегралов"
Зап. научн. сем. ЛОМИ, 192, 149-162.
http://www.mathnet.ru/rus/znsl4950
А.И. Барвинок (1991) “Задачи комбинаторной оптимизации, статистические суммы
и представления полной линейной группы" Матем. заметки, 49:1, 3-11.
http://www.mathnet.ru/rus/mzm2860
А.И. Барвинок, А.М. Вершик, Н.Е. Мнёв (1992)
"Топология пространств конфигураций,
выпуклых многогранников, представлений
решеток" Тр. МИАН СССР, 193, 37-41.
http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tm&paperid=1504&option_lang=rus
А.И. Барвинок (1992) “Экспоненциальные интегралы и суммы по выпуклым
многогранникам" Функц. анализ и его прил., 26:2, 64-66.
http://www.mathnet.ru/rus/faa784
А.И. Барвинок (1992) “Статистические суммы в оптимизации и
вычислительных задачах" Алгебра и анализ, 4:1, 3-53.
http://www.mathnet.ru/rus/aa298
related:
A.V. Pukhlikov, A.G. Khovanskii (1992) “The Riemann-Roch theorem for integrals and sums
of quasipolynomials on virtual polytopes”, Algebra i Analiz 4:4, 188-216.
translation in St. Petersburg Mathematical Journal, 4:4 (1993), 789-812. См.:
А. В. Пухликов, А. Г. Хованский (1992) "Теорема Римана-Роха для интегралов и
сумм квазиполиномов по виртуальным многогранникам" Алгебра и анализ, 4:4, 188-216.
http://www.mathnet.ru/rus/aa339
А. В. Пухликов, А. Г. Хованский (1992) "Конечно-аддитивные меры виртуальных
многогранников" Алгебра и анализ, 4:2, 161-185.
http://www.mathnet.ru/rus/aa315
А.Г. Хованский "Многогранники и Алгебра"
http://www.math.toronto.edu/askold/dop-vniisi.pdf
%%%%%%%%%%%%%%%%%%%%%%%
Lectures:
Г.Ю. Панина "Целые точки в выпуклых многогранниках"
http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=1307
Конспекты:
http://club.pdmi.ras.ru/moodle/mod/resource/view.php?id=102
http://club.pdmi.ras.ru/moodle/mod/resource/view.php?id=151
http://club.pdmi.ras.ru/~panina/spezkurs2009.html
Кушниренко А. "Целые точки в многоугольниках и многогранниках" Квант N4, 1977
http://kvant.mccme.ru/1977/04/celye_tochki_v_mnogougolnikah.htm
Васильев Н. "Сложение фигур" Квант N6, 1977
http://kvant.mccme.ru/1976/04/slozhenie_figur.htmA Short Lecture Series on Lattice Points:
http://www.math.ucdavis.edu/~latte/background.php
Software:
http://www.math.ucdavis.edu/~latte/
http://www.math.ucdavis.edu/~latte/software/manual_v1.5.pdf
%%%%%%%%%%%%%%%%%%%%%%%
Additional books:
R.P. Stanley (1986) "Enumerative Combinatorics" Vol.1, Ch.4,
Wadsworth & Brooks/Cole, Monterey, California, 1986.
http://libgen.info/view.php?id=3618
J.A. De Loera, J Rambau, F. Santos "Triangulations: Structures for Algorithms and Applications"
Springer series: Algorithms and Computation in Mathematics, Vol. 25, 2010.
http://www.springer.com/mathematics/geometry/book/978-3-642-12970-4
http://libgen.info/view.php?id=759981
%%%%%%%%%%%%%%%%%%%%%%%
P.S.: О Многоугольниках Ньютона:
Кушниренко А. журнал "Квант" N6,1977
http://kvant.mccme.ru/au/kushnirenko_a.htm
Н.Б.Медведева "Особые точки векторных полей на плоскости"
Соросовский образовательный журнал, 1999, №5, с. 121-127.
http://www.pereplet.ru/nauka/Soros/pdf/9905_121.pdf
Чеботарев Н.Г. 1943 "Многоугольник Ньютона".
http://libgen.info/view.php?id=5194