CS 540, Spring 2015: Assignment 6 (half assignment)
Creating a Sequential Algorithm Portfolio

Download Master CSV

Download Master CSV Version 2 Last Updated: April 18th, 14:00 Changes: Fixed percent-from-optimal-costs for grouse and osprey

Download Master CSV Version 3 Last Updated: April 30th, 15:52 Changes: Fixed entries for red and osprey; Fixed four entries of red; fixed entry for "red" in line 65

Part 1: Portfolio code due Saturday 5/2/15 at noon MDT
Part 2: Analysis due Saturday 5/2/15 at noon MDT

Part 1: A Sequential Portfolio

The "portfolio" developed in assignment 5 was actually just an algorithm selector. In this assignment, you will use what you developed in assignment 5 to build a very simple sequential portfolio, where the selector picks a sequence of up to 3 solvers to try. Such portfolios are often trading off time and solution quality.

As in assignment 5, your code should figure out which solver would be best given the features of a problem instance. However, if you think it might not be the best, your code can hedge its bets and run multiple solvers.

The input is the same as in assignment 5 but the output is now a sequence of solvers as in:

In the first case, the portfolio chose to run 2 solvers and 3 in the second case. We will simulate the portfolio by pretending that all solvers in a sequence are run for 5 minutes and the best solution is selected. Thus a portfolio with 3 solvers is assumed to take 15 minutes. The portfolio will be scored using the following function:
    F = (.5 * % from best known) + (.5 * amount of time)
where "amount of time" is either 5, 10 or 15 and "% from best known" will be allowed to vary depending on which solver and instance are chosen. The best performance of the solvers in the sequence will be used to determine % from best known. Note: for this function, lower is better.

The code should have the same input and signature as the portfolio from assignment 4. You can make this as complicated or simple as you want. For example, you can submit a slightly modified assignment 5 for this assignment and only select a single algorithm as was done in assignment 5. You could ignore the learned model and hard code a selection strategy based on your own analysis of the data. You could use multiple learned models. To paraphrase a quote from a favorite cooking show of mine "You will be judged on creativity and presentation." (see below) But getting something working that shows thought is the key criterion.

Part 2: Context and Analysis

As in assignment 1, you need to read a paper from the literature and describe what was done. Select a paper from these: Then you need to describe in prose a) how you designed your sequential portfolio code and b) why you designed your portfolio as you did. Relate your design to what was done in the paper. Obviously, the published portfolio will be more complex than what you do; you should be able to take some good idea from it though. In the description of your solution, you should also explain c) how you factored in the trade-off of time and solution quality and d) how you used the learned model to determine which solver(s) to run.