Discrete Optimization Data Science Heuristic & Metaheuristic
- 3.3
-
![]()
![]()
![]()
Brief Introduction
Discrete Optimization in Data Science: Heuristic and Metaheuristic MethodsDescription
Discrete Optimization is something all of us use in our daily activities when say, we order at a restaurant, decide which subject to study, take up a new activity… or look for a change.
It comprises of choosing between alternatives that best suit some objective we have in mind. When such things are formalized, i.e. the objective and the ability of each choice to fulfill that objective are quantified, we get a mathematical expression of the problem we would optimize.
The classical or statistical method of enumerating all solutions and choosing the best out of them is the ideal way of solving any optimization problem, and will always lead to the global optimal solution— however complex be the discrete optimization (or Combinatorics) problem.
But such a brute force solution is only feasible for some smaller problems involving a handful of features. As soon as the dimension of the problem starts growing, brute force fails, sheerly from time considerations. We then have to think of better ways to solve… and come across methods or heuristics such as a greedy algorithm, which chooses the most beneficial solution step at each iteration. Such a procedure gives an acceptable solution fast enough, but not always able to find the shortest route (our original objective). This results in a compromise or trade-off between accuracy and speed, without which most practical problems would never be solved.
The major treatise of optimization is considered equivalent to finding the shortest route through a series of cities. This comprises the generic Travelling Salesman Problem (TSP), generic in the sense that most discrete optimization problems can be reduced to the TSP very easily. Different algorithms can be employed to solve this problem. The solution methods in this discrete optimization course are practically illustrated with different instances of the TSP (and a knapsack problem) as examples.
Nature-inspired metaheuristics give us some excellent ways to solve a discrete optimization problem in an elegant way. Ant Colony Optimization (ACO) is one such algorithm proposed by Marco Dorigo in the 1990’s, and is considered a state-of-the-art method to solve the TSP.
The course progressively relates live real-world experiences to optimization problems and casts them in the language of mathematics. The methods to solve the TSP is introduced lucidly, and with care. Three example problems of increasing difficulty are solved through different methods introduced in the course, and their individual results compared.
Requirements
- ESSENTIAL : A moderate knowledge of Mathematics (High School level)
- BOOSTER : Familiarity with some programming language (preferably R)
- BOOSTER : Interest in solving puzzles and games involving logic
- BOOSTER : Basic knowhow on what Data Science is about
Knowledge
- What is optimization
- Some real-life situations where we need to optimize an objective
- The mathematical formalism of optimization
- How discrete optimization (Combinatorics) differs from continuous optimization
- Different approaches to solve a Combinatorics problem, including— The simplest, perfect but slow ‘Brute Force’ method. One of the fastest and practicable ‘Greedy’ heuristic.A look-ahead mechanism to refine the greedy approach.
- The most popular problem in Combinatorics, viz. Travelling Salesman Problem
- Other generic problems in discrete optimization, like the Knapsack Problem
- How metaheuristic approaches compare to heuristic solutions
- The nature-inspired class of metaheuristic approaches
- Ant Colony Optimization: its basis, modus operandi, algorithm and flow chart
- The R library to implement Ant Colony Optimization and other heuristic solutions
- Examples of Travelling Salesman Problems solved through different approaches
Outline
- Introduction and Overview
- Instructor Details, Experience and why you fit to teach the course
- THE FULL COURSE CURRICULUM OVERVIEW [ MUST DOWNLOAD ]
- Know Your Instructor [DOC]
- Who can take the course
- Who Can Take This Course [DOC]
- Prerequisite to take the course
- Prerequisite to take the course [DOC]
- What students will learn at the end of the course
- What students will learn at the end of the course [DOC]
- What is the Importance of the Course
- What is The Importance of the Course [DOC]
- Story with a Lession
- Selecting a candidate in an interview
- Selecting a candidate in an interview [DOC]
- Which Movie to Suggest?
- Which Movie to Suggest ( STUDY NOTE )
- Finding the Objective
- Finding the Objective [ Study Note ]
- The Story of a Travelling Salesman
- The Story of a Travelling Salesman [ STUDY NOTE ]
- Packing a Knapsack for the Tour
- Packing a Knapsack for the Tour [ STUDY NOTE ]
- Packing a Knapsack for the Tour [ CODE ]
- Heuristic Solutions
- Brute Force Algorithm
- Brute Force Algorithm [STUDY NOTE]
- Brute Force Algorithm [ CODE ]
- Taking an Obvious Short-Cut
- Taking an Obvious Short-Cut [ STUDY NOTE ]
- Taking an Obvious Short-Cut [ CODE ]
- A Look-ahead Trick for Long-term Gain
- A Look-ahead Trick for Long-term Gain [ STUDY NOTE ]
- Mathematicizing the Heuristic
- Mathematicizing the Heuristic [ STUDY NOTE ]
- Metaheuristic Approaches
- Learning from Natural Phenomena
- Learning from Natural Phenomena [ STUDY NOTE ]
- How Ants Find Food
- How-ants-find-food [ STUDY NOTE ]
- The Abstraction of Ant Colony Optimization
- The Abstraction of Ant Colony Optimization [ STUDY NOTE ]
- The Ant Colony Optimization Algorithm
- The Ant Colony Optimization Algorithm [ STUDY NOTE ]
- Examples and Solution
- bays 29 : 29 Cities Problem in Baveria
- 29 Cities Problem in Baveria [ STUDY NOTE ]
- DOWNLOAD LINK
- bays 29 : 29 Cities Problem in Baveria [ CODE ]
- bays 29 : 29 Cities Problem in Baveria [ DATA SET ]
- berlin 52 : 52 Locations in Berlin
- berlin 52 : 52 Locations in Berlin [ STUDY NOTE ]
- berlin 52 : 52 Locations in Berlin [ CODE ]
- berlin 52 : 52 Locations in Berlin [ DATA SET ]
- ch150: 150 City Problem
- ch150: 150 City Problem [ STUDY NOTE ]
- ch150: 150 City Problem [ CODE ]
- ch150: 150 City Problem [ DATA SET ]
- Comparing Solutions
- Comparing Solutions [ STUDY NOTE ]
Up Degree
3.3 Raiting
Discrete Optimization Data Science Heuristic & Metaheuristic
- 3.3
-
![]()
![]()
![]()
![]()
![]()
Discrete Optimization in Data Science: Heuristic and Metaheuristic Methods It comprises of choosing between alternatives that best suit some objective we have in mind....
