5
1

The past couple of months i have been studying the basic algorithms for OR (GLS, ILS, TS, SS etc.)

"Studying" means:

  1. Taking an algorithm, studying the first paper that proposed it.

  2. Reading the corresponding chapter from "Handbook of Metaheuristics- 2010" (btw: amazning work. Congratulations to all of the Authors.)

  3. Studying papers with illustrative applications for each algorithm.

This procedure works well up to point. This point is where theory stops and practice begins.

So i'm currently trying to code the algorithms i learn.

As a "guiding" book i use Clever Algorithms since it has code examples. But to be more effective i code the examples coded in Ruby, in Java. I've also checked this but i didn't like it much.

I think most of the OR researchers in this forum have taken this step and my question is quite simple: How did you do it? I would like some advice on the way i should work to effectively go from design to implementation. Is there a good book i could use?

I already have a good understanding of OOP (Java and Ruby).

Finally, do i have to learn an other programming language (such as C++ even if i disagrre with the claim that is faster than java). Also, what about Haskell? Is it worth spending time on learning procedural programming as another perspective?

asked 12 Aug '11, 04:23

Florents%20Tselai's gravatar image

Florents Tselai
600516
accept rate: 7%


First an observation, that you have been studying metaheuristics, which are only a part of OR... many people here would probably argue not as important a part as exact methods such as linear and integer programming, or even non-linear programming. Personally, I love metaheuristics, but it is worth drawing the distinction.

The Handbook of Metaheuristics is a fantastic introduction. If you want to learn more detail I'd suggest following up the journal articles cited in each chapter.

Programming these algorithms is definitely a great way to learn them. In terms of how you should do it, my advice would be to just dive on in and give it a go however seems best to you. Your first attempts will probably not be as efficient or elegant as those of an experienced practitioner, or even as your later attempts, but that is part of learning. The more of these algorithms you program, the more you will start to identify the parts where they are similar, and you can then abstract these out for reuse. But I'd suggest programming them naively first, and refactoring later, rather than trying to do it the "best" way to begin with.

Java and ruby will be fine for these algorithms. I wouldn't bother learning another language unless you want to anyway. Raw close-to-the-metal speed is important for linear-algebra-based algorithms like the simplex method, but for metaheuristics the way you implement it will make so much more difference that I wouldn't bother trying to optimize prematurely.

It's always worth learning another language to get more perspective of different ways of doing things. I'm currently learning clojure, and getting a lot out of it. But it's not necessary to implement metaheuristics.

link

answered 12 Aug '11, 07:25

DC%20Woods's gravatar image

DC Woods ♦
4.1k22546
accept rate: 5%

edited 12 Aug '11, 07:30

Thanks for the answer. I've already completed courses on: LP and MIP formulations, math programming (principles of duality theory, simplex method etc.) and non-linear optimization. Wich means that i already know tha fundamentals/classic methods of OR, but i find algorithmic optimization much more interesting. Nevertheless, i do not neglect exact methods.

Actually, in the next 2 semesters i'll have 2 courses in heuristic and metaheuristic methods.

(12 Aug '11, 07:43) Florents Tselai

@Florenc So LP and MIP is not "algorithmic optimization" ?

(12 Aug '11, 07:46) Bo Jensen ♦

@Bo Jensen Of course it is. Simplex method for LP it is an algorithm. :P But i mean "algorithmic optimization" using heuristic algorithms.

(12 Aug '11, 07:53) Florents Tselai

@Florenc, I think your terminology is a bit misleading, probably best to be specific. I'm with you on metaheuristics being interesting though.

(12 Aug '11, 07:58) DC Woods ♦

My path towards OR started with an IT degree, and I think that it helped me a lot. Coding is a matter of practice and good coding skills are even more important in OR because of the complexity of the algorithms. I think that there are two different important issues on coding OR algorithms (and maybe in general):

  • writing efficient code;
  • writing useful and readable code.

For the first topic, I would suggest practicing at places like SPOJ, TopCoder and Google CodeJam whose main focus is programming contests and you can learn a lot reading somebody else's codes and trying increasingly more difficult problems.

For the last topic, I think that professional experience and reading online articles helped me a lot. I don't see a real issue about coding in Java instead of C++. What really matters is coding in a way that you can understand what you are doing, the code works well and you can share it with others. After all, choosing a high level language increases runtime only at a constant factor. What really matters to us is to find a better asymptotical complexity: a clever and smart way of solving a hard problem. I would recommend two interesting essays about programming: Teach Yourself Programming in Ten Years by Peter Norvig and Optimization: Your Worst Enemy by Joseph M. Newcomer.

link

answered 12 Aug '11, 09:15

Thiago%20Serra's gravatar image

Thiago Serra
1.2k413
accept rate: 1%

edited 12 Aug '11, 09:16

If you are concerned about execution speed/efficiency, you might want to poke around Stack Overflow and other programming sites, specifically looking for information about relative virtues of different collection types (and other programming tips, such as avoiding unnecessary recursion). From what I've read (online), sometimes people code algorithms in what appears to be a perfectly logical and streamlined way, but use a less than ideal collection type (for instance, using an ArrayList to track which constraints are violated -- a HashSet is more efficient) and pay a rather surprising (to me) performance penalty.

link

answered 12 Aug '11, 18:07

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Well, for the time being, i don't worry that much for performance of this level, as for learning the basic techniques e.g. performing moves, perturbations etc.

The "perfectly logical and streamlined way" is what @DC Woods described as "first attempts will probably not be as efficient or elegant as those of an experienced practitioner"

Indeed, ArrayList is one of the most useful collections but it's too inefficient.

(12 Aug '11, 18:32) Florents Tselai
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×29
×28
×14
×13

Asked: 12 Aug '11, 04:23

Seen: 2,035 times

Last updated: 12 Aug '11, 19:03

OR-Exchange! Your site for questions, answers, and announcements about operations research.