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…