MATP6620 / DSES6760
- Exam and homework scores
are available. They are sorted by the sum of the last five digits of
your RIN, which is in the middle column.
- Homework scores are available. They are sorted by the sum of the last five digits of your RIN, which is in the last column.
- Course outline.
- I will put solutions to homeworks and exams, as well as some books, on reserve in the library, where they will be available electronically. You can borrow the materials for up to an hour. Further, you can borrow the books overnight if you check them out less than an hour before closing time and return them early the following day.
- Final Exam:
Scheduled for Tuesday, May 8, 3-6pm,
in DCC 235.
Guidelines for the Final Exam
Some old exams:
- Final exam from 2005 (in-class). The mean on this exam was 81%.
- Final exam from 2003 (in-class). The mean on this exam was 61%.
- Final exam from 2001 (take-home). The mean on this exam was 87%.
- Midterm exam from 2001 (in-class), and its solution. The mean on this exam was 58%.
- Final exam from 1999 (take-home). The mean on this exam was 70%.
- Midterm exam from 1997 (in-class), and its solution. The mean on this exam was 64%.
- Final exam from 1997 (take-home). The mean on this exam was 73%.
- Midterm exam from 1995 (in-class). The mean on this exam was 70%.
- Midterm exam from 1993 (in-class). The mean on this exam was 72%.
- Midterm exam from 1991 (in-class).
- Midterm exam from 1989 (in-class).
- Projects
- Homeworks:
- Homework 1. To determine the most 'effective' formulation, you need to think about LP relaxations. Here is more information about AMPL.
- Solutions to homework 1.
- Homework 2.
- Solutions to homework 2.
- Homework 3.
- Solutions to homework 3.
- The AMPL files used to solve Homework 3.
- Homework 4, including an AMPL model and data file for question 4, and also some hints about using AMPL.
- Solutions to homework 4, questions 1-3.
- Solution to Question 4 on Homework 4.
- Homework 5.
- Solutions to Homework 5.
- Homework 6.
- Solutions to Homework 6.
- Handouts:
-
Papers and resources:
Most of these pointers do not lead to sites at RPI.- Two libraries of MINLP problems: MINLPlib and MacMINLP.
-
MINLP references:
- J.-P. Goux and S. Leyffer, Solving large MINLPs on computational grids, Optimization and Engineering 3(3), 2002, pages 327-346.
- I. E. Grossmann, Review of Nonlinear Mixed Integer and Disjunctive Programming Techniques, Optimization and Engineering 3(3), 2002, pages 227-252.
- S. Leyffer, Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Computational Optimization and Applications 18, 2001, pages 295-309.
- M. Tawarmalani and N. V. Sahinidis, Global optimization of mixed integer nonlinear programs: a theoretical and computational study, Mathematical Programming 99, 2004, pages 563-591.
- Tutorial on Computational Complexity, by Craig Tovey. Appeared in Interfaces 32(3), pages 30-61, 2002. Here is the library's list of ejournals starting with I. (Direct links to the journal website expire.)
- The P=NP conjecture is one of the Millennium Prize Problems. A problem based on Minesweeper is NP-complete.
- PRIMES is in P; see also here.
- NP-Completeness columns by David S. Johnson.
- Survey papers on cutting plane algorithms, branch-and-bound, and branch-and-cut.
- An amusing interview with Vasek Chvatal regarding cutting plane methods for the TSP.
- Here is a page on the history of the TSP, with pictures (including one involving Car 54 and one of the optimal tour for a graph with 13,509 cities). This is part of a larger site at Georgia Tech on the TSP. The website also includes the downloadable software Concorde. Two further references for this problem are TSPBIB and Vasek Chvatal's page on the TSP. Instances of TSP can be obtained from the TSPLIB. Hamilton called the problem of finding a route through the vertices of a icosahedron the Icosian game. A similar problem was posed by Euler: Is it possible for a knight to visit every square of a chessboard without visiting any square twice?
- A list of selected textbooks and articles in combinatorial optimization, compiled by Brian Borchers. (Postscript file.) Updated Feb 9, 1999.
- PORTA, a polyhedral representation algorithm. If you provide the algorithm with an integer programming problem, it will return a list of all the extreme points and information about the facets. Also available from the same site is SMAPO, a library of linear descriptions of polytopes of small instances of various integer programming problems.
- AMPL is a mathematical programming and optimization modeling language. You can input your model into AMPL in a reasonably intuitive way and it will use a solver (such as MINOS or CPLEX) for solving the problem. It is capable of solving linear, nonlinear, and integer programs. Here is local information about AMPL, including information about using it on RCS. You can download the first chapter of the book.
- A survey paper on GRASP.
- A survey paper on metaheuristics for the TSP (scroll down to the last couple of papers on the TSP, since the papers are in chronological order).
- A survey paper on tabu search.
- The semidefinite programming homepage maintained by Christof Helmberg.
- A survey paper by Mike Todd on semidefinite programming, with an emphasis on algorithms. (Acta Numerica 10 (2001), pp. 515-560.)
- A survey paper by Michel Goemans on semidefinite programming in combinatorial optimization. (Mathematical Programming, 79 (1997), pages 143-161.)
- Myths and counterexamples in optimization. This site shows that you have to be careful about your assumptions when you state some things that are "obvious" in optimization.
- A list of operations research sites.
- A compendium of approximability results for NP optimization problems.
- Some papers on the hardness of approximation by Sanjeev Arora.
Back to John Mitchell's homepage
Current semester Mathematics Course Materials.
RPI Math
DSES