Discrete optimisation

Discret optimization techniques applied on different combinatorial problems.

Problems implemented

Graph-coloring
Knapsack
Travelling salesman

###Graph-coloring (aka map-coloring) Problem statement: The basic idea is to color a graph in which no two connected nodes share the same colors. The challenge is to find the minumim number of colors needed to color the graph (chromatic number)

Currently solved using these approaches:

• Greedy - Just pick the first available color and proceed to the neighbour, backtrack if not feasible.
• D-satur - Color most saturated verices then proceed to neigbours.
  
• Great paper by Technical University of Gdansk about D-Satur algorithm
• VAS(Variable neighborhood search)

Knapsack

Problem statement: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

Currently solved using these approaches:

• Dynamic-programming