« Putting the TSP Algorithm Together | Main | More TSP Problems »
March 28, 2005
The plan for the rest of the semester
We will wrap up the TSP algorithm today. Wednesday (3/30) we will do the minimax algorithm and start linear programing if time permits. Friday (4/1) we will go into linear programing in earnest and stick with that through the last day of class.
Linear programing is not in the textbook. A handout will be made available before 4/1. Linear programing is an important topic because it gives you another way to think about optimization problems and ties together most of hte ideas from the whole course.
The last project is to code up the simplex method. In linear programming problems, half the "fun" is coming up with the formulation of the problem as a linear program. So this project will be a little different. We will give you a constraint satisfaction problem and you will formulate it as a linear program, convert it to slack form, implement the simplex method and use your implementation to solve the slack form of your linear program. That will simplify the project a little while focusing on the main ideas.
Posted by jones at March 28, 2005 08:52 AM
Comments
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)