Project One paper outline guide

The project addresses a "problem", e.g.,

• what is the cheapest diet I can eat and still be healthy?
• what is the best path to take on a trip of multiple cities?
• what songs should my friends and I sing at karaoke?

You will solve this problem by formulating it as an LP, and then solving the LP.

You are not writing software (though you will most likely need to write code to solve the problem) or creating a "tool" for solving a class of problems: you will be creating and solving an LP to solve a specific problem.

To as great an extent as possible, real-world data should be used to formulate your problem. If you are not using real-world data, be sure to very carefully explain why you chose not to use real-world data, and your methods for synthesizing data.

• Introduction (5 points)

  Describe what you modeled and what mathematical concepts you incorporated (e.g., linear programs, graphs, markov chains, etc.) This section should be written last!

• Background (15 points)

  Describe how your group came up with the problem you will be solving: What sort of discussions led to this problem? Were personal interests of group members an inspiration for this problem?(5 points)

  Give the history of similar and related problems. In particular, research past applications of LP to problems like yours. You should cite at least four past results. Look for problems similar to yours solved by others (you may need to expand the scope of your search for previous work to include work that, for example, uses a similar technique applied to a not quite identical application). Who were the first people to solve a problem like yours? When did they do their work? What mathematical techniques did they use? How similar to your problem was it? What were the differences? (10 points)

• The model itself (40 points)

  Thoroughly describe the mathematical model (e.g., the LP) you have developed for your investigation. You should include all data used, or at least a large subset of it. (20 points).

  Describe the implementation, including code used to generate the lpsolve input file. Described any challenges you encountered to this point. (20 points).

• Solution (20 points)

  Present the results of your calculations and include all code (e.g. the lpsolve input file itself).

• Commentary on solution (20 points)

  What did you find out? What do your model and calculations tell you?

  What constraints in your LP were binding? What does that tell you?

  Is your solution realistic? What does realistic mean to your problem? How do you know if it is realistic?

  For example, if you are doing a diet problem, and you solution says you need to drink a gallon of lemon juice a day, you must ask: could I actually do that?

  Be sure to keep in mind that the solution is not the value of the objective function: it is a set of values of your variables, and how these are interpreted in terms of your original problem (i.e., how much lemon juice do I need, what cities should I visit, what ball players should I put on my team, etc.) The value of the objective function is important and interesting, but it is not, by itself, the solution.

• Variations (30 points)

  Create related problems by modifying your original problem in at least two different ways; analyze how your model needs to be updated, and find solutions to these problem variations. What do these variations tell you?

• Conclusion (10 points)

  This is not a summary: do not repeat what you did. You should answer the question: what are the major conclusions you can make from your efforts? This may include conclusions about the object of study as well as the methods of attack or any other aspect of your project.

• References/bibliography (10 points)

  Cite all sources of quoted material in place. A list at the end is not sufficient: it must be clear in the paper where the quoted material appears.

  Take a look at the Chicago Manual of Style's citation guidelines for ideas of how to format the list of references.

  Note: if you are citing a web source, you must include the URL. If the URL is ridiculously long, feel free to truncate it, but only do so if necessary.

• Appendixes (optional)

  Feel free to put long tables, code, output, etc., in appendices, but be sure to describe and label them well so that one can read them on their own without having to refer back to the rest of the paper.

• Presentation (10 points)

  While not actually part of the paper, it is part of the project. One or more group members should present the highlights of your projects to the class. It is completely okay if only one member presents. The presentation should be no more than 10 minutes long: you must select a group member to be responsible for ensuring that the presentation does not go over 10 minutes. Do not try to give every detail of your project. Be sure to give a clear description of what problem it is you are solving, then quickly describe any interesting features of the LP (if there are any), then get to the solution and variations. It is okay to just give the interesting bits.

Additional specific comments and requirements of the paper (of varying significance)

• The project paper will be submitted electronically as a pdf. Each group should submit one copy of their paper. Please name your file with the form GroupX-Project1.pdf .
• For an LP/IP problem, make sure that you justify your objective function well, particularly if it is a weighted sum of values (e.g., summing movie ratings to get the "best" set of movies). Such a function is essentially arbitrary, and so a significant part of your paper must support this choice of objective function. There are many ways to combine a set of values into one composite one.
• For an LP/IP problem, start with as few constraints as possible that will give a meaningful results. Then add constraints if the solution does not capture what you want. For instance, in a diet problem, you might be expecting a solution with very few foods; don't add a constraint forcing variety until you have run the LP and get a non-diverse result. Then add constraints to make the solution closer to your actual goal (e.g., a diet you might actually want to eat). Describe this process in the paper.
• Do not give references to internet files for project material except if it is of excessive size and then only if partial bits are included in the actual paper. For instance, if your LP file is 1000 lines, you may include just a few lines of each type (e.g., a few of each type of constraint, plus the objective function), and then give a link to the file online.
• For bibliography/references/works cited, if you use information from the web, you need to include URLs: the name of the website is not sufficient. If something is printed (e.g., a book), you need to follow usual guidelines for citing works.
• If you copy text from anywhere, you must make it clear that that is what you are doing immediately in your paper. For example, if you want to quote a few lines from Wikipedia, you can do something like this:

  The Wikipedia article on astronomy (en.wikipedia/org/wiki/Astronomy) says

  Before tools such as the telescope were invented, early study of the stars was conducted using the naked eye.

  It is NOT sufficient to simply add the article as a list of references at the end of the paper.
• Images, if copied from elsewhere, need to be sourced *in place*. A common way is with a caption below the figure.
• Be sure to state what software and version you used, on what machine, for your main calculations. You should also include the approximate time required to perform the calculations.
• Watch out that you don't use acronyms or particularly techical terms without defining them first.
• Subscripts! If you mean x_ij, write that, not xij.
• Never use the pronoun "I" in a group project paper. Either say we, or give the group member's name.
• A variation is not simply a single change of a constant in a bound. One way to get an interesting variation may be to replace your objective function with one of your constraint functions, and move the old objective function into a constraint. (This may not be feasible for all projects, as the resulting LP may not be solving a meaningful problem, but there are always other variation possibilities). This may require setting a value for your new constraint, and you will most likely want to investigate a set of choices for this value to thoroughly analyse the situation. Removal of constraints, or adding more constraints can also result in interesting variations.
  
  Comparing the value of the objective function of solutions versus the value in one constraint (e.g., how does the maximum amount of protein we can get in a burrito relates to the amount of sodium we allow in the burrito?) can be a very interesting analysis. A plot of objective function values versus the value used in a constraint can nicely illustrate this. You should run your LP many times with different constraint values to get good information of this sort.

• Don't be stingy! You've got an IP/LP (and/or some other model) all wired, so use it! Use it hard! Change every constant and see what happens! Add constraints, remove constraints, change your objective function, figure out what matters and what doesn't, dig deep and compare and discuss!