26
$\begingroup$

Do you know of a good book on linear programming? To be more specific, i am taking linear optimization class and my textbook sucks. Teacher is not too involved in this class so can't get too much help from him either, Any help will be appreciated. Thank you

$\endgroup$
  • $\begingroup$ Are there books / textbooks on Linear Programming with R? I did a quick Amazon search but could not find any (at least from the book titles). I am aware of CRAN reference manuals for packages like lpSolve, lpSolveAPI, Rglpk, glpkAPI but there are not exactly books. $\endgroup$ – dwstu Dec 30 '13 at 2:41
  • $\begingroup$ I have to thank you for this thread. I'm in the same position you were: my teacher isn't really involved in this class and my textbook sucks. $\endgroup$ – Victor S. Sep 21 '18 at 2:11
18
$\begingroup$

The other classics besides Winston are Hillier and Lieberman's Introduction to Operations Research and Chvátal's Linear Programmming. I learned linear programming out of Bob Vanderbei's Linear Programming: Foundations and Extensions, which is also a fine book. The last time I taught linear programming I used Dave Rader's new book, Deterministic Operations Research, and was happy with it.

As for a comparison, Winston focuses on how the different methods work and gives lots of examples but doesn't spend much time on theory. Hillier and Lieberman is at a slightly higher level than Winston, with a more leisurely pace and a little more theory but with fewer examples. Chvátal and Vanderbei have a more noticeable focus on the theory. Rader takes a different approach in that the simplex method does not appear until about halfway through the book. Instead, he spends a lot of time early on algorithm design and on what an algorithm for solving linear programs might look like so that when you finally do see the simplex method the reaction is closer to "Of course" than to "Where in the world did that come from?" He doesn't do the tableau form of the simplex method, which, while a plus in my opinion, may make it hard to understand his version of the simplex method if you're used to the tableau.

Many LP books spend little time on how to construct linear programming models (i.e, how to come up with variables, an objective function, and constraints that describe the problem you're trying to solve). Of these five, Winston and Rader discuss construction of LP models the most.

$\endgroup$
  • 3
    $\begingroup$ Some introductory material is avialable in Linear Algebra and Its Applications by Gilbert Strang. $\endgroup$ – 911 Feb 6 '11 at 11:23
7
$\begingroup$

I recommend Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis. The authors are professors at MIT.

Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis

$\endgroup$
  • $\begingroup$ Chapter 8 of Linear Algebra and its Applications (4th edition) on linear programming and game theory is a concise and clear introduction to the simplex method and it also contains a short description of Karmakar's interior-point method. $\endgroup$ – dwstu Oct 26 '12 at 9:12
6
$\begingroup$

I feel like I have to mention Schrijver's "Theory of Linear and Integer Programming" as it is a classic, but I don't feel like it is the best text for an introduction or for application.

$\endgroup$
3
$\begingroup$

There are many books. A cheap one that is also very good is Combinatorial Optimization: Algorithms and Complexity by Papadimitriou and Steiglitz.

$\endgroup$
2
$\begingroup$

This(Operations Research: Applications and Algorithms by Winston) is a good book. I learned linear optimization techniques from this book(e.g. the simplex method, assignment problems, etc..).

$\endgroup$
2
$\begingroup$

Linear Programming : An Introduction To Finite Improvement Algorithms by Daniel Solow. It is also a good introduction to the theme. Appendix discusses about the other algorithms. His book develops proof aspect systematically.

$\endgroup$
1
$\begingroup$

I'm taking a class that uses Linear Programming with Matlab, but it's really hard to read. I got Linear Programming: Methods and Applications to supplement it and it's much more readable. It's targeted at undergraduates, I guess. It has a lot of proofs, but most of the text is explanatory.

$\endgroup$
0
$\begingroup$

I can recommend two books not mentioned here.

First is Understanding and Using Linear Programming by Jiri Matousek and Bernd Gärtner.

Here you find basic intro into geometry, simplex method, duality and interior point method with proofs.

Second is Combinatorial Optimization by Cook, Cunningham, Pulleyblank, Schrijver.

This is more a books of application ( with proofs ) full of algorithms using linear and integer programming, duality, also unimodularity, Chvatal-Gomory cuts and solving TSP with various methods. Both books are complementary ;) I recommend starting with first one and read few chapters of Combinatorial Optimization to get another look at things.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.