Integer Programming

H. Paul Williams ()
Additional contact information
H. Paul Williams: The London School of Economics

Chapter Chapter 2 in Logic and Integer Programming, 2009, pp 25-70 from Springer

Abstract: In this chapter we begin with a brief explanation of linear programming (LP) since integer programming (IP) is usually regarded as an extension of LP. Also most practical methods of solving IP models rely on solving an LP model first. However, our discussion of LP will be brief since this is not the main theme of this book. Although LP models are often solved in the course of solving IP models we will, in the main, regard a method of solving LP models in this context as a ‘black box’. However, we will give a (computationally inefficient) method of solving LP models which illustrates the use of the predicate calculus as discussed in Sect. 1.5 as well as demonstrating important properties of LP models which are relevant to IP. In Sect. 2.4 we discuss the comparative computational complexity of IP comparedwith LP. A list of references to the further study of LP is given in Sect. 2.5.

Keywords: Convex Hull; Integer Programming; Feasible Region; Travel Salesman Problem; Knapsack Problem (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-0-387-92280-5_2

Ordering information: This item can be ordered from
http://www.springer.com/9780387922805

DOI: 10.1007/978-0-387-92280-5_2

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().