Into the Unknown
Basic Modeling for Discrete Optimization The University of Melbourne The Chinese University of Hong Kong This is the official course of learning MiniZinc, which is a high-level constraint modelling language that allows you to easily express and solve discrete optimization problems. Learning how to build models could easily become a mind-dumbing task, but fables will…
A typical problem requiring us to select a subset from a set of objects that meets some criteria and optimize some objective functions. This kind of problem is likely to be represented as an array of 0/1 variables, or an array of boolean variables. Or in MiniZinc, we can use set variables. Set Variables Modeling…
MiniZinc allows us to directly describe and solve discrete optimization problems. MiniZinc is a modeling language, you can throw the problem at different solvers. Instead of using a specific solver directly, the benefit of using a modeling language is that the user can try different solvers easily to find the one that works best for…
Scheduling is one of the most fascinating areas of Discrete Optimization. They are beautiful scientifically meanwhile there is a lot of application in practice. Constraint programming has been really successful in this area. The problem you usually deal with is to minimize some project duration, subject to some precedence constraints (say, some task has to…
Mixed Integer Program is a big field. Essentially a mixed integer program is a linear program with m constraints but some of the n variables are integers. The difference between having integer variables or not having integer variable is big. That’s the gap between being polynomial (P) and NP-complete. Having integers is what makes problems…
Invented by聽George Dantzig in 1947, Linear Programming is one of the most fundamental tools in combinatorial optimization. You have two views: the geometrical view and the algebraic view.聽There are beautiful connection between them. This is what a linear program looks like, which is minimizing a linear objective function and is subject to a set of…
Previously we talked about constraint programming, which actually works with partial assignments, we try to extend them, and to prune search space as much as possible. Another method, called local search, is very different. Simply put, local search is moving the configuration from it’s聽current state to a state which is very close to it, i.e….
Constraint Programming is one of the main paradigms to actually tackle optimization problems. The idea is to look at the problem constraints, and try to use constraints to reduce the set of values that each variables can take, and remove the values that can not appear in any solution. Constraint programming can help model problems…
Filling a knapsack is an NP-hard optimization problem, it is widely believed that in the worst case it takes exponential time to solve. One of the targets in optimization, is to try to delay the exponential growth as late as possible, so we can solve the real practical problems. Often it is impossible to find…
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…