Introduction to Metaheuristics (2/9). Combinatorial Optimization problems

[@portiseremacunix]

Thanks! It is the only series of videos about metaheuristics on youtube!

[@sebon11]

Very clear explanation, thanks

[@hanserj169]

Such a clear and motivating content! Thanks!

[@LuisRIzquierdo]

Thanks so much for such a nice comment, Hanser!

[@Snowmanver2]

Thank you for the lecture, it is very useful and interesting!

[@LuisRIzquierdo]

Thanks for the nice comment, An!

[@SaraH-kg4hx]

Great video thank u sir sir what are the methaheuristic methods that we could use to solve the shortest path problem I have already used ACO

[@rafiqbodalal6358]

Hi Luis, I'm currently studying the problem of weight optimization of truss structures where the link cross-sectional areas are considered design variables and subjected to a penalized cost function that incorporates structural weight with stress and displacement constraints. Since the design variables operate in the continuous domain and are selected from a predefined subset from R (0.1~35), I was wondering if my problem is classified as a combinatorial one, since the main goal of the problem is to find the "right" area of each link which reduces weight all the while not compromising structural integrity. As an example, the optimized areas of a 10 bar structure (solution vector) is: [23.522 , 0.1, 25.364, 14.503, 0.1, 1.97, 12.418, 12.971, 20.050, 0.1]. Do the design variables have to be discrete so that they are an combinatorial problem or do they also extend to continuous domains? Thanks

[@LuisRIzquierdo]

Hi Rafiq, combinatorial optimization is a topic that consists in finding an optimal object from a **finite** set of objects. The key point is whether the space of candidate solutions is finite or not. If you only allow a few values for your design variables, then the space of candidate solutions is finite and then the techniques of combinatorial optimization will probably be useful. If, as in your problem, the design variables operate in the continuous domain, then they can take any value out of an infinite set (remember there is an uncountable infinite number of real numbers in any real interval), and other techniques will be more useful. It seems that the function you want to optimize is continuous; in that case, there are other optimization techniques that use that property of your problem to find better solutions more quickly (en.wikipedia.org/wiki/Optimization_problem). The more you know about the function you want to optimize, the better, since you will be able to use algorithms specifically designed for the kind of problem you are dealing with. en.wikipedia.org/wiki/Mathematical_optimization

[@alexanderbarlse2991]

Hi Luis, Great video, thank you! I have a question. I'm confused as to how linear programming (LP) is related to combinatorial optimization. Does LP belong to discrete or continuous optimization? After all LP problems use continuous variables, but serval places I have seen LP used to solve combinatorial problems, e.g., using LP-relaxation to solve an (mixed) integer problem. Can combinatorial problems be modeled as LP? In advance, thank you!

[@LuisRIzquierdo]

Hi Alexander, thanks for your comment. LP deals with methods to optimize linear objective functions, subject to linear constraints, and most often the variables are real (i.e. continuous). When the variables are required to be integers, the problem is often called integer linear programming (ILP), and it is usually way harder to solve (see en.wikipedia.org/wiki/Linear_programming#Integer_unknowns ). Combinatorial optimization problems are characterized by discrete decision variables and a finite search space, and not necessarily linear functions or constraints, so, in general, they cannot be solved using ILP techniques. I think you will find chapter 1 in Talbi ( www.wiley.com/en-us/Metaheuristics%3A+From+Design+to+Implementation+-p-9780470496909 ) very useful. Hope this helps!

[@alexanderbarlse2991]

@@LuisRIzquierdo Thank you so much!

[@alexanderbarlse2991]

Hi again Luis. Once again, thanks for your recommendation of the book, it was really good. However, I have one more question, I hope you don't mind! :-) Combinatorial Optimization is characterized by a finite search space, since its decision variables are discrete, and there is a finite but very large set of possible combinations. Does this mean that continious optimization (linear programming) has an infinite search space since its decision variables operate in the continuous domain? I mean, the search space of the LP is always bounded by its constraints so does is not have a finite search space as well? Hope you understand my question. In advance, thank you!

[@LuisRIzquierdo]

Hi @@alexanderbarlse2991, the confusion may come from the fact that you seem to think that a bounded set is necessarily finite, but this is not true. For instance, the (real) interval [0,1] is bounded and is infinite (what is even more, uncountably infinite!). Thus, if your search space is the unit interval (or, more generally, any real interval [a,b] with a

[@alexanderbarlse2875]

@@LuisRIzquierdo thank you!

[@whom4751]

wowwww