A node coloring is valid or admissible if any two adjacent nodes do not have the same color. If a graph is colorable, there is a smallest number such that the graph is node colorable. This number is called the chromatic number of the graph and is usually denoted by . The problem to identify… Read more Graph Coloring Problem

# Category: heuristics & algorithms

## TSP Miller-Tucker-Zemlin Subtour Elimination Constraint

In this post we want to try to provide a solution to solve the Traveling Salesman Problem (TSP) using linear programming. The post is based on this excellent video from Mr. Michel Bierlaire at the EPFL. A good written documentation of the Miller Tucker Zemlin Constraint can be found here. What is a TSP? The… Read more TSP Miller-Tucker-Zemlin Subtour Elimination Constraint

## Solve Knapsack Problem with Heuristics in R

In this post I’ll show a way how to solve the Knapsack Problem applying a simple greedy improvement heuristic and how to implement it in R. What is the Knapsack Problem? On Wikipedia, you find the following definition: “The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a… Read more Solve Knapsack Problem with Heuristics in R

## A Sudoku Solver in a few Lines of Code – Or the Power of Recursive Programming

In this post I want to demonstrate the power of recursive programming by programming a sudoku solver in Python. The complete sourcecode can also be downloaded here. Although I like solving Sudokus by hand, I’m far away from being a professional Sudoku solver. Usually I get the medium-ones solved, however, since I always want to… Read more A Sudoku Solver in a few Lines of Code – Or the Power of Recursive Programming

## Calculate an MST with Ant Colony Optimization in Python

Ant Colony Optimization is an old but still often applied construction heuristic to develop solutions using nature inspired behavior. The heuristic mimics the behavior of ants when finding shortest paths to between their nests and some kind of attraction, i.e. a food-source. The main idea are the pheromone trails, which ants leave behind, when travelling… Read more Calculate an MST with Ant Colony Optimization in Python

## Tabu Search in R

Here I’ll show you a way, how to do Tabu Search with Steepest Descent with best improvement in R. Tabu Search is a local improvement heuristic used to improve existing solutions. Such heuristics are also called local search heuristics. How does Local Search work? Local search can be described in words as follows: Take initial… Read more Tabu Search in R

## Solve TSP using Pilot Method

This post shows a simple implementation using R to solve a given TSP (Traveling Salesperson Problem) instance using the Pilot Method. The whole R script can be accessed here on my gist. How does the Pilot Method work? The Pilot Method is a construction heuristic to build (i.e. initial) solutions. The method tries to avoid… Read more Solve TSP using Pilot Method