The Different VersionsIn the previous section, I showed how different systems of
equations and inequalities can replaced an instance of absolute value. While each system is mathematically
equivalent to the absolute value, they are not equivalent in the eyes of an algorithm. For example, my
proposed system introduces more variables than the original formulation. The increase of complexity implies
at the start that the second algorithm will take longer to produce an optimal schedule.
In addition to auditioning different models of absolute value, the concept of applying
track changes to resolve conflicts also needed to be incorporated (thereby increasing complexity once again).
Out of the perhaps dozen variations that I generated, only a handful are useful for comparison. The following
are abbreviated descriptions of some of the primary code versions that I came up with:
The following table compares the above three versions, in terms of the problem dimension and
processing time. The value of the objective function for the optimal schedule is 91; note that the latter pair
of versions is much more consistent in that regard.
Five principal versions are compared in the following graph. Identical
data sets of differing sizes were fed into each of the versions, and the output is how long it took for each version
to reach optimality for that number of flights. You can think of the five versions as a spectrum; the original code
does not include track changes as a viable tool for conflict resolution, nor does it include appropriate absolute
value equivalents. The final version, listed here as "AV + Track Changes" includes all of those bells and whistles.
You'll note that the processing time skyrockets as more features are added, and it's easy to see that faster processing
comes at the cost of a less realistic model. Please note that the chart is not terribly robust from a statistical standpoint;
the sample size for each plotted value is too small to test for significant deviation. However, the chart reflects
the intuitive inverse relationship between model complexity and time to solution.
We gave our final presentations a week before the program officially ended, since half of us went on an
all-expenses-paid trip to Prague. My final presentation
includes some review from my first presentation, and summarizes the results that I discussed above.
From the table above, it looks like the original version of the code is practically worthless. What
good is an algorithm, even a fast one, if the resulting schedule is not optimal? If conflicts still exist in the output,
clearly the algorithm needs improvement.
But maybe it's not that cut-and-dried. Several weeks into the project, I took a closer look at the section
of the algorithms that generates the output (either written into a file or displayed within XPress) and found some errors.
Within the matrix output of XPress, the solution was consistently correct. The internal matrix display - at least in my
admittedly limited experience - has not failed to display the optimal schedule. Even so, the output dispensed by the code
contains errors. I spent some time investigating the lines of code responsible for generating the output in an easy-to-interpret
file, but could not find an alternate way to print the schedule. The results of this minor investigation? The formulation of the
original version is not to blame for faulty schedules, as the matrix produces the optimal schedule; the fault lies with
the way in which output is written to a file.
To a certain extent, this relatively recent discovery nullifies my comparisons from earlier. When
comparing the versions it is important to note that the original code is the simplest tested, which accounts for at
least part of its processing speed. Perhaps it has a superior formulation as well, but that would require "beefing"
it up to the complexity of the other versions before they could be truly compared.
Given more time, I would work towards the following goals:
It's hard to get a foothold in a research project and produce tangible results within only a few weeks;
that's been my experience and the experience of several peers this summer. Even so, I learned about the importance of
background research and cross-referencing during the introduction phase of a project. Software output commands are not
necessarily infallible, and sometimes what looks like a simpler model on paper will actually generate a more complex
programming problem.
In addition to working on my project, I also got to attend the
MISTA Conference at the Stern School of Business at NYU. Since Abhinav and I
were definitely the only undergraduates in attendance, we learned a lot about scheduling at the thirty+ presentations we
went to :) Seeing the spread of information at such a focused conference was a nice motivation for research in general; now I
have a better idea of how theories and algorithms gain fame and audiences.
If you have any questions about my work at Rutgers or my time in New Jersey, please feel free to drop me a line at
jhmccoy@ncsu.edu!
|
