Introduction to Linear Optimization

What Hacker News says

1. stnclsJul 2021
   For linear programming I much preferred the Bertsimas/Tsitsiklis (Introduction to Linear Optimization). Not free, but if you look at the first couple Google result you may get nice surprises.
   thread
2. merrakshJun 2016
   the optimum is always at a vertex

   As you point out in [2], it would be more correct to say that among the optimal solutions there is always one at a vertex of the polyhedron</nitpicking>

   Also, simplex methods are very versatile when combined with other methods (see branch-and-bound for mixed integer linear optimization), but are sometimes easily beaten by barrier methods.

   Excellent textbooks for LP: Chvátal [4] and Bertsimas and Tsitsiklis [5]. For mixed integer linear optimization: Wolsey [6], Nemhauser and Wolsey [7], and Conforti et al. [8].

   [4] V. Chvátal, Linear Programming. MacMillan 1983.

   [5] D. Bertsimas, J.N. Tsitsiklis. Introduction to linear optimization. Vol. 6. Belmont, MA: Athena Scientific, 1997.

   [6] L.A. Wolsey (1998). Integer programming (Vol. 42). New York: Wiley.

   [7] L.A. Wolsey, G.L. Nemhauser. Integer and combinatorial optimization. John Wiley & Sons; 2014 Aug 28.

   [8] M. Conforti, G. Cornuéjols, G. Zambelli (2014). Integer programming (Vol. 271). Berlin: Springer.

   Show morethread
3. justokayJan 2010
   Mike Jordan at Berkeley sent me his list on what people should learn for ML. The list is definitely on the more rigorous side (ie aimed at more researchers than practitioners), but going through these books (along with the requisite programming experience) is a useful, if not painful, exercise.

   I personally think that everyone in machine learning should be (completely) familiar with essentially all of the material in the following intermediate-level statistics book:

   1.) Casella, G. and Berger, R.L. (2001). "Statistical Inference" Duxbury Press.

   For a slightly more advanced book that's quite clear on mathematical techniques, the following book is quite good:

   2.) Ferguson, T. (1996). "A Course in Large Sample Theory" Chapman & Hall/CRC.

   You'll need to learn something about asymptotics at some point, and a good starting place is:

   3.) Lehmann, E. (2004). "Elements of Large-Sample Theory" Springer.

   Those are all frequentist books. You should also read something Bayesian:

   4.) Gelman, A. et al. (2003). "Bayesian Data Analysis" Chapman & Hall/CRC.

   and you should start to read about Bayesian computation:

   5.) Robert, C. and Casella, G. (2005). "Monte Carlo Statistical Methods" Springer.

   On the probability front, a good intermediate text is:

   6.) Grimmett, G. and Stirzaker, D. (2001). "Probability and Random Processes" Oxford.

   At a more advanced level, a very good text is the following:

   7.) Pollard, D. (2001). "A User's Guide to Measure Theoretic Probability" Cambridge.

   The standard advanced textbook is Durrett, R. (2005). "Probability: Theory and Examples" Duxbury.

   Machine learning research also reposes on optimization theory. A good starting book on linear optimization that will prepare you for convex optimization:

   8.) Bertsimas, D. and Tsitsiklis, J. (1997). "Introduction to Linear Optimization" Athena.

   And then you can graduate to:

   9.) Boyd, S. and Vandenberghe, L. (2004). "Convex Optimization" Cambridge.

   Getting a full understanding of algorithmic linear algebra is also important. At some point you should feel familiar with most of the material in

   10.) Golub, G., and Van Loan, C. (1996). "Matrix Computations" Johns Hopkins.

   It's good to know some information theory. The classic is:

   11.) Cover, T. and Thomas, J. "Elements of Information Theory" Wiley.

   Finally, if you want to start to learn some more abstract math, you might want to start to learn some functional analysis (if you haven't already). Functional analysis is essentially linear algebra in infinite dimensions, and it's necessary for kernel methods, for nonparametric Bayesian methods, and for various other topics. Here's a book that I find very readable:

   12.) Kreyszig, E. (1989). "Introductory Functional Analysis with Applications" Wiley.

   Show morethread
4. antmanJun 2013
   Here is the instructor Pascal Van Hentenryck answer from the coursera forums:

   "Thanks for pointing this out.

   First, we obviously cover linear programming and mixed-integer programming in this course. These techniques are indeed very successful in practice and I hope that you will also enjoy these lectures. They make up a third of the class. The references

       Integer Programming by Laurence A. Wolsey
       Integer and Combinatorial Optimization by Laurence A. Wolsey, George L. Nemhauser
       Large Scale Linear and Integer Optimization: A Unified Approach by Richard Kipp Martin
       Introduction to Linear Optimization by Dimitris Bertsimas, John N. Tsitsiklis
       Understanding and Using Linear Programming by Jiri Matousek, Bernd Gärtner
       Theory of Linear and Integer Programming by Alexander Schrijver
   

   are also provided in the additional material. The work mentioned in the introductory lectures include many applications that are based on mixed-integer programming. So I am not sure where this person is coming from with her/his comment.

   This being said, constraint programming and local search are also very successful in practice, often for different types of problems. So this class aims at giving an introduction to a subset of the techniques that are successful in practice (there are other too) as an introduction to the field. My research group uses all three of these techniques to solve large-scale problems in logistics and supply-chains, energy, and disaster management. Some of the problems we solve require the three approaches together to achieve high-quality solutions. To paraphrase John von Neumann defending George Dantzig: "If this technique applies to your problem, use it; otherwise do not".

   We also cover column generation and large neighborhood search in the advanced topics. I used to cover Lagrangian relaxation in my class at Brown and we may add a lecture on this. This class has almost all the material of my optimization class at Brown University but not all, since it is a shorter. We may still add an advanced lecture on this topic (I have an additional motivation now)

   With respect to the job market, I would simply say: Go to the Informs conference and see how many people, both from academia, industry, and government, are recruiting. Companies such Google, IBM, Amazon, ... have outstanding groups in optimization. Follow Mike Trick's blog and tweeter accounts to get a sense of how lively this community is (see the community link on the page). I never had a student not find a job and most of them did not go to academia. One of them actually works for ... Fedex. My sense is that the opportunities for optimization keep growing and it is an exciting time for optimization. There are many startups, established companies, large multi-national organizations all doing optimization. Some focus on solvers, some on vertical products, some on dedicated applications, and some of several or all of these aspects. The field has progressed significantly.

   There is a lot of work, and a lot of progress, in making optimization more reusable and the tools/solvers are now much better in being more generic. Unless P=NP, this will always be a challenge but there are more generic tools to solve classes of applications. There are also solvers that provide a lot more flexibility to build dedicated algorithms much more simply. Many people (including me) spent their research and academic careers trying to design such tools and some make a significant difference in practice.

   Finally, optimization is a multi-disciplinary field. My group employs mathematicians, physicists, engineers, and computer scientists. What I personally find incredibly stimulating in this area right now, is that sometimes you need a physicist, a mathematician, and a computer scientist together to solve a complex problem. We all look at a problem from different angles and there is tremendous values in that. I am part of the INFORMS, artificial intelligence, and computer science communities, and some of the scientific contributions I am most proud of are typically those when I was able to bridge two fields. Many of the techniques in optimization come from a variety of fields and this is also what makes it exciting.

   And, yes, I am exciting about the future of optimization,

   I hope it helps."

   Show morethread