Premium
Upper and lower bound results on the convex hull of integer points in polyhedra
Author(s) -
Morgan D. A.
Publication year - 1991
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579300006665
Subject(s) - mathematics , combinatorics , convex hull , polyhedron , upper and lower bounds , knapsack problem , polytope , integer points in convex polyhedra , convex polytope , integer (computer science) , integer programming , regular polygon , linear programming , linear inequality , hull , discrete mathematics , convex set , inequality , convex optimization , branch and price , mathematical optimization , geometry , mathematical analysis , marine engineering , computer science , engineering , programming language
In typical linear programming problems, we are concerned with finding non‐negative integers {x 1 ,…, x n } that maximize a linear form c 1 x 1 + … + c n x n , subject to a number of linear inequalities,a 1 jx 1 + … + a n jx n ⩽ L , for 1 ⩽ j ⩽ r . The maximum is necessarily attained at one of the vertices of the convex hull of integer points defined by the inequalities, so we have an interest in estimating the number M of these vertices. We give two results; one improving an upper bound result for M of Hayes and Larman concerning the Knapsack polytope, the other an example showing that, in 3‐dimensions, it is possible to choose the coefficients a ij to obtain a lower bound for M .