Complicated linear programs were difficult to solve until Dr. George Dantzig developed the simplex method. In this week, we first introduce the standard form and the basic solutions of a linear program. With the above ideas, we focus on the simplex method and study how it efficiently solves a linear program. Finally, we discuss some properties of unbounded and infeasible problems, which can help us identify whether a problem has optimal solution.

Integer programming is a special case of linear programming, with some of the variables must only take integer values. In this week, we introduce the concept of linear relaxation and the Branch-and-Bound algorithm for solving integer programs.

In the past two weeks, we discuss the algorithms of solving linear and integer programs, while now we focus on nonlinear programs. In this week, we first review some necessary knowledge such as gradients and Hessians. Second, we introduce gradient descent and Newton’s method to solve nonlinear programs. We also compare these two methods in the end of the lesson.

As the last lesson of this course, we introduce a case of NEC Taiwan, which provides IT and network solutions including cloud computing, AI, IoT etc. Since maintaining all its service hubs is too costly, they plan to rearrange the locations of the hubs and reallocate the number of employees in each hub. An algorithm is included to solve the facility location problem faced by NEC Taiwan.

In the final week, we review the topics that we have learned and give students a summary. Besides, we briefly preview the advanced course to provide future direction of studying.