Hardcover ISBN:  9780821805350 
Product Code:  MMONO/156 
List Price:  $87.00 
MAA Member Price:  $78.30 
AMS Member Price:  $69.60 
Electronic ISBN:  9781470445713 
Product Code:  MMONO/156.E 
List Price:  $82.00 
MAA Member Price:  $73.80 
AMS Member Price:  $65.60 

Book DetailsTranslations of Mathematical MonographsVolume: 156; 1997; 146 ppMSC: Primary 90; Secondary 68;
Integer solutions for systems of linear inequalities, equations, and congruences are considered along with the construction and theoretical analysis of integer programming algorithms. The complexity of algorithms is analyzed dependent upon two parameters: the dimension, and the maximal modulus of the coefficients describing the conditions of the problem. The analysis is based on a thorough treatment of the qualitative and quantitative aspects of integer programming, in particular on bounds obtained by the author for the number of extreme points. This permits progress in many cases in which the traditional approach—which regards complexity as a function only of the length of the input—leads to a negative result.
ReadershipGraduate students studying cybernetics and information science and applied mathematicians interested in the theory and applications of discrete optimization.

Table of Contents

Chapters

Chapter 1. Intersection of a convex polyhedral cone with the integer lattice

Chapter 2. A discrete analogue of the Farkas theorem, and the problem of aggregation of a system of linear integer equations

Chapter 3. Intersection of a convex polyhedral set with the integer lattice

Chapter 4. Cut methods in integer programming

Chapter 5. Complexity questions in integer linear programming

Appendix 1. Solution of systems of linear equations and congruences in integers

Appendix 2. Examples of applied problems related to the topic of the book

Appendix 3. Investigation of minor and permanent characteristics of certain Boolean matrices

Appendix 4. Threshold functions of manyvalued logic and their deciphering


Reviews

Of interest … references many papers in Russian that are largely unavailable outside (and, sometimes, inside) Russia.
Mathematical Reviews


Request Review Copy

Get Permissions
 Book Details
 Table of Contents
 Reviews

 Request Review Copy
 Get Permissions
Integer solutions for systems of linear inequalities, equations, and congruences are considered along with the construction and theoretical analysis of integer programming algorithms. The complexity of algorithms is analyzed dependent upon two parameters: the dimension, and the maximal modulus of the coefficients describing the conditions of the problem. The analysis is based on a thorough treatment of the qualitative and quantitative aspects of integer programming, in particular on bounds obtained by the author for the number of extreme points. This permits progress in many cases in which the traditional approach—which regards complexity as a function only of the length of the input—leads to a negative result.
Graduate students studying cybernetics and information science and applied mathematicians interested in the theory and applications of discrete optimization.

Chapters

Chapter 1. Intersection of a convex polyhedral cone with the integer lattice

Chapter 2. A discrete analogue of the Farkas theorem, and the problem of aggregation of a system of linear integer equations

Chapter 3. Intersection of a convex polyhedral set with the integer lattice

Chapter 4. Cut methods in integer programming

Chapter 5. Complexity questions in integer linear programming

Appendix 1. Solution of systems of linear equations and congruences in integers

Appendix 2. Examples of applied problems related to the topic of the book

Appendix 3. Investigation of minor and permanent characteristics of certain Boolean matrices

Appendix 4. Threshold functions of manyvalued logic and their deciphering

Of interest … references many papers in Russian that are largely unavailable outside (and, sometimes, inside) Russia.
Mathematical Reviews