4005-741-01 Advanced Computer Networks
Module 4. Combinatorial Optimization
Lecture Notes

Combinatorial Optimization

• Optimization problems
  • Continuous optimization -- optimization over a continuous domain
    • Neighborhoods
    • Smoothness
  • Combinatorial optimization -- optimization over a (large) discrete domain
    • No neighborhoods
    • No smoothness
  • Local vs. global optimum

• Combinatorial optimization techniques
  • Finding the answer: "I'll know it when I see it"
  • Exhaustive search
  • Heuristic
  • Directed search

• Exhaustive search
  • Completely unintelligent
  • Easy to program
  • Guaranteed to find the global optimum
  • Takes too long

• Heuristic
  • Requires a high degree of intelligence and insight to design
  • Runs quickly
  • Not guaranteed to find the global optimum
  • May come close to the global optimum
  • In some cases, can guarantee the answer is within a known factor worse than the global optimum

• Directed search
  • A combination of searching and heuristics
  • Use heuristics to decide what to search, rather than searching everything
  • A bit tricky to program
  • Can find answers much faster than exhaustive search
  • Not guaranteed to find the global optimum
  • May come close to the global optimum

• Directed search techniques
  • We want "wide spectrum" directed search techniques that can be applied to many different kinds of problems
  • Genetic algorithms
  • Simulated annealing
  • Tabu search

• I don't like genetic algorithms or simulated annealing
  • They have parameters that must be hand-tuned to get good results

• I like tabu search
  • Simple concept
  • A variation, reactive tabu search, automatically tunes its own parameters

Reactive Tabu Search

• R. Battiti and G. Tecchiolli. The reactive tabu search. ORSA Journal on Computing, 6(2)126-140, 1994.

• Reactive Search Web Site. http://www.reactive-search.org/

• Package edu.rit.discreteopt
  • Class Configuration
  • Class ReactiveTabuSearch

• The reactive tabu search algorithm
  • Class ReactiveTabuSearch source code

• Example: graph coloring

• Package edu.rit.discreteopt.test
  • Class Edge [source code]
  • Class Graph [source code]
  • Class Coloring [source code]
  • Class GraphColoring01 [source code]

Example: Sensor Network Cluster Heads

A sensor network is located in a square area of D×D meters. The area is divided into NX×NY subareas. A sensor node is located at a random position in each subarea. There is a base station at the center of the area. The nodes are to be arranged into a two-level tree topology, as follows. Certain nodes are designated as cluster heads. There is a link from each leaf node (non-cluster-head node) to the closest cluster head node. There is a link from each cluster head node to the base station.

Question: Which nodes should be cluster head nodes, so as to minimize the total transmitter power in the sensor network?

Each node's transmitter power is determined by the length of the longest link attached to that node. So we will modify the question: Which nodes should be cluster head nodes, so as to minimize the sum of the lengths of the longest links attached to each node?

The program below conducts a reactive tabu search to solve this combinatorial optimization problem. Class ClusterHeads represents a configuration, stating which nodes are cluster heads and which are not. Class SensorNet01 is the main program. Whenever the search finds a new best solution, the program both prints the solution and displays a plot of the solution.

• Class ClusterHeads [source code]

• Class SensorNet01 [source code]

• Example program run

  [ark sensor]$ java SensorNet01 1000 10 10 142857 10000
  0. Cluster heads = 2 4 5 8 12 13 18 20 21 22 23 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 53 cluster heads, total length = 23870.428769994676
  1. Cluster heads = 4 5 8 12 13 18 20 21 22 23 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 52 cluster heads, total length = 23482.97676976945
  2. Cluster heads = 5 8 12 13 18 20 21 22 23 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 51 cluster heads, total length = 23111.42623723279
  3. Cluster heads = 8 12 13 18 20 21 22 23 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 50 cluster heads, total length = 22836.124105124072
  4. Cluster heads = 12 13 18 20 21 22 23 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 49 cluster heads, total length = 22370.82919437051
  5. Cluster heads = 13 18 20 21 22 23 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 48 cluster heads, total length = 22119.660444280875
  6. Cluster heads = 13 18 21 22 23 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 47 cluster heads, total length = 21752.927867880437
  7. Cluster heads = 13 18 21 23 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 46 cluster heads, total length = 21498.454677428846
  8. Cluster heads = 13 18 21 25 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 45 cluster heads, total length = 21399.789527630448
  9. Cluster heads = 13 18 21 28 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 44 cluster heads, total length = 21327.82447091247
  10. Cluster heads = 13 18 21 30 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 43 cluster heads, total length = 21076.37441385993
  11. Cluster heads = 13 18 21 31 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 42 cluster heads, total length = 20731.48821881524
  12. Cluster heads = 13 18 21 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 41 cluster heads, total length = 20637.21337420866
  13. Cluster heads = 13 18 21 33 34 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 42 cluster heads, total length = 20612.272105307147
  14. Cluster heads = 13 18 21 33 35 37 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 41 cluster heads, total length = 20560.812190796267
  15. Cluster heads = 13 18 21 33 35 38 40 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 40 cluster heads, total length = 20261.259109490795
  16. Cluster heads = 13 18 21 33 35 38 41 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 39 cluster heads, total length = 19893.701580473455
  17. Cluster heads = 13 18 21 33 35 38 44 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 38 cluster heads, total length = 19618.342027847226
  18. Cluster heads = 13 18 21 33 35 38 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 37 cluster heads, total length = 19608.852226645024
  19. Cluster heads = 13 18 21 33 35 38 45 46 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 38 cluster heads, total length = 19570.272051857504
  20. Cluster heads = 13 18 21 33 35 38 45 48 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 37 cluster heads, total length = 19484.57966936271
  21. Cluster heads = 13 18 21 33 35 38 45 49 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 36 cluster heads, total length = 19223.991869080794
  22. Cluster heads = 13 18 21 33 35 38 45 50 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 35 cluster heads, total length = 18869.07761202923
  23. Cluster heads = 13 18 21 33 35 38 45 51 52 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 34 cluster heads, total length = 18551.557086417706
  24. Cluster heads = 13 18 21 33 35 38 45 51 53 54 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 33 cluster heads, total length = 18412.57733144538
  25. Cluster heads = 13 18 21 33 35 38 45 51 53 55 56 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 32 cluster heads, total length = 18394.090573240566
  26. Cluster heads = 13 18 21 33 35 38 45 51 53 55 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 31 cluster heads, total length = 18386.793179097265
  27. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 57 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 32 cluster heads, total length = 18352.134344464004
  28. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 31 cluster heads, total length = 18201.789048344548
  29. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 63 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 30 cluster heads, total length = 18099.260809917774
  30. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 64 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 29 cluster heads, total length = 17989.250510650338
  31. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 67 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 28 cluster heads, total length = 17972.19814656238
  32. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 68 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 27 cluster heads, total length = 17721.3353789642
  33. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 69 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 26 cluster heads, total length = 17671.69864542589
  34. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 25 cluster heads, total length = 17437.40004436686
  35. Cluster heads = 13 18 21 33 35 38 45 46 48 51 53 55 72 74 76 79 80 87 90 91 92 93 94 95 98 99, 26 cluster heads, total length = 17410.886134055316
  36. Cluster heads = 13 18 21 33 35 38 45 46 48 51 53 55 72 74 76 80 87 90 91 92 93 94 95 98 99, 25 cluster heads, total length = 17140.546789277
  37. Cluster heads = 13 18 21 33 35 38 45 46 48 51 53 55 67 72 74 76 80 87 90 91 92 93 94 95 98 99, 26 cluster heads, total length = 17115.068691527722
  38. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 67 72 74 76 80 87 90 91 92 93 94 95 98 99, 25 cluster heads, total length = 17102.461484335538
  39. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 67 72 74 76 80 87 90 91 92 93 94 95 98 99, 26 cluster heads, total length = 17050.033800213347
  40. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 80 87 90 91 92 93 94 95 98 99, 25 cluster heads, total length = 17017.535384945604
  41. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 87 90 91 92 93 94 95 98 99, 24 cluster heads, total length = 16666.844730556466
  42. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 90 91 92 93 94 95 98 99, 23 cluster heads, total length = 16450.55312162024
  43. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 91 92 93 94 95 98 99, 22 cluster heads, total length = 15977.837965384913
  44. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 92 93 94 95 98 99, 21 cluster heads, total length = 15461.302361696135
  45. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 93 94 95 98 99, 20 cluster heads, total length = 15375.91142343863
  46. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 94 95 98 99, 19 cluster heads, total length = 15165.312737992677
  47. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 92 94 95 98 99, 20 cluster heads, total length = 15121.58185122379
  48. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 92 95 98 99, 19 cluster heads, total length = 14832.517582795766
  49. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 74 76 92 95 99, 18 cluster heads, total length = 14318.298094667061
  61. Cluster heads = 13 18 21 33 35 38 45 46 51 53 55 58 72 75 76 92 95 99, 18 cluster heads, total length = 14301.99913291725
  121. Cluster heads = 4 11 15 18 32 34 37 43 45 46 51 53 55 58 62 67 74 75 86 89 91, 21 cluster heads, total length = 14257.728311814571
  123. Cluster heads = 4 11 15 18 32 34 37 43 45 46 51 53 55 58 62 67 75 83 86 89 91, 21 cluster heads, total length = 14252.54991374412
  124. Cluster heads = 4 11 15 18 32 34 37 43 45 46 51 53 55 58 67 75 83 86 89 91, 20 cluster heads, total length = 14248.97038752765
  125. Cluster heads = 4 11 15 18 32 34 37 43 45 46 51 53 55 58 67 71 75 83 86 89 91, 21 cluster heads, total length = 14223.546484057639
  126. Cluster heads = 4 11 15 18 32 34 37 43 45 46 51 53 55 58 67 71 75 83 86 89, 20 cluster heads, total length = 14153.325009608634
  128. Cluster heads = 4 11 15 18 32 34 37 43 45 46 51 53 55 58 67 71 75 86 89 92, 20 cluster heads, total length = 14116.778325573974
  129. Cluster heads = 4 11 15 18 32 34 37 43 45 46 51 53 55 58 63 67 71 75 86 89 92, 21 cluster heads, total length = 14109.973924208476
  10000. Cluster heads = 4 11 15 18 32 34 37 43 45 46 51 53 55 58 63 67 71 75 86 89 92, 21 cluster heads, total length = 14109.973924208476
  

  

Advanced Computer Networks • 4005-741-01 • Fall Quarter 2009

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2009 Alan Kaminsky. All rights reserved. Last updated 03-Nov-2009. Please send comments to ark­@­cs.rit.edu.