Into the Unknown
Operations Research (3): Theory National Taiwan University What a long journey, but totally worth it! The theory taught in this course is critical, beautiful, powerful. Whatever fields or industry you are in, statistics, machine learning, economics, logistics, etc. This course definitely will help you consolidate the foundation for all skills you need to be professional….
The theory of Operations Research has been used to develop models in many fields like statistics and machine learning. Linear Regression We try to find 伪 and 尾 such that a line g = 伪 + 尾 x to minimize the sum of squared errors for all the data points: Despite the word linear in…
In the case of unconstrained non-linear programs, we may determine whether the objective function is convex and then use the first order condition (FOC) to find all local minima. However in practice, most of the time, nonlinear programs are constrained. We can not simply ignore those constraints treating the program as an unconstrained, and then…
Compared with linear programs, non-linear programs (NLPs) are much more difficult to solve. In an NLP, a local minimum is not always a global minimum. A greedy search method like gradient decent may be trapped at a local minimum. Also even the NLP has optimal solutions, these optimal solutions may exist on a boundary, but…
Network flow models are one specific format of mathematical programs. These are used to study operations that are related to network transportation. A unified model, called Minimum Cost Network Flow (MCNF) covers many network operations. MCNF is a special form of linear program or integer program. Even better, MCNF has a very nice property: once…
Previously, we mentioned that an sensitivity analysis tool called Shadow Price is helpful to evaluate the impact of change when right hand side value of a constraint is increased by 1. However in some cases, there might be new variables or new constraints added, the good news is you don’t have to solve the problem…
When you are given a linear program, in many cases we call it a primal linear program. It is usually going to be able to find another program, called a dual linear program. The primary reason why we want to use duality is that the computation time of the simplex method is roughly proportional to…
When it comes to Operations Research, we are mainly talking about optimization problems, so the theories are mainly optimality conditions. They basically mean for an optimization problem, somehow there should be an optimal solution. We want to get the conditions which will make the optimal solution satisfy. Typically we search for the necessary conditions, while…
Operations Research (2): Optimization AlgorithmsNational Taiwan University You probably have used some solver / optimizer software to solve problems, this wonderful course will show you what is under the hood. Being able to comprehend what has happened is crucial to customize the algorithms or even to develop your own ones. There is a warm-up at…
The objectives for any research is that we want to build a mathematical model to formulate the given problem. The heart of operations research is a mathematical model. That model is going to precisely describe the problem, but the model may be too complicated to get an optimal solution. We need heuristic algorithms, and the model could be…
Non-Linear Programs When visualizing a linear program, its feasible region looks like a polygon. Because the objective function is also linear, the optimal solution is on the boundary or corner of the region. But a non-linear program is quite different, its feasible region may be in any shape, moreover the optimal solution may not exist…
In some cases, variables must take integer values, or binary values. Formulating and solving the models with integer variables is integer programming. There are mainly 2 methods to solve it: The branch-and-bound algorithm finds an optimal solution for an integer program. Essentially, it decomposes the integer program into multiple linear programs, then solves all of…
The simplex method is the most fundamental tool in linear programming, it is a single algorithm that is able to solve any kinds of linear program regardless of its format, number of variables and constraints. We firstly transform the linear program to a standard form, then we focus on the standard form. The idea of…
There are 2 perspectives to look at linear equation systems, row view and column view. Both are equivalent, sometimes row view is more intuitive, sometimes column view is easier to understand. Linear Equations (n = 2) By row Each equation represents a straight line on the x-y plane.The intersection is the only point on both…
Operations Research (1): Models and ApplicationsNational Taiwan University This is an amazing beginner-level course about Operations Research (abbr. OR). Simply put, it is all about optimization and decision-making. It is deep-rooted in math, but its emphasis on practical applications makes OR even more beautiful. Firstly, the course introduces basic concepts, then 3 fundamental models are…