Enchom's blog

Solving Marathons and NP problems
By Enchom, 10 years ago, In English

Hello everybody,

I like participating in Marathon-type competitions and in the near future I will participate in a few more. However I feel like my solutions are always not good enough. I've been to a lecture of Psyho where he explained some approaches. I know in theory things like Beam Search, Simulated Annealing, Hill climbing. However when I face a marathon task I really have a hard time to choose which one to use and more importantly, how exactly to construct it.

Take a simple NP-Hard problem as the Travelling Salesman. I have no clue how to solve it using any of the above techniques, and I would probably end up using some randomized short backtracks, which would end up with a horrible score.

I would be very grateful if someone could give me some tips, and perhaps explain some not-too-hard approach for the Travelling Salesman problem, so I can learn from that.

Thanks in advance! :)

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Just wanted to share this great course on coursera which might be helpful to you: https://www.coursera.org/course/optimization. I've participated in the first session of it and I think it might be of great help. There are lectures on different optimization techniques (Simulated Annealing of what you mentioned) and there is a really great set of practical assignments to find a good solution for some NP hard problem (including travelling salesman). Also during the first session of this course there was a really strong community on the forums there which was really helpful in case if you had any questions. Though I should mention that this course is probably the most complicated and time-consuming one of those which I took on coursera.

P.S.: Can't stop myself from mentioning that lecturer there is great as well, just watch an introduction to see what I'm talking about (hm, it doesn't seem to load for me at the moment).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I haven't seen that course, so my point of view might be slightly off.

    The main problem I see with anything/anyone that shares his knowledge around various topics in AI (optimization, ML, CV) is that he/she has either purely theoretical knowledge or highly specialized in a narrow field. In those kinds of problems it's usually possible to apply many different solving techniques and unfortunately both kinds of people don't have any comparison between different methods and thus usually fail to provide any useful information.

    Let's be clear, everyone from the top of the rankings in MMs learned on their own (usually with the help of various "Post Your Approach" threads and/or code from other competitors). Not because they are super smart ignorant people, but simply because it's hard to find something that is actually worth your time. And nothing beats hands-on experience.

    That being said, if you're just starting it's nice to see 1 course / read 1 book, to get a general understanding of how huge this field is. Just remember that you still have to go through practice in the same way as you did for "classical" algorithms.

    And for SA. I think some day I'll finish that dreaded tutorial on my blog. And I'm pretty sure that reading it, is going to be worth it :)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Agree 100% with you and let me emphasize it one more time, the practice plays VERY important role in this course. The assignments on this particular course are way different from the assignments I've seen on other courses. Usually the assignments are matching the lectures — here is a lecture covering some topic, here is an assignment for the same topic. On this course you are given all the assignments in advance and there is no single topic covering some assignment, instead you just have a bunch of NP hard problems and it's up to you which approach to use, though some might work better for some given task. So in this particular course assignments are really a part of SELF-education, lecturer only gives you tools but he doesn't say how to solve some particular assignment or even which approach to use.

      → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

please, can you tell where are the Psyho's lectures?.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sorry it was on a final round of a competition held in my country about an year ago, I'm not really sure if they are publicly available online somewhere, though they were really helpful.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I should still have them on my old laptop, although don't expect too much, because the slides were created a night before the lectures :) The slides contain only bullet points — there's not too much content there. So you'll know what did I talked about, but not how :)

    The other thing is that for me, knowledge always comes secondary (after the skills). So, I tried to talk more about the proper mindset, problem solving aspect and I tried (not sure if I made a good job) to inspire and show that everything is actually pretty simple.

    Anyway, give me a couple of hours and I should be able to upload them somewhere.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    Slides:

    #0 #1 #2 #3 #4

    Be easy on the amount of grammatical/logical errors. If I remember correctly, I started doing them at 2AM :) I didn't had enough time to draw the graphs, so I drew them during the lecture. The examples section was actually quite long, but I just used visualization from old MMs mostly.

    Feel free to ask any questions.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Funny that you should say that you hate programming -- I tried to do marathons but I always think of a solution and then give up seeing how absurdly boring that would be to actually code. I see you always try to divide work in smaller steps, but aren't there times when you have to take a bigger annoying step? You said "You don't have to invest a lot of time", how long do you take generally?

      About "you don't need to try lots of approaches": I'm guessing you have more than one idea for any given problem, do you usually just filter them based on intuition alone?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        By saying "I hate programming" I mean that I dislike writing the code. Especially when I exactly know what will happen. But honestly, it's very complex topic. The point was (and still is) — you don't have to be a, let's say, computer enthusiast to be a good competitive programmer. I'm a horrible material for a software developer, since I usually have to take day off after spending more than 30 minutes on reading any kinds of documentation :) As chaotic as it sounds, my main point is that I treat programming as a tool for solving problems — I don't enjoy using those tools, but I don't really have any other choices (and I do enjoy solving complex problems)

        About the absurdly boring part — sometimes I feel the same, but the competitive aspect motivates me :) And well, I've noticed that a lot of people who seem fast in "classical" algorithms, are actually rather slow coders when it comes to MMs. I guess hyper-specialization hurts them when doing anything else.

        How long? For most qualification rounds I took something between 25-50 hours, but usually I put way too much time, to make sure that I'll qualify (i.e. failure is not an option). But in order to "gain" anything out of the competition (knowledge), you often need only 2-3 hours.

        "You don't need to try lots of approaches" part -- you answered it :) When you have enough intuition, you can actually tell what is going to work, and what won't. Sometimes there are some close calls, and you have to do some experiments, but in most cases you can tell it before even starting visualizer with some naive solution.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          I can speak only for myself, but my speed problem is actually the other way around — I'm a slow coder when it comes to pretty much everything. The first time I tried to code bipartite matching it took more than an hour, today it would take at most 5 minutes. So hyper-specialization doesn't hurt me when doing anything else, it just helps me not to be painfully slow when doing what I'm specialized at.

          Thanks for the answers!

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I feel it's so dumb question but what do u mean by 'MM' ? :D

          → Reply
»
10 years ago, # |
← Rev. 8   Vote: I like it +11 Vote: I do not like it

For Travelling Salesman Problem (TSP) one of the simplest methods is local search with 2-opt. The algorithm is the following:

tour = getRandomPermutation(n) // generate initial tour
repeat until no improving move can be found
  for i = 1..n
    for j = 1..n
      newTour = tour
      reverse(newTour, i, j) // 2-opt operator: reverses order of elements from i to j
      if (length(tour) > length(newTour))
        tour = newTour // improving move found

In spite of simplicity this method already gives quite good solutions. At least there will be no edge intersections in the case of Euclidean TSP.
There are some ways to improve this method.

One option is to run the algorithm above with different random initial solutions. Thus we come up with local search with random restarts, exactly the algorithm Petr used to solve TCO-Round-3A hard problem link. The method is powerful enough to get optimal solution for all test cases.

Another option is to use operators like 3-opt to enlarge search neighbourhood. The evolution of this idea is Variable neighborhood search.

Next we can allow not only improving moves (as in algorithm above), but also moves that make tour longer (in hope that subsequent improving moves will obtain even shorter tour). This idea brings the following methods:

I recommend you to get acquainted with these methods, then solve TSP using each of them and compare results. You will develop powerful intuition. I think TSP is ideal problem to experiment with different metaheuristics.

Recommended references:

  • wikipedia
  • "How to Solve It: Modern Heuristics" by Zbigniew Michalewicz. find
  • "Clever Algorithms: Nature-Inspired Programming Recipes" by Jason Brownlee find
  • "The Traveling Salesman Problem: A Computational Study" by David L. Applegate find
→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

All the techniques you mentioned are applicable to optimization problems. But my personal feeling is that most Topcoder Marathon matches are of a different kind — e.g. machine learning (classifying something properly) or image processing (like the matches going on right now). Sure, all the matches have a scoring function and you can argue that you need to optimize your score (which makes every marathon match problem a "score optimization problem"), but that's not the same thing.

The TCO Marathon qualifying rounds were indeed optimization problems (according to my own definition of it) and there you could have tried some of the techniques you mentioned (simulated annealing, beam search, various greedy approaches, etc.). But it seems to me that apart from the 3 TCO Marathon qualifying rounds, there are very few optimization problems in Marathon matches (so the chance to practice the techniques you mentioned is lower).

In case you want to test your skills on NP-hard optimization problems more often you could try participating in Codechef long contests — there is 1 contest per month, which lasts for 10 days. To me this time frame is better than the 2 weeks long Topcoder Marathon matches, because I find it hard to focus for 2 weeks on a single problem (also due to lack of time) — and not doing that would only bring me low scores, which makes the participation pointless to me.

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I find these problems fascinating too. After winning a few prizes on CodeChef, I tried to put together the key elements when solving these kind of problems.

HackerEarth has recently hosted my blog on this topic. Hope it helps.

NP Problem Solving

→ Reply