KIAM Main page Web Library  •  Publication Searh  Русский 

Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992
Authors: Shevchenko V.N.
Upper bounds on the number of extreme points in integer programming
The article applies an approach, which was previously used by the author, to evaluate the number of extreme points in the convex hull of a set M of integer solutions for a system of linear equations. We consider the properties of extreme points for the case when M is defined by a system of linear equations and congruences, and we obtain various bounds on their number. The same is performed for a set M defined by a system of linear inequalities. For a fixed dimension value the bounds are polynomial and do not depend on the right-hand side of the systems that define M. We also show how similar problems may be treated for a partially integer case.
integer programming, convex hull, linear equation system, linear inequality system, extreme points
Publication language: russian,  pages: 8 (p. 65-72)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Shevchenko Valerii Nikolaevich,  ,  ННГУ им. Н. И. Лобачевского, факультет вычислительной математики и кибернетики