It’s time talk more about barrier in class

In today’s post, I argue that optimization classes and textbooks should put a greater emphasis on interior point methods.

During my many years of study, I have been exposed to quite a bit of simplex theory. I also had to perform many primal and dual simplex pivots by hand, as it was considered a good way to understand how the algorithm works. The teaching was quite in line with the classical textbook used by our school, the Winston and Venkataramanan. I remember it was mentioned that “other methods exist, some of which are polynomial time”, but that in practice the simplex was more used. It wasn’t until I got to start working with mixed-integer programming solvers that I was exposed to interior-point methods, and then I had to do quite a bit of reading to understand what it was all about.

Nowadays, interior point methods are often the most powerful for solving many linear programming models. Many LP models just couldn’t be solved efficiently if it wasn’t for this class of algorithms. For instance, over the last weeks I had to solve a set of about 60 relatively large linear programming models (1.5 million variables and about 500k constraints). These models were quite effectively handled by the solver we used (in this case it was CPLEX, but some earlier tests revealed that Gurobi did just as good). It took between 60 and 90 minutes to solve each one of these models. Just out of curiosity, I forced the solver to solve the same model using the dual simplex, and it was still running after 3 days. If it wasn’t for barrier, we would have needed to drastically reduce our model size in order to be able to do anything in this project.

Many syllabus I have read on linear programming courses spend a large amount of time on both primal and dual simplex, and either cover interior point methods in 3 hours at the end of the semester or don’t cover it at all. This is especially true in business schools. Students in analytics and business intelligence get very little exposure to the algorithms that are embedded in the tools they use daily and they might only have one class who focuses linear and integer programming. I think it’s time to split class time more fairly between simplex and interior point methods.

If you are interested in the topic of what optimization algorithms should be taught in optimization classes, I recommend you read Bob Fourer’s excellent post on which simplex methods to teach to engineers and computer scientists.

Comments

  1. Do you have any recommended resources for teaching barrier methods to undergrads in engineering?

  2. I wrote up some notes to introduce barrier (interior-point) methods: http://www.4er.org/CourseNotes/Book%20B/B-III.pdf. They use only elementary math but still the subject may be more appropriate to first-year graduate students. Some slides based on these notes are at https://www.dropbox.com/s/eobqe19mddz3w36/Interior-Point%20Methods.pdf?dl=0. Also I collected comparisons of simplex and barrier method performance under various options which you can see at https://www.dropbox.com/s/671wcwv89ihlhr7/Iteration%20Counts%20NEW.xls?dl=0.

Speak Your Mind

*