Combinatorial optimization is about picking one element of a set of finite objects that optimizes an objective function. Put in this way, the solution may seem straightforward: just enumerate all elements of the set and assess the objective function for each object.
The problem with this naïve approach is that the number of elements of the set can be very large. Let's consider, for instance, the symmetric travelling salesperson problem. For an instance of n nodes, the number of possible solutions is the factorial of (n-1) divided by two. This means that, for a problem of size n=20, and taking one millisecond to assess each solution, it takes around 1,108,606 years to assess all solutions. This effect is called combinatorial explosion.
This video shows an example of an even faster combinatorial explosion. Additionally, helps in learning how to count large numbers in Japanese...
sábado, 19 de septiembre de 2015
viernes, 11 de septiembre de 2015
Modeling and Solving Linear Programming with R
Citation
Sallan, Jose M.; Lordan, Oriol; Fernandez, Vicenc (2015). Modeling and Solving Linear Programming with R. Omniascience.
Abstract
Linear programming is one of the most extensively used techniques in the toolbox of quantitative methods of optimization. One of the reasons of the popularity of linear programming is that it allows to model a large variety of situations with a simple framework. Furthermore, a linear program is relatively easy to solve. The simplex method allows to solve most linear programs efficiently, and the Karmarkar interior-point method allows a more efficient solving of some kinds of linear programming. The power of linear programming is greatly enhanced when came the opportunity of solving integer and mixed integer linear programming. In these models all or some of the decision variables are integers, respectively.
In this book we provide a brief introduction to linear programming, together with a set of exercises that introduce some applications of linear programming. We will also provide an introduction to solve linear programming in R. For each problem a possible solution through linear programming is introduced, together with the code to solve it in R and its numerical solution.
Availability
Please see Omniascience website for details, and the repository containing the code used in the book.
Also available through UPCommons in this direction.
Sallan, Jose M.; Lordan, Oriol; Fernandez, Vicenc (2015). Modeling and Solving Linear Programming with R. Omniascience.
Abstract
Linear programming is one of the most extensively used techniques in the toolbox of quantitative methods of optimization. One of the reasons of the popularity of linear programming is that it allows to model a large variety of situations with a simple framework. Furthermore, a linear program is relatively easy to solve. The simplex method allows to solve most linear programs efficiently, and the Karmarkar interior-point method allows a more efficient solving of some kinds of linear programming. The power of linear programming is greatly enhanced when came the opportunity of solving integer and mixed integer linear programming. In these models all or some of the decision variables are integers, respectively.
In this book we provide a brief introduction to linear programming, together with a set of exercises that introduce some applications of linear programming. We will also provide an introduction to solve linear programming in R. For each problem a possible solution through linear programming is introduced, together with the code to solve it in R and its numerical solution.
Availability
Please see Omniascience website for details, and the repository containing the code used in the book.
Also available through UPCommons in this direction.
Suscribirse a:
Entradas (Atom)