#discreteoptimization

[vincentrupp]

Knapsack Perfection

It took some enhancing, but I improved my relaxation, branch, and bound algorithm quite nicely.

That last set has 10,000 items. It took about 20 minutes to run, which isn't bad for a sample space that has 2^10000 possible permutations.

Not bad for someone who hadn't written a serious Python program until three days ago.

[vincentrupp]

Algorithmic Efficiency

I took Data Structures and Algorithms using C++ in college. One thing that kept coming up was that some algorithms are much better than others.

That's great, but no one at the time really cared. Computers were getting faster all the time, so whether you could multiply matrices in O(N^3) or O(N^2.7) time didn't really affect our lives. Plus, our matrices were small.

My relaxation, branch, and bound algorithm took well over two hours to run on a set of 30 items.

My new dynamic programming algorithm took under 1 second.

For 200 items, it only took a couple seconds.

My algorithm basically copies the example from the videos, but I made a huge improvement in that instead of filling in the entire table, I recursively fill in the table as needed. That means computing (with my small-number tests) about 1/10th as many values.

When I tried it for 400 items (#4 out of 6 in the graded assignments), it took up all my computer's memory and I had to shut it down. (~10M capacity * 400 items = a matrix with 4 billion entries)

I have two computers. One is a desktop with six cores and 10GB of RAM. The other is an all-in-one with two cores and 4GB of RAM. You can probably guess which is for work and which is for games.

I used my super-simple greedy algorithm to submit the 400-item, 1000-item, and 10000-item knapsack problems and got results that were within 1% of optimal.

My total score for the first assignment is now

10/10 Optimal

10/10 Optimal

10/10 Optimal

7/10 Good

7/10 Good

7/10 Good

That's 51/60, which is plenty to pass the course, but I want that certificate of distinction so I'll have to come back to these once I learn some more advanced techniques.

And since the whole course is online at once, I'm off to watch some more videos now. =D

[vincentrupp]

Discrete Optimization - Knapsack

The course submits assignments using python, so there are solver.py and submit.py scripts given to students. There's also a solverJava.py for students who want to program in java and have python grab their results.

Since many of the jobs I've looked at want Python, I decided to use Python instead of tackling these assignments in R.

I took the whole 13-hour sequence for Python on Codecademy, but that was last summer, about six months ago. Apparently, I didn't remember as much as I thought I did.

Python 3.4 is already installed on my computer, but the course files use 2.7.x, so I installed that; Google helped me figure out how to run scripts from the command line, and the course's forums pointed to the IDE Anaconda, which is SO much easier.

Parts of the next ten hours would have made a great 80's musical montage, as I googled "python dictionaries" and a hundred other absolute basics like syntax of for loops and then tried out variations to see what I could do and what would throw me errors.

Either I remembered more than I thought or I'm just amazing with picking up new things (probably a mix of both) because by 10PM I had finished a simple greedy algorithm and implemented a relaxation/branch/bound depth-first tree search.

I got stuck for almost two hours trying to track down a "bug" that turned out to be a fundamental part of how Python works. Lists, you see, are mutable. So when I say:

x = [1,2]

y = x

x += [3]

y

The output shows that y is also the list [1,2,3]. That's because when I created y, it only created a memory reference to where x is also pointing. I was passing item_values around to at least three functions, which is why it took me so long to find out exactly what was going on.

This works as I wanted:

x = [1,2]

y = []

y += x

x += [3]

y

Now the output for y is [1,2].

It's always such an interesting puzzle when you can do something simple by hand, like list every permutation of 1's and 0's for n spaces, but you have to figure out how to tell the computer how to do what you can easily see.

The first graded set has 30 items. There are 2^30 (about a billion) ways to permute those items (for inclusion or not).

My program hadn't finished running in two hours, so I went to bed. This morning, it had spit out the optimal solution [sunglasses emoji], but due to particulars with the item set, this method is simply not very good. Even pruning 70% of the possibilities meant it had to explore close to 300 million trees.

Now, I'm off to implement dynamic programming. It should go quicker today, since I won't have to look up how to write an IF statement.

[vincentrupp]

Discrete Optimization Week 1 - Content

I joined this class on a lark, something to build some new skills, practice some more programming.

The intro video got me fairly hooked. The instructor is quite clearly just the right amount of nuts. Enough to make the class interesting, but not so you worry about poking around in his cellar.

Professor Pascal Van Hentenryck leads the optimization research group at NICTA. There's nothing on their website (visible within 6 seconds) regarding what that acronym means, but he works in Australia (also at Brown) and I believe is Dutch.

His bio is seriously impressive, including "main designer and implementor of the CHIP programming system, the foundation of all modern constraint programming systems."

The introductory video starts with him dressed up as Indiana Jones, speaking very excitedly at a speed that made me check whether I'd accidentally set the video to 1.25x playback.

The lectures are all him, wearing different hats to represent different methods ,in front of a green screen while moving around (at one point fumbling with his hat in the air for two seconds before catching it again) expertly clicking through his slides.

He says this class is very hard, maybe 15 hours a week. For a single class, that's quite a commitment. Most instructors would be worried about scaring off students, but he doesn't care. He wants students to work hard and enjoy it.

He's clearly enjoying dressing like Indiana Jones and describing the knapsack problem and several simple attempts at solving it.

The lectures regarding the knapsack problem cover greedy algorithms; dynamic programming; relaxation, branch, and bound; and methods to implement that last item.

Despite an MS in Mathematics and a programming-heavy education and hobbies, I hadn't seen any of this before. Not too difficult to understand, but he said this week was the easy week.

The course is totally open, meaning all the material is there and we can explore the five programming assignments and five major topics at our leisure over the next nine weeks, mixing methods and assignments to keep trying to achieve perfect scores on every assignment.

A key to a good course seems to be motivating students to tackle a lot of work, just like good workplaces make people feel engaged, challenged, and rewarded.

It's rare to see such a technical expert and good instructor. I don't know if I have time to stick with the whole course, but he's put this big challenge in front of me, and one thing about me is that I always rise to challenges.