A First Course in Linear Optimization (2013) | Hacker News Reader

A First Course in Linear Optimization (2013)

umich.app.box.com

53 pointskneth12 comments

Linear optimization is a subject that is often neglected in computer science curriculums, even at the graduate level. It is common for computer science students to learn algorithms such as hill climbing or even stochastic local search algorithms such as simulated annealing, but in fact there are many applications for which linear optimization methods can solve the same problems better in a small fraction of the time. If you are a computer scientist or a software engineer with an interest in mathematical optimization, linear and integer programming are must-have tools to round out your knowledge base.

A great way to get started is to play around with the solver feature in Excel. Many software engineers may be loath to use this tool, but Excel actually provides a great GUI with which to do simple linear and integer programming problems.

I would make a stronger statement: numerical algorithms (computational continuous mathematics) are seriously neglected in favor of combinatorial algorithms (computational discrete mathematics).

Take any undergrad algorithms class: 99% of it is combinatorial. There's an equal (probably larger) parallel universe of numerical thinking and numerical algorithms which is either not taught, or taught as a secondary class under the names of 'numerical analysis', 'scientific computing', and so on. None of stacks, queues, trees, and graphs are going to help you out when you have to discretize a differential equation or solve the resulting linear system with correctly enforcing the boundary conditions. You could ace an algorithms class and not have a clue how to begin tackling those kinds of problems.

This is especially relevant today when machine learning is heavily dependent on computational linear algebra and other numerics, and a typical CS student is not trained for that.

> a typical CS student is not trained for that.

And what about a typical CS prof? No, I won't name any names, not today.

Interesting. I agree, though linear programming does get a spot almost all the way back in "Introduction to Algorithms", which I believe is a pretty common standard text for CS students (one of the authors is an IEOR professor at Columbia). My guess is that most algorithms courses don't make it all that far back. I wasn't a CS student - I was a math major and did an MS in IEOR, and I was a little surprised to see this topic at the end of this book when I was doing some self-study in algorithms. It seems very different, and I hadn't thought of it as an algorithm before, but of course it is, just one that is heavily based on linear algebra.

LP and NLP do seem to be treated as a niche subject, something that would be taught in an Industrial Engineering (or barring that, a math) class rather than as a core CS topic.

Interesting that you mentioned excel - I agree that this is a good way to learn and play around with LP, but normally I'd have a good python library to point to. I used a python library a while back to do some homework problems, and I wouldn't' be surprised if it has improved considerably since then. Still, interesting that LP and NLP aren't part of scikit-learn (http://scikit-learn.org), which covers classification, regression, clustering, dimensionality reduction, model selection, and preprocessing, but not optimization per se, even though non-linear optimization is a key bit of mathematics behind many of these algorithms (regression that uses a cost function almost certainly uses some kind of NLP, right?). It really is notable that LP is not part of the main packages, front and center.

If you go on kaggle or other data science sites, linear and non-linear optimization don't seem to get much attention, either. Wonder why that is. Anyway, interesting topic.

I believe that the optimize package within Scipy has a linear programming feature (http://docs.scipy.org/doc/scipy/reference/optimize.html), although I have never used it because I have found the documentation lacking.

However, for Python I would actually recommend the PuLP package (http://pythonhosted.org/PuLP/), which has pretty good documentation and let's you use various solvers (CBC, GLPK, CPLEX, Gurobi, etc.) on the backend. This package definitely has it's advantages over Excel, especially for large or complex LP problems where I have found Excel to be much slower and/or incapable of finding as food of a solution. However, for someone learning about LP (linear programming) or integer programming, it's unlikely that they will be doing anything that can't be done efficiently enough in Excel, particularly with an add-on such as OpenSolver. I think that Excel is just easier to use than any of the Python packages that I've come across for this (hopefully that will change though!). But once someone knows what they're doing, learning how to use something such as PuLP can be very valuable in my opinion.

We in cs theory are constantly emphasizing the universal nature of LPs and their generalizations :)

If you are interested in the above text, this textbook might also be of interest: Applied Mathematical Programming by Bradley, Hax, and Magnanti for MIT's Introduction to Optimization. (15.053). Not as code heavy, but still enlightening.

http://web.mit.edu/15.053/www/

I studied Industrial Engineering & Operations Research in undergrad and grad school. Optimization and mathematical modeling has been helpful in consulting, problem-solving, business and programming. I highly recommend taking a deep dive into this subject.

Call me a snob, but after reading too many beautifully typeset LaTeX books/papers, trying to reading math in fonts like this is very off putting.

It is written in LaTeX. It even says so in the first few pages.

From the dedication: For students (even Ohio students). Not for publishers — not this time. Maybe next time.

He has one of the best backgrounds -- Cornell, Nemhauser, Bland, etc.

Reply on news.ycombinator.com