**Translations of Mathematical Monographs**

1997;
146 pp;
Hardcover

MSC: Primary 90;
Secondary 68

**Print ISBN: 978-0-8218-0535-0
Product Code: MMONO/156**

List Price: $87.00

AMS Member Price: $69.60

MAA Member Price: $78.30

**Electronic ISBN: 978-1-4704-4571-3
Product Code: MMONO/156.E**

List Price: $82.00

AMS Member Price: $65.60

MAA Member Price: $73.80

# Qualitative Topics in Integer Linear Programming

Share this page
*V. N. Shevchenko*

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.

#### Readership

Graduate students studying cybernetics and information science and applied mathematicians interested in the theory and applications of discrete optimization.

#### Reviews & Endorsements

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

-- Mathematical Reviews

#### Table of Contents

# Table of Contents

## Qualitative Topics in Integer Linear Programming

- Cover Cover11
- Title page v6
- Contents vii8
- Notation ix10
- Foreword xi12
- Chapter 1. Intersection of a convex polyhedral cone with the integer lattice 116
- Chapter 2. A discrete analogue of the Farkas theorem, and the problem of aggregation of a system of linear integer equations 2540
- Chapter 3. Intersection of a convex polyhedral set with the integer lattice 3550
- Chapter 4. Cut methods in integer programming 6176
- Chapter 5. Complexity questions in integer linear programming 7994
- Appendix 1. Solution of systems of linear equations and congruences in integers 97112
- Appendix 2. Examples of applied problems related to the topic of the book 101116
- Appendix 3. Investigation of minor and permanent characteristics of certain Boolean matrices 109124
- Appendix 4. Threshold functions of many-valued logic and their deciphering 125140
- Bibliography 133148
- Back Cover Back Cover1162