CSCE 782: Problem Set 4

Due: Tuesday, 9 November 2004, before class

Upload Problem Set

Figure 1:Implementation of the distributed breakout algorithm for graph coloring.

Better Breakout

For this problem set you will design, implement, and test a modification of the standard distributed breakout algorithm that also works for distributed constraint optimization problems.

You will start using my code for distributed breakout (click on Figure 1 to get the code) and modify the program in two ways.

  1. Change it so that it no longer ensures that the graph generated has a coloring that does not violate any constraints.
  2. Make each constraint violation have a cost of 1.
After these changes the breakout algorithm should still work, even if it does not always find the optimal solution.

You will then design and implement your own modification of the breakout algorithm which helps improves performance over the standard algorithm.

In order to prove that your algorithm is better you should have one button that runs both algorithms on the same graphs, with the same initial colorings, and then plots the difference in their final cost. If you are doing better then the graph should show a bunch of points above the x-axis and few below.

For added credit you can identify those circumstances under which your algorithm really performs well (number of nodes, number of colors, edge ratio).

Submission Instructions

This problem set is to be done individually. You cannot ask or receive help from anyone. As will all the problem sets, you will hand them in using our department's dropbox. You will hand in only one file, your .nlogo file. You will use the information tab of the program for writing your detailed explanation of the techniques you used, how the program works, how to set the controls to obtain the different behaviors you want to show, etc. The information tab needs to start with:

email: (I will email your grade and comments to this address)

I understand that it is the responsibility of every member of the Carolina community to uphold an maintain the academic standards and integrity of the University of South Carolina. Any member of the University community, who has reasonable grounds to believe that an infraction of the Code of Student Academic Responsibility has occurred, has an obligation to report the alleged violation.

I certify that I have neither given nor received unauthorized aid on this problem set.

José M. Vidal
Last modified: Fri Oct 29 12:34:11 EDT 2004