PhD-level textbooks on linear programming

Question

My graduate Linear Programming class uses Bertsimas & Tsitsiklis's Introduction to Linear Optimization. Are there any alternative texts that I could use to supplement this textbook (mainly the content of Chapter 2 of Bertsimas & Tsitsiklis: extreme point, vertex, basic feasible solution, contains/does not a line, Fourier-Motzkin) at the same level rigor and which contain exercises that I could practice on?

Ideally, I would also like a book with a decent (the more the better) number of pictures that gives geometric intuition behind proofs.

You can also checkout a relevant INFORMS open forum question here: https://connect.informs.org/communities/community-home/digestviewer/viewthread?MessageKey=fc88c066-c1d1-4a4d-90cf-a90762c188d9&CommunityKey=1d5653fa-85c8-46b3-8176-869b140e5e3c&tab=digestviewer — Josh Allen, Oct 13 '19 at 21:09

score 12 · Answer 1 · answered Oct 05 '19 at 16:17

12

A classic textbook that does a really good job of building from the fundamentals is Theory of Linear and Integer Programming by Schrijver. Chapter 7 in particular gives great intuition on linear programming.

These lecture notes by Ryan O'Donnell and Anupam Gupta are also a good, quicker reference as well as the textbook they refer to, Understanding and Using Linear Programming by Matoušek and Gärtner.

answered Oct 05 '19 at 16:17

ydubey7

579
2
9

thanks @ydubey7. i think perhaps schrijver is a bit more high level than bertsimas. I really like gartner although i don't believe there's any exercises. are there any books similar to bertsimas chapter 2 with exercises I can practice on. – tiger123 Oct 05 '19 at 23:25

score 9 · Answer 2 · edited Oct 17 '19 at 07:47

9

I used to study with the following book:

Chvatal, V. (1983). Linear programming.

Overall it's very clear. It's written primary for graduate courses in operations research, math and computer science. Chapter 17: Connections with Geometry, may give some geometric intuitions.

I hope it helps you.

edited Oct 17 '19 at 07:47

Marco Lübbecke

5,919
22
64

answered Oct 08 '19 at 18:46

Agus Montero

309
1
4

score 8 · Answer 3 · answered Oct 08 '19 at 14:43

G.B. Dantzig and M.N. Thapa Linear Programming 1: Introduction, Springer, 1997 and Linear Programming 2: Theory and Extensions, Spinger, 2003.

Linear Programming 2, Theory and Extensions, is the one with the hard-core theoretical Linear Programming Ph.D. material which you seem to want. Among other things, it contains some of the old Stanford O.R. Ph.D. comprehensive exam questions in Linear Programming - you won't find that in any other book.

score 7 · Answer 4 · answered Oct 05 '19 at 01:59

7

There are some good problems in Linear Optimization: Theory and Extensions by Fang and Puthenputra. Chapter 2 of the book ("Geometry of Linear Programming") is most comparable to Chapter 2 of Bertsimas.

Also see this related question on Math.SE: https://math.stackexchange.com/q/20643/669798

answered Oct 05 '19 at 01:59

dxb

1,799
2
12
32

thanks, ill check it out. – tiger123 Oct 05 '19 at 02:10

PhD-level textbooks on linear programming

4 Answers4