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

Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992
Authors: Shevchenko V.N.
Upper bounds on the number of extreme points in integer programming
Abstract:
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.
Keywords:
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,  ,  ННГУ им. Н. И. Лобачевского, факультет вычислительной математики и кибернетики